第九章 糾錯編碼1

1、第九章第九章 糾錯編碼糾錯編碼1 1 糾錯碼的分類糾錯碼的分類2 2 糾錯碼的基本概念糾錯碼的基本概念 3 3 線性分組碼線性分組碼 4 4 漢明碼漢明碼 5 5 循環(huán)碼循環(huán)碼l 香農(nóng)第二定理證明，當(dāng)香農(nóng)第二定理證明，當(dāng) 時時 的碼存在。的碼存在。l 證明過程采用的是隨機編碼的方法：證明過程采用的是隨機編碼的方法：隨機編碼所得的碼集很大，通過搜索得到好碼的方法在實隨機編碼所得的碼集很大，通過搜索得到好碼的方法在實際上很難實現(xiàn)；際上很難實現(xiàn)；即時找到了好碼，這種碼的碼字也沒有規(guī)律，不便于譯碼。即時找到了好碼，這種碼的碼字也沒有規(guī)律，不便于譯碼。l 真正實用的信道編碼方法還需要通過各種數(shù)學(xué)工具真正

2、實用的信道編碼方法還需要通過各種數(shù)學(xué)工具來構(gòu)造，使碼具有好的結(jié)構(gòu)性以便于譯碼。來構(gòu)造，使碼具有好的結(jié)構(gòu)性以便于譯碼。RC0EP l 糾錯編碼的糾錯編碼的基本思路基本思路： 根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一些冗余碼元，這些冗余碼元與信息碼元之間以某入一些冗余碼元，這些冗余碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。種確定的規(guī)則相互關(guān)聯(lián)（約束）。 在接收端按照既定的規(guī)則檢驗信息碼元與監(jiān)督碼在接收端按照既定的規(guī)則檢驗信息碼元與監(jiān)督碼元之間的關(guān)系。如果傳輸過程出錯，則信息碼元與監(jiān)元之間的關(guān)系。如果傳輸過程出錯，則信息碼元與監(jiān)督碼元之間的關(guān)

3、系將受到破壞，從而可以發(fā)現(xiàn)錯誤乃督碼元之間的關(guān)系將受到破壞，從而可以發(fā)現(xiàn)錯誤乃至糾正錯誤。至糾正錯誤。概述概述干擾一般分為兩種形式：干擾一般分為兩種形式：一是隨機噪聲，它主要來源于設(shè)備的熱噪聲和散彈一是隨機噪聲，它主要來源于設(shè)備的熱噪聲和散彈噪聲以及傳播媒介的熱噪聲，它是通信系統(tǒng)中的主噪聲以及傳播媒介的熱噪聲，它是通信系統(tǒng)中的主要噪聲；要噪聲；二是脈沖干擾和信道衰落，它的特點是突發(fā)出現(xiàn)，二是脈沖干擾和信道衰落，它的特點是突發(fā)出現(xiàn)，主要來源于雷電、通電開關(guān)、負(fù)荷突變或設(shè)備故障主要來源于雷電、通電開關(guān)、負(fù)荷突變或設(shè)備故障等。等。 概述概述信道可分為三類：信道可分為三類：1. 只產(chǎn)生隨機錯誤的信道稱

4、為隨機信道。比如衛(wèi)星信道、只產(chǎn)生隨機錯誤的信道稱為隨機信道。比如衛(wèi)星信道、同軸電纜、光纜信道以及大多數(shù)微波中繼信道。同軸電纜、光纜信道以及大多數(shù)微波中繼信道。2. 產(chǎn)生突發(fā)錯誤的信道稱為突發(fā)信道。實際的短波信道、產(chǎn)生突發(fā)錯誤的信道稱為突發(fā)信道。實際的短波信道、移動通信信道、由于差傷造成成串差錯的光盤和磁盤，均移動通信信道、由于差傷造成成串差錯的光盤和磁盤，均為這一類信道。為這一類信道。3. 有些實際信道既有隨機錯誤又有突發(fā)錯誤，稱為混合有些實際信道既有隨機錯誤又有突發(fā)錯誤，稱為混合信道。信道。 根據(jù)不同的信道類型設(shè)計的信道編碼分為糾隨機錯誤根據(jù)不同的信道類型設(shè)計的信道編碼分為糾隨機錯誤碼、糾突

5、發(fā)錯誤碼和糾混合錯誤碼。碼、糾突發(fā)錯誤碼和糾混合錯誤碼。 概述概述在通信系統(tǒng)中，糾檢錯的工作方式有：在通信系統(tǒng)中，糾檢錯的工作方式有：(1) 反饋重傳反饋重傳(ARQ)(2) 前向糾錯前向糾錯(FEC)(3) 混合糾錯混合糾錯概述概述 發(fā)送端經(jīng)編碼后發(fā)出能夠發(fā)現(xiàn)錯誤的碼，接收端收到后經(jīng)發(fā)送端經(jīng)編碼后發(fā)出能夠發(fā)現(xiàn)錯誤的碼，接收端收到后經(jīng)檢驗，如果發(fā)現(xiàn)傳輸中有錯誤，則通過反饋系統(tǒng)把這一判斷結(jié)檢驗，如果發(fā)現(xiàn)傳輸中有錯誤，則通過反饋系統(tǒng)把這一判斷結(jié)果反饋回發(fā)端，然后發(fā)送端把前面發(fā)出的信息重新傳送一次，果反饋回發(fā)端，然后發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認(rèn)為正確地收到信息為止。直到接收端認(rèn)為

6、正確地收到信息為止。 (1) 反饋重傳反饋重傳(ARQ)mCRm檢錯檢錯編碼編碼信道信道檢錯檢錯譯碼譯碼反饋反饋(2) 前向糾錯前向糾錯(FEC)mCRm糾錯糾錯編碼編碼信道信道糾錯糾錯譯碼譯碼 發(fā)送端發(fā)出的是具有糾錯能力的糾錯碼，接收端根據(jù)譯發(fā)送端發(fā)出的是具有糾錯能力的糾錯碼，接收端根據(jù)譯碼規(guī)則進行譯碼。當(dāng)誤碼個數(shù)在碼的糾錯能力范圍內(nèi)時，譯碼規(guī)則進行譯碼。當(dāng)誤碼個數(shù)在碼的糾錯能力范圍內(nèi)時，譯碼器可以自動糾正錯誤。碼器可以自動糾正錯誤。特點：特點： 1 1）前向糾錯方式不需要反饋信道，特別適合于只能）前向糾錯方式不需要反饋信道，特別適合于只能 提供單向信道的場合。提供單向信道的場合。2 2）由

7、于能自動糾錯，不要求檢錯重發(fā)，因而延時小，）由于能自動糾錯，不要求檢錯重發(fā)，因而延時小， 實時性好。實時性好。3 3）隨著糾錯能力的增強，譯碼設(shè)備也變得復(fù)雜。）隨著糾錯能力的增強，譯碼設(shè)備也變得復(fù)雜。 (3) 混合糾錯混合糾錯 對發(fā)送端進行適當(dāng)?shù)木幋a。當(dāng)對發(fā)送端進行適當(dāng)?shù)木幋a。當(dāng)錯誤不嚴(yán)重錯誤不嚴(yán)重，在碼的，在碼的糾錯能力范圍之內(nèi)時，采用自動糾錯；當(dāng)產(chǎn)生的糾錯能力范圍之內(nèi)時，采用自動糾錯；當(dāng)產(chǎn)生的差錯超差錯超出碼的糾錯能力范圍出碼的糾錯能力范圍時，通過反饋系統(tǒng)要求發(fā)端重發(fā)。時，通過反饋系統(tǒng)要求發(fā)端重發(fā)。(1) 按按功能功能分：分： 檢錯碼：僅能檢測誤碼檢錯碼：僅能檢測誤碼 糾錯碼：可糾正誤碼糾

8、錯碼：可糾正誤碼 糾刪碼：兼糾錯和檢錯能力糾刪碼：兼糾錯和檢錯能力糾錯碼糾錯碼1 1 糾錯碼的分類糾錯碼的分類(2) 按信息碼元與監(jiān)督碼元之間的檢驗關(guān)系分： - 線性碼線性碼：滿足線性關(guān)系- 非線性碼非線性碼：不存在線性關(guān)系 (3) 按信息碼元與監(jiān)督碼元之間的按信息碼元與監(jiān)督碼元之間的約束方式約束方式不同分：不同分： 分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關(guān)。分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關(guān)。 卷積碼：本碼組的監(jiān)督碼元不僅和本碼組的信息元相卷積碼：本碼組的監(jiān)督碼元不僅和本碼組的信息元相關(guān)，而且與前面碼組的信息碼元有關(guān)。關(guān)，而且與前面碼組的信息碼元有關(guān)。碼與碼相互影響不能碼與

9、碼相互影響不能分開，又稱數(shù)碼或鏈碼分開，又稱數(shù)碼或鏈碼重點討論線性分組碼重點討論線性分組碼(4) 按信息碼元在編碼后是否保持原形式不變：按信息碼元在編碼后是否保持原形式不變： 即：根據(jù)信息元在分組碼中的位置分為系統(tǒng)碼，非系統(tǒng)碼系統(tǒng)碼：信息碼元與監(jiān)督碼元在分組內(nèi)有確定位置，系統(tǒng)碼：信息碼元與監(jiān)督碼元在分組內(nèi)有確定位置，編碼后的信息碼元保持不變；編碼后的信息碼元保持不變；非系統(tǒng)碼：信息位打亂，與編碼前不同。非系統(tǒng)碼：信息位打亂，與編碼前不同。(5)(5)按糾正差錯的類型可分為：按糾正差錯的類型可分為： 糾糾隨機錯誤隨機錯誤碼碼 糾糾突發(fā)錯誤突發(fā)錯誤碼碼 糾糾隨機和突發(fā)錯誤隨機和突發(fā)錯誤碼碼非線性卷

10、積碼線性樹碼非線性非循環(huán)碼循環(huán)碼線性分組碼糾錯碼糾錯碼按結(jié)構(gòu)分類如下：糾錯碼按結(jié)構(gòu)分類如下： 1 1 糾錯碼的分類糾錯碼的分類(續(xù)續(xù))l 分組碼的表示方法：分組碼的表示方法： （二元分組碼）（二元分組碼） 信息碼組由信息碼組由 k 個信息碼元組成，共有個信息碼元組成，共有 2k 個不同的個不同的信息碼組；信息碼組；信息位信息位 附加附加 個校驗碼元，每個校驗碼元是該信息個校驗碼元，每個校驗碼元是該信息碼組的某些信息碼元模碼組的某些信息碼元模2和；和；校驗位或監(jiān)督位校驗位或監(jiān)督位 編碼器輸出長度為編碼器輸出長度為n的碼字；的碼字；碼字的數(shù)目共有碼字的數(shù)目共有 2k ；這這2k 個碼字的集合稱為個

11、碼字的集合稱為 (n,k) 分組碼；分組碼；rnk2 2 糾錯碼的基本概念糾錯碼的基本概念信息傳輸率（碼率），編碼效率信息傳輸率（碼率），編碼效率o 對 二進制(n, k)線性分組碼，合法碼字?jǐn)?shù)為2k，可用編碼空間的序列數(shù)為2n個。許用序列 ，禁用序列 o 任一種2k信息集合到二進制序列集合(2n)的映射都是一種(n, k)碼。因此總共可能的編碼方案有 種。22knC2 2 糾錯碼的基本概念（續(xù)）糾錯碼的基本概念（續(xù)）o 發(fā)現(xiàn)或構(gòu)造好碼是信道編碼研究的主要問題：編碼方案太多，以至全局搜索是不可能的?，F(xiàn)實的做法是對編碼方案加以一定的約束，在一個子集中尋找局部最優(yōu)。這種約束即要能包含盡可能好的碼，

12、又要便于分析，便于譯碼。o 線性分組碼是最具實用價值的一類碼，比如漢明碼、循環(huán)碼、BCH碼、RS碼等。2 2 糾錯碼的基本概念糾錯碼的基本概念（續(xù)）（續(xù)）2 2 糾錯碼的基本概念糾錯碼的基本概念（續(xù)）（續(xù)）對信道編碼的一般要求是：對信道編碼的一般要求是：糾錯檢錯能力強；糾錯檢錯能力強；信息傳輸率高；信息傳輸率高；編碼規(guī)律簡單，實現(xiàn)設(shè)備簡單且費用合理；編碼規(guī)律簡單，實現(xiàn)設(shè)備簡單且費用合理；與信道的差錯統(tǒng)計特性相匹配。與信道的差錯統(tǒng)計特性相匹配。 漢明距離漢明距離niiiiccc21cnjjjjccc21cnkjijikkccd1),(cc漢明距離滿足距離公理漢明距離滿足距離公理(1) 非負(fù)性非負(fù)

13、性(2) 對稱性對稱性(3) 三角不等式三角不等式 0),(jidcc),(),(ijjiddcccc),(),(),(jllijidddcccccc2 2 糾錯碼的基本概念糾錯碼的基本概念漢明重量漢明重量 nkiikcW1)(cniiiiccc21c碼碼C 的最小漢明距離的最小漢明距離 jiddjiji,: ),(minminCcccc),()()(),(10cccccclljijnkijidWWccdkk線性分組碼的最小漢明距離等于非零碼字的最小重量。線性分組碼的最小漢明距離等于非零碼字的最小重量。2 2 糾錯碼的基本概念糾錯碼的基本概念3 3 線性分組碼線性分組碼327216321531

14、4CCCCCCCCCCCCC00007326215321431CCCCCCCCCCCCC3.1 3.1 校驗矩陣與生成矩陣校驗矩陣與生成矩陣 7654321CCCCCCCC(1) 校驗矩陣校驗矩陣000010001100100011001011100011017654321CCCCCCCTT0HC0CHTIQH 1011000111010011000100110001H1234567 ,c c c c c c cC C0,0,0,00 0則則TTHC0HC0TCH0CH0令令l 被稱為被稱為校驗矩陣校驗矩陣。l 對對 線性分組碼，校驗矩陣為線性分組碼，校驗矩陣為 維矩陣。維矩陣。l對于系統(tǒng)碼，

15、校驗矩陣可以表示為對于系統(tǒng)碼，校驗矩陣可以表示為H, )n k（()nkn=HQI其中 為 維矩陣， 為 維單位矩陣。Q()nkk()()nknkI3272163215314332211CCCCCCCCCCCCCCCCCCC3272163215314CCCCCCCCCCCCCl由校驗方程，得到由校驗方程，得到(2) (2) 生成矩陣生成矩陣101110011100100111001321CCCCPIG l令令123 ,c c cm100111001001110011101GIPCmG其中其中 為為 維矩陣，維矩陣， 為為 維單位矩陣。維單位矩陣。l 被稱為被稱為生成矩陣生成矩陣。l 對對 線性

16、分組碼，生成矩陣為線性分組碼，生成矩陣為 維矩陣。維矩陣。l對于系統(tǒng)碼，生成矩陣可以表示為對于系統(tǒng)碼，生成矩陣可以表示為G, )n k（knP()knkkkGIPIl把生成矩陣的每一行用一個行向量把生成矩陣的每一行用一個行向量 來來表示，則生成矩陣可以表示為表示，則生成矩陣可以表示為12kmmmm12kGGGG1kiiimCmGG,1,2,iikG Gl令令 ，則，則l由于生成矩陣由于生成矩陣GG的每一行都是一個碼字，所以的每一行都是一個碼字，所以G G 的每的每行都滿足行都滿足 ，則有，則有l(wèi)對于標(biāo)準(zhǔn)形式的校驗矩陣和監(jiān)督矩陣，有對于標(biāo)準(zhǔn)形式的校驗矩陣和監(jiān)督矩陣，有TTi iH HG G0 0

17、TH HG G0 0TTT+Q QI II IP PQ QP P0 0HGTQ QP P(3) (3) 校驗矩陣和生成矩陣的關(guān)系校驗矩陣和生成矩陣的關(guān)系l線性分組碼的封閉性線性分組碼的封閉性：線性分組碼中任意兩個碼字之：線性分組碼中任意兩個碼字之后仍然是該碼的碼字。后仍然是該碼的碼字。證明：設(shè)證明：設(shè) 和和 分別是碼分別是碼 中的兩個碼字，因此有中的兩個碼字，因此有即即 滿足監(jiān)督方程，所以是碼滿足監(jiān)督方程，所以是碼 中的一個碼字。中的一個碼字。TT1TTTT1212TT2(+)H HC C0 0H H C CC CH HC CH HC C0 0H HC C0 01C CC CC C2C C12

18、+C CC C例：重復(fù)碼是一個（例：重復(fù)碼是一個（3,1）線性分組碼。其生成矩陣為）線性分組碼。其生成矩陣為111G1111111321mmmmCCCC例：（例：（4,3）偶校驗碼是一個（）偶校驗碼是一個（4,3）線性分組碼，其生成）線性分組碼，其生成矩陣為矩陣為 110010101001G1100101010013213213214321mmmmmmmmmCCCCC例例 已知生成矩陣為已知生成矩陣為 求生成的線性分組碼及由求生成的線性分組碼及由H 生成的線性生成的線性分組碼。分組碼。 101110011100100111001G11101001111101001110101001110110

19、011101000111010011010011101000111010010000000000CmmGC 1000110010001100101110001101IQHQPT101111100111PPIG 101110011100100111001G1000110010001100101110001101IQH1101000011010011100101010001111111111111110100111011010011101110001011001011000101110100111010100111010011000101100001110100111011000101100101

20、10001010100111010000111010011001011000100001011000100000000000Cm關(guān)于碼的最小距離與糾、檢錯能力的關(guān)系有以下結(jié)論：關(guān)于碼的最小距離與糾、檢錯能力的關(guān)系有以下結(jié)論：對于（對于（n，k）線性分組碼，設(shè)）線性分組碼，設(shè) 為最小漢明距離。為最小漢明距離。（）（）這組碼有糾正這組碼有糾正 u 個錯誤的充要條件是個錯誤的充要條件是mind12min uduu2u+1對于一個二進制對稱信道，當(dāng)輸入為對于一個二進制對稱信道，當(dāng)輸入為2k個等可能的個等可能的n長長碼字，則最大后驗概率準(zhǔn)則等效于最小漢明距離譯碼準(zhǔn)則。碼字，則最大后驗概率準(zhǔn)則等效于最小漢

21、明距離譯碼準(zhǔn)則。 3.2 3.2 線性分組碼的糾、檢錯能力線性分組碼的糾、檢錯能力 lll+1（）具有檢測（）具有檢測l個錯誤的充要條件是個錯誤的充要條件是1min lduutlt+l+1（）具有糾正（）具有糾正 t 個錯誤，同時可以發(fā)現(xiàn)個錯誤，同時可以發(fā)現(xiàn)l個錯誤的充分必個錯誤的充分必要條件為要條件為1minltd碼的糾錯能力碼的糾錯能力u與碼字的長度與碼字的長度n和消息數(shù)和消息數(shù)M滿足以下關(guān)系：滿足以下關(guān)系：02uinniMC3.3 校驗矩陣與最小距離的關(guān)系校驗矩陣與最小距離的關(guān)系 對于（對于（n，k）線性分組碼：校驗矩陣）線性分組碼：校驗矩陣H中的任意中的任意t列線列線性無關(guān)而性無關(guān)而t

22、 +1列線性相關(guān)，則碼的最小距離列線性相關(guān)，則碼的最小距離(碼字的最小碼字的最小重量重量)為為t+1。反過來說，若碼的最小距離。反過來說，若碼的最小距離(碼字的最小碼字的最小重量重量)為為t+1則則H 的任意的任意t列線性無關(guān)而列線性無關(guān)而t+1列線性相關(guān)。列線性相關(guān)。3.4 線性分組碼的伴隨式線性分組碼的伴隨式 0CHTR=C+E E=e1 e2 en TTTTTEHCHEHHCERHS)(1) ，說明，說明R 是一個碼字是一個碼字;2) 2) ，說明，說明R 不是碼字，傳輸過程產(chǎn)生了誤碼。不是碼字，傳輸過程產(chǎn)生了誤碼。0S S0S STTS = HRTTS = HEl 令令12121nTT

23、niiinee=eeSHEHHHHSHEHHHH12n= eeeE E12n=HHHHHHHHiH HH H 則則（其中（其中 表示表示 的列向量）的列向量） 結(jié)論：結(jié)論：1) 當(dāng)傳輸過程沒有錯誤時當(dāng)傳輸過程沒有錯誤時 ，即，即 ， 2)2)當(dāng)發(fā)生一位錯誤時，當(dāng)發(fā)生一位錯誤時， 是校驗矩陣的某一列。是校驗矩陣的某一列。3)3)當(dāng)發(fā)生多個錯誤時，當(dāng)發(fā)生多個錯誤時， 為校驗矩陣對應(yīng)列的模為校驗矩陣對應(yīng)列的模2 2和。和。0 00=E ET0S STS STS S例例： 設(shè)設(shè)(7,3)線性分組碼的校驗矩陣為線性分組碼的校驗矩陣為1011000111010011000100110001H（1）接收碼字

24、）接收碼字R R=(1010011)，TT101011000011110100001100010000110001011 S = HR傳輸過程中沒有誤碼，傳輸過程中沒有誤碼，=CRCR（2）接收碼字）接收碼字R R=(1110011)，TT111011000011110100101100010100110001111 S = HR ，第，第2位出錯，位出錯，= (1010011)=+C CR RE ET2SH(0100000)=E E（3）接收碼字）接收碼字R R=(0011011)，TT001011000011110100111100010100110001011 S = HR與與 中的任一

25、列都不相同，中的任一列都不相同，TSHT142756SHHHHHH不能確定到底是哪兩位出錯，不能正確譯碼。不能確定到底是哪兩位出錯，不能正確譯碼。niiinnnnTTeeeeeee122112121HHHHHHHHES線性分組碼的伴隨式譯碼線性分組碼的伴隨式譯碼 ERCEEHST編碼C=mG計算Em輸出CER0RHTCRECnoyes輸出R02uinniMC若（若（n，k）線性分組碼能夠糾正）線性分組碼能夠糾正 u 個錯誤，則其校驗位個錯誤，則其校驗位的數(shù)目必須滿足的數(shù)目必須滿足 uiinknC02完備碼完備碼l漢明碼是一種能夠糾正單個錯誤的完備碼。漢明碼是一種能夠糾正單個錯誤的完備碼。漢明碼

26、最小碼距漢明碼最小碼距設(shè)監(jiān)督碼共有設(shè)監(jiān)督碼共有m位，對于漢明碼必然有位，對于漢明碼必然有 。通常漢明碼可以表示成通常漢明碼可以表示成 。mn = 21mm(21,21)mmin3d4 漢明碼漢明碼 在同樣的糾錯能力下，漢明碼的碼率是最高的在同樣的糾錯能力下，漢明碼的碼率是最高的 12111212mmmmRl漢明碼監(jiān)督矩陣構(gòu)成的兩種方式：漢明碼監(jiān)督矩陣構(gòu)成的兩種方式：構(gòu)成構(gòu)成 H H 陣的標(biāo)準(zhǔn)形式，陣的標(biāo)準(zhǔn)形式， 。按按m位的二進制數(shù)的位的二進制數(shù)的自然自然順序從左到右排列（不包順序從左到右排列（不包括全括全0列）。當(dāng)發(fā)生可糾的單個錯誤時，伴隨式為列）。當(dāng)發(fā)生可糾的單個錯誤時，伴隨式為 H H

27、陣中對應(yīng)的列，譯碼比較方便。陣中對應(yīng)的列，譯碼比較方便。非標(biāo)準(zhǔn)形式的監(jiān)督矩陣可以通過列置換變成標(biāo)準(zhǔn)形非標(biāo)準(zhǔn)形式的監(jiān)督矩陣可以通過列置換變成標(biāo)準(zhǔn)形式的監(jiān)督矩陣，糾錯能力保持不變。式的監(jiān)督矩陣，糾錯能力保持不變。mHQIl如果給漢明碼添加一位奇偶校驗位，可得到擴展?jié)h明碼：如果給漢明碼添加一位奇偶校驗位，可得到擴展?jié)h明碼： 信息位保持不變，監(jiān)督位增加一位。信息位保持不變，監(jiān)督位增加一位。 最小碼距最小碼距 ， 可糾正一位錯誤，可糾正一位錯誤，同時發(fā)現(xiàn)兩位錯誤。同時發(fā)現(xiàn)兩位錯誤。min4d111000HH1214mindl擴展?jié)h明碼的監(jiān)督方程：擴展?jié)h明碼的監(jiān)督方程： l循環(huán)碼是線性分組碼的一個重要子集

28、。循環(huán)碼是線性分組碼的一個重要子集。l循環(huán)碼除了具有線性分組碼的一般性質(zhì)外，還具有循環(huán)碼除了具有線性分組碼的一般性質(zhì)外，還具有循循環(huán)性環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。到的碼組仍然是許用碼組。 l循環(huán)碼有嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)，檢錯和糾錯能力較循環(huán)碼有嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)，檢錯和糾錯能力較強，而且編碼和解碼設(shè)備都不太復(fù)雜。強，而且編碼和解碼設(shè)備都不太復(fù)雜。5 循環(huán)碼循環(huán)碼5 循環(huán)碼循環(huán)碼 1)對于二進制碼，碼多項式的每個系數(shù)不是對于二進制碼，碼多項式的每個系數(shù)不是0就是就是1。 2) 僅是碼元僅是碼元位置的標(biāo)記。我們并

29、不關(guān)心位置的標(biāo)記。我們并不關(guān)心 的取值。的取值。 l設(shè)循環(huán)碼的碼字為設(shè)循環(huán)碼的碼字為 ，用碼多項式表，用碼多項式表示為示為120nnCccc121210( ).nnnnC xcxcxc xcl碼字（碼字（1100101）可以表示為：）可以表示為：xx 654321652( )11001011C xxxxxxxxxx l循環(huán)碼的循環(huán)特性可以用碼多項式來證明。循環(huán)碼的循環(huán)特性可以用碼多項式來證明。,mpQpnnn()mpn模l在整數(shù)運算中，有在整數(shù)運算中，有模模n運算運算。若一個整數(shù)。若一個整數(shù)m可以表示為可以表示為: 則則在模在模n運算下，一整數(shù)運算下，一整數(shù)m等于其被等于其被n除所得的余數(shù)。除

30、所得的余數(shù)。5 循環(huán)碼循環(huán)碼l在碼多項式運算中也有類似的按模運算法則。在碼多項式運算中也有類似的按模運算法則。l若一任意多項式若一任意多項式F(x)被一個被一個n次多項式次多項式N(x)除，得到商除，得到商式式Q(x)和一個次數(shù)小于和一個次數(shù)小于n的余式的余式R(x)，也就是：，也就是： 則可以寫為：則可以寫為： ( )()( )( )( )F xR XQ xN xN x( )( )( )F xR xN x模l在循環(huán)碼中，若在循環(huán)碼中，若 是一個長為是一個長為n的許用碼字，則的許用碼字，則 在模在模 運算下，也是一個許用碼字。運算下，也是一個許用碼字。( )C x( )ix C x1nx 例例

31、 某循環(huán)碼的一個碼字為某循環(huán)碼的一個碼字為1100101，則，則 若將此碼左移一位，得：若將此碼左移一位，得： 對應(yīng)的碼字為對應(yīng)的碼字為1001011，與將碼字，與將碼字1100101循環(huán)左移循環(huán)左移一位相同。一位相同。 652( )1C xxxx763( )xC xxxxx763763mod11xxxxxxxx5 循環(huán)碼循環(huán)碼012211)(cxcxcxcxCnn102112) 1 ()()(nnncxcxcxcxxCxC2120132)2()()(nnnncxcxcxcxCxxC1223101) 1()()(cxcxcxcxCxxCnnn5 循環(huán)碼循環(huán)碼l從碼中取出一個前面從碼中取出一個前

32、面k-1位都是位都是0的碼字，定義這個碼的碼字，定義這個碼字的碼多項式為生成多項式字的碼多項式為生成多項式 。l 在在 循環(huán)碼中，除了全循環(huán)碼中，除了全0碼字以外，其他碼字的連碼字以外，其他碼字的連0個數(shù)最多只有個數(shù)最多只有k-1個。個。( , )n k( )g xnkl 碼多項式的次數(shù)為碼多項式的次數(shù)為 ，且常數(shù)項不為，且常數(shù)項不為0。5 循環(huán)碼循環(huán)碼信息比特碼字（循環(huán)1）信息比特碼字(循環(huán)2）信息比特碼字000100100101011010001011110000010110010110010110001100011000101101100011000100011 010001111001101011011110001110101001110111010100111