通信原理-CH11-差錯控制編碼和線性分組碼

1、第十一章第十一章 差錯控制編碼和線性分組碼差錯控制編碼和線性分組碼主要內(nèi)容和重點主要內(nèi)容和重點n差錯控制編碼的基本概念差錯控制編碼的基本概念n線性分組碼線性分組碼 n性質(zhì)、基本原理n校正子n監(jiān)督矩陣n生成矩陣n漢明碼n循環(huán)碼循環(huán)碼n概念及性質(zhì)n生成多項式n生成矩陣與監(jiān)督矩陣n編碼器2.1 引言引言 n為什么要引入差錯控制編碼？n什么是差錯控制編碼（信道編碼）？n差錯控制編碼的3種方式 n信道發(fā)生差錯的模式n差錯控制編碼的基本原理n差錯控制編碼的分類n編碼信道及香農(nóng)編碼定理2.1 引言引言 n為什么要引入差錯控制編碼？n在實際信道上傳輸數(shù)字信號時，由于信道傳輸特性不理想及加性噪聲的影響，接收端所

2、收到的數(shù)字信號不可避免地會發(fā)生錯誤n為了在已知信噪比情況下達(dá)到一定的誤比特率指標(biāo)，應(yīng)該合理設(shè)計基帶信號，選擇調(diào)制解調(diào)方式，采用時域、頻域均衡，使誤比特率盡可能降低n但若誤比特率仍不能滿足要求，則必須采用信道編碼若誤比特率仍不能滿足要求，則必須采用信道編碼（即差錯控制編碼），將誤比特率進(jìn)一步降低（即差錯控制編碼），將誤比特率進(jìn)一步降低2.1 引言引言 n什么是差錯控制編碼n差錯控制編碼的基本思路差錯控制編碼的基本思路：n在發(fā)送端將被傳輸?shù)男畔⒏缴弦恍┍O(jiān)督碼元，這些多余的碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）n接收端按照既定的規(guī)則校驗信息碼元與監(jiān)督碼元之間的關(guān)系，一旦傳輸發(fā)生差錯，則信

3、息碼元與監(jiān)督碼元的關(guān)系就受到破壞，從而接收端可以發(fā)現(xiàn)錯誤乃至糾正錯誤n差錯控制編碼所要解決的問題：各種編碼和譯碼差錯控制編碼所要解決的問題：各種編碼和譯碼方法方法2.1 引言引言 n差錯控制的三種方式n檢錯重發(fā)（ARQ）n在接收端根據(jù)編碼規(guī)則進(jìn)行檢查，如果發(fā)現(xiàn)規(guī)則被破壞，則通過反向信道要求發(fā)送端重新發(fā)送，直到接收端檢查無誤為止nARQ系統(tǒng)的重發(fā)機(jī)制：停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)n需要反饋信道，效率較低，但是性能很好發(fā)收能夠發(fā)現(xiàn)錯誤的碼應(yīng)答信息2.1 引言引言 n差錯控制的三種方式（續(xù)）n前向糾錯（FEC） n發(fā)送端發(fā)送能糾正錯誤的編碼，在接收端根據(jù)接收到的碼和編碼規(guī)則，能自動糾正傳輸中的錯

4、誤n不需要反饋信道，實時性好，但是隨著糾錯能力的提高，編譯碼設(shè)備復(fù)雜 發(fā)收可以糾正錯誤的碼2.1 引言引言 n差錯控制的三種方式（續(xù)）n混合方式n結(jié)合FEC和ARQ：在糾錯能力范圍內(nèi)，自動糾正錯誤，超出糾錯范圍則要求發(fā)送端重新發(fā)送發(fā)收可以發(fā)現(xiàn)和糾正錯誤的碼應(yīng)答信號2.1 引言引言 n信道發(fā)生差錯的模式n隨機(jī)差錯：n差錯的出現(xiàn)是隨機(jī)的，差錯出現(xiàn)的位置是隨機(jī)分布的n一般由信道的加性隨機(jī)噪聲引起n這種信道稱為隨機(jī)信道隨機(jī)信道 n突發(fā)差錯：n差錯的出現(xiàn)是一連串出現(xiàn)的。這種情況如移動通信中信號在某一段時間內(nèi)發(fā)生衰落，造成一串差錯；光盤上的一條劃痕等等n這樣的信道稱之為突發(fā)信道突發(fā)信道 n混合差錯：n既有

5、突發(fā)錯誤又有隨機(jī)差錯的情況n這種信道稱之為混合信道混合信道 2.1 引言引言 n差錯控制編碼的基本原理 n以差錯重發(fā)編碼來闡述差錯編碼在相同的信噪比情況下為什么會獲得更好的系統(tǒng)性能？ n例1：假設(shè)發(fā)送的信息0、1等概，采用2PSK方式，則最佳接收的系統(tǒng)誤比特率為 ，現(xiàn)假設(shè)n如果將信息0編碼成00，信息1編碼成11，則在接收端：n如果發(fā)送00，收到01、10，知道發(fā)生了差錯，要求發(fā)送端重新傳輸，直到傳送正確為止n只有當(dāng)收到11時，我們才錯誤地認(rèn)為當(dāng)前發(fā)送的是1 n因此在這種情況下發(fā)生譯碼錯誤的概率是 n同理，如果發(fā)送的是11，只有收到00時才可能發(fā)生錯誤譯碼，因此在這種情況下發(fā)生譯碼錯誤的概率是

6、n故采用00、11編碼的系統(tǒng)誤比特率為 021NEerfcPse310eP221eP221eP2eP2.1 引言引言 n差錯控制編碼的基本原理（續(xù)） n依此類推，可知：n采用000、111編碼的ARQ系統(tǒng)誤比特率是多少？n采用0000、1111編碼的ARQ系統(tǒng)誤比特率是多少？n例2，如例1，如果0、1采用00000、11111編碼，在接收端用如下的譯碼方法，每收到5個比特譯碼一次，采用大數(shù)判決，即5個比特中0的個數(shù)大于1的個數(shù)則譯碼成0，反之譯碼成1；不采用ARQ方式。那么，這種編碼方式就變成了糾錯編碼n由于傳輸錯誤當(dāng)接收端收到11000，10100，10010，10001，01100，010

7、10，01001，00110，00101，00011中的任何一種時，都可以自動糾正成00000n課外題：請計算在這種情況下的系統(tǒng)性能n上述例1、例2的編碼方式叫重復(fù)碼2.1 引言引言 n差錯控制編碼的基本原理（續(xù)） n例3，2PSK系統(tǒng)中誤比特率與Es/N0有關(guān)n我們看到，重復(fù)碼中假設(shè)傳輸時每個符號的Es/N0相等，因此才得到以上的性能分析對比n但是如果我們以Eb/N0的指標(biāo)進(jìn)行比較，則我們看到n例1的 n例2的 n如果要求各系統(tǒng)在Eb/N0相同的情況下進(jìn)行比較（n重復(fù)碼中用了n倍能量來傳輸一個比特，從每個比特能量的角度來看），則可看到這2種系統(tǒng)性能相近（即獲得相近的編碼增益）002NENEs

8、b005NENEsb2.1 引言引言 n差錯控制編碼的基本原理（續(xù)）n當(dāng)x1有n2PSK系統(tǒng)： n2重重復(fù)碼： n編碼增益編碼增益= 221)(xexxerfc00011/22/bENebbPerfcENeEN020011222/bENbebEPerfceNEN00/NENEbb所需要的編碼時達(dá)到一定性能時時所需的未編碼時達(dá)到一定性能2.1 引言引言 n差錯控制編碼的分類n根據(jù)差錯控制編碼的功能不同：n檢錯碼、糾錯碼、糾刪碼（兼檢錯、糾錯）n根據(jù)信息位和校驗位的檢驗關(guān)系：n線性碼（存在線性關(guān)系）和非線性碼n按信息碼元在編碼后是否保持原來的形式n系統(tǒng)碼：保持不變n非系統(tǒng)碼：信息碼元改變了原有的信

9、號形式n按糾正錯誤的類型：n糾正隨機(jī)錯誤的碼：用于隨機(jī)錯誤的信道n糾正突發(fā)錯誤的碼：用于突發(fā)信道2.1 引言引言 n差錯控制編碼的分類（續(xù)）n根據(jù)信息碼元和監(jiān)督碼元的約束方式：n分組碼：監(jiān)督碼元僅與本碼組的信息碼元有關(guān)n卷積碼：監(jiān)督碼元還與前面碼組的信息碼元有約束關(guān)系n分組碼：將k個信息比特編成n個比特的碼字，共有2k個碼字。所有個碼字組成一個分組碼。傳輸時前后碼字之間毫無關(guān)系 n卷積碼：也是將k個信息比特編成n個比特的碼字，但是前后的N個碼字之間相互關(guān)聯(lián) n編碼速率=平均每個碼字所攜帶的信息比特率 kknn個信息比特編成 個比特的碼字2.1 引言引言 n編碼信道n所謂的編碼信道就是將調(diào)制解調(diào)

10、包括在信道內(nèi)的一種模型上的等效。 即如果研究編碼和譯碼，完全可以將調(diào)制、解調(diào)與信道合起來等效成一個等效的信道，這種信道就稱之為編碼信道編碼信道源編碼調(diào)制信道解調(diào)譯碼宿2.1 引言引言 n編碼信道（續(xù)）n根據(jù)調(diào)制解調(diào)的不同輸入和輸出具有不同的類型 n離散無記憶對稱二進(jìn)制輸入二進(jìn)制輸出信道（BSC）n這種情況相應(yīng)于2進(jìn)制調(diào)制解調(diào)+判決n離散無記憶二進(jìn)制輸入多進(jìn)制輸出信道n對應(yīng)于2進(jìn)制輸入，量化后輸出的情況，即所謂的軟譯碼n離散無記憶多進(jìn)制輸入多進(jìn)制輸出n對應(yīng)于多進(jìn)制輸入、量化后輸出n離散無記憶二進(jìn)制輸入連續(xù)輸出n對應(yīng)于二進(jìn)制輸入，模擬輸出（未判決、未量化）2.1 引言引言 n香農(nóng)有擾離散信道的編碼

11、定理n對于一個給定的有擾信道，若信道的容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為編碼器的輸入二進(jìn)制碼元速率），則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值，表示為n其中E(R)稱為誤差指數(shù) n結(jié)論：nn和R一定情況下，為減小P，可增大C n在C及R一定的情況下，增加n，可以 使P指數(shù)下降。從實際的角度看，這時 設(shè)備復(fù)雜性和譯碼延時也隨之增加 )(RnEePE（R） C0 C1 C2 R 2.2 糾錯編碼的基本原理糾錯編碼的基本原理n主要內(nèi)容n碼重、碼距n最小碼距n碼的糾錯、檢錯性能 2.2 糾錯編碼的基本原理糾錯編碼的基本原理n分組碼將k個比特編成n

12、個比特一組的碼字（碼組），記為（n，k）碼n由于輸入有 2k種組合，因此（n，k）碼應(yīng)該有2k個碼字n碼重、碼距n碼重：碼字中1的個數(shù)。如碼字11000的碼重為2n碼距：碼字C1與碼字C2之間不同的比特數(shù)（又稱漢明距） 2.2 糾錯編碼的基本原理糾錯編碼的基本原理n最小碼距n所用碼字中任何兩個碼字之間的碼距的最小值，用 dmin表示n碼的糾錯、檢錯性能：由最小碼距決定 n為了檢測e個錯誤，要求最小碼距n為了糾正t個錯誤，要求最小碼距n為了糾正t個錯誤，同時檢測e個錯誤，要求最小碼距 min1de12min tdmin1()dteet eBAd0tAtB1tAeB1(a)(b)(c)d0d0糾錯

13、碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強距離越大，說明碼字間的最小差別越大，抗干擾能力就越強 2.2 糾錯編碼的基本原理糾錯編碼的基本原理 2.3 常用的簡單編碼常用的簡單編碼 n奇偶監(jiān)督碼（奇偶校驗）n設(shè)奇偶監(jiān)督碼的碼字表示為： n則偶校驗碼： （即偶數(shù)個1） 奇校驗碼： （即奇數(shù)個1）n可見這種碼的最小碼距為2，只能檢1個錯 ),.,(021aaann0.021aaann1.021aaann 奇偶監(jiān)督碼的編碼可以用軟件實現(xiàn)，也可用硬奇偶監(jiān)督碼的編碼可以用軟件實現(xiàn)，也可用硬

14、件電路實現(xiàn)件電路實現(xiàn) 如果碼組如果碼組B無錯，無錯，BA，則，則M0；如果碼組；如果碼組B有單個（或奇數(shù)個）錯誤，則有單個（或奇數(shù)個）錯誤，則M1 a4a3a2a1a0a4a3a2a1信息組編碼輸出b0b4b3b2b1接收碼組檢錯信號SBAM 2.3 常用的簡單編碼常用的簡單編碼 2.3 常用的簡單編碼常用的簡單編碼 n二維奇偶監(jiān)督碼n提高奇偶校驗碼對突發(fā)錯誤的檢測能力 n將若干奇偶校驗碼排成若干行，然后對每列進(jìn)行奇偶校驗，放在最后一行。傳輸時按照列順序進(jìn)行傳輸，在接收端又按照行的順序檢驗是否差錯 n由于突發(fā)錯誤是成串發(fā)生的，經(jīng)過傳輸后錯誤被分散（交織編碼+奇偶校驗） n移動通信中的信道衰落造

15、成突發(fā)錯誤，因此傳輸前，先將輸入的信息比特交織，將突發(fā)錯誤盡可能分散成隨機(jī)錯誤，然后用其它編碼方式來糾正隨機(jī)的錯誤mmnmnnnnncccaaaaaa021202221101211. 2.3 常用的簡單編碼常用的簡單編碼 n恒比碼n每個碼組中的1的個數(shù)都一樣n電傳機(jī)傳輸漢字時每個漢字用4位阿拉伯?dāng)?shù)字表示，每個阿拉伯?dāng)?shù)字用5個比特的碼字表示。由于阿拉伯?dāng)?shù)字只有10個，因此從32中可能的碼字中挑出 =10個1的個數(shù)為3的碼字作為阿拉伯?dāng)?shù)字的編碼方式n譯碼可以采用查表方法，檢錯時檢查1的個數(shù)是否為3n一般用在電傳、電報53C阿拉伯?dāng)?shù)字編碼阿拉伯?dāng)?shù)字編碼101011610101211001711100

16、310110801110411010910011500111001101 2.3 常用的簡單編碼常用的簡單編碼 nISBN國際統(tǒng)一圖書編號n國際圖書的發(fā)行中，用編碼的方式來防止書號在通信過程中發(fā)生錯誤 n如通信原理的書號是ISBN 7-118-01429-Xn其中第一位數(shù)字“7”表示“中國”，“118”表示出版社，“01429”表示書名編號，最后一位“X”表示校驗位（它是羅馬數(shù)字10的表示）n所采用的校驗方式如下所示：n7 1 1 8 0 1 4 2 9 X=10n7 8 9 17 17 18 22 24 33 43n7 15 24 41 58 76 98 122 155 198 198 (模

17、11)=0 2.4 線性分組碼線性分組碼n差錯編碼的重點：各種編碼和譯碼的方法n主要內(nèi)容n性質(zhì)n基本原理n校驗矩陣（監(jiān)督矩陣）n生成矩陣n校正子（伴隨式）n漢明碼2.4 線性分組碼線性分組碼n定義：n將信息碼分組，為每組信息位附加若干監(jiān)督位，且信息位和監(jiān)督位間的關(guān)系可由線性方程組表示的編碼n即可用線性方程組表述碼的規(guī)律性的分組碼 n線性分組碼（n，k）的性質(zhì)n許用碼字（組）為2k個n定義線性分組碼的加法為模2加，乘法為二進(jìn)制乘法。即有n1+1=0、1+0=1、0+1=1、0+0=0 n1x1 = 1, 1x 0 =0, 0 x0 =0, 0 x1 =0n且碼字與碼字的運算是各相應(yīng)比特位上符合上

18、述二進(jìn)制加法運算規(guī)則 2.4 線性分組碼線性分組碼n線性分組碼（n，k）的性質(zhì)（續(xù)）n群：集合G上定義了一種加法運算，如果該運算符合以下4條公理，則稱G是該運算的一個群n封閉性：任何a、b屬于G，有a*b屬于Gn單位元：G中存在一個元素e滿足e*a=an有逆元：任何a屬于G，存在b屬于G滿足a*b=en結(jié)合率成立：a*(b*c)=(a*b)*cn線性分組碼的性質(zhì)：n封閉性。任意兩個許用碼組的和仍是一個許用碼組n最小碼距等于非零碼的最小碼重 2.4 線性分組碼線性分組碼n基本原理n(n, k)碼：碼長n，信息位數(shù)為k，則監(jiān)督位數(shù)r=n-kn校正子（伴隨式）S：為了檢測傳輸過程中是否有錯，將接收到

19、的碼組代入監(jiān)督方程式所得到的結(jié)果n以（7，4）線性分組碼為例，說明（n，k）碼的基本原理n7碼元a6a5a4a3a2a1a0，信息碼元a6a5a4a3，監(jiān)督碼元a2a1a0n校正子S1S2S3與信息碼元及監(jiān)督碼元之間的關(guān)系為654216531264303aaaaSaaaaSaaaaS2.4 線性分組碼線性分組碼n基本原理（續(xù)）n3個校正子可以指示23-1=7種錯誤圖樣，如表所示n可知，（7，4）碼可糾正一位錯誤n在編碼時a2a1a0應(yīng)根據(jù)監(jiān)督方程確定：S1S2S3001010100011101110111000誤碼位置a0a1a2a3a4a5a6無誤654265316430000aaaaaaa

20、aaaaa265416530643aaaaaaaaaaaa即2.4 線性分組碼線性分組碼n基本原理（續(xù)）n由此可得16個許用碼組信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a000000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111112.4 線性分組碼線性分組碼n基本原理（續(xù)）n接收端收到每個碼組后，計算出S1、S2和S3，如不全為0，則查表確定誤碼的位置，予以糾正n如，接收碼組為0000011，可

21、算得S1S2S3011，查表知a3錯n（7，4）碼：dmin=3，能糾正1個誤碼或檢測2個誤碼n(n, k)線性分組碼：nr=n-k個監(jiān)督碼元，有r個校正子，可以指示2r-1個誤碼圖樣n當(dāng)2r-1n（即2rk+r+1）時，就可糾正1位或1位以上的錯誤n編碼效率（編碼速率）：k/n=(2r-r-1)/(2r-1)=1-r/n2.4 線性分組碼線性分組碼n校驗矩陣（監(jiān)督矩陣）n監(jiān)督碼元與信息碼元之間的關(guān)系可表示為監(jiān)督方程形式，上例（7，4）碼的監(jiān)督方程為n簡記為 HAT0T 或或 AHT0 TTTaaaaaaa00000001001101010101100101110123456000100110

22、10101011001011101234560aaaaaaaAH其中2.4 線性分組碼線性分組碼n校驗矩陣（監(jiān)督矩陣）（續(xù)）n稱H為監(jiān)督矩陣n設(shè)收到的碼組為B，則校正子SHBTn故可根據(jù)H及誤碼圖樣表構(gòu)成差錯控制譯碼器n典型形式監(jiān)督矩陣nHP Ir n其中，其中，P為為rk階矩陣，階矩陣，Ir為為rr階單位方陣階單位方陣n各行線性無關(guān)n非典型形式監(jiān)督矩陣可以經(jīng)過行運算化為典型形式n由典型形式監(jiān)督矩陣及信息碼元可算出各監(jiān)督碼元2.4 線性分組碼線性分組碼n生成矩陣n監(jiān)督碼元與信息碼元之間的關(guān)系還可表示為生成方程形式n上述（7，4）碼的生成方程為n稱G為生成矩陣，由生成矩陣G可構(gòu)造差錯控制編碼器

23、110100010101000110010111000111010001010100011001011100013456345634560123456GGAaaaaGaaaaaaaaaaaaaaa或2.4 線性分組碼線性分組碼n生成矩陣（續(xù)）n典型生成矩陣GnGIk Q n其中，其中，QPT為為kr階矩陣，階矩陣，Ik為為kk階單位方陣階單位方陣nPQTn由典型生成矩陣G可以得到系統(tǒng)碼n各行線性無關(guān)n非典型形式生成矩陣可以經(jīng)過行運算化為典型形式2.4 線性分組碼線性分組碼n校正子（伴隨式）n發(fā)送碼組A在傳輸過程中可能發(fā)生誤碼n設(shè)接收到的碼組為Bbn-1 bn-2 b0n則錯誤圖樣 E=B-A，

24、或 B=A+En其中，E= en-1 en-2 e0n校正子為nS=BHT=(A+E)HT=AHT+EHT=EHTnS與E間有確定的關(guān)系iiiiab, 1ab, 0當(dāng)當(dāng)ie2.4 線性分組碼線性分組碼n漢明碼n上述方法構(gòu)造的糾正單個錯誤的線性分組碼n特點n碼長：n2m1n信息碼位：k=2m-m-1n監(jiān)督碼位：r=n-k=mn最小碼距：d=3n糾錯能力：t=12.5 循環(huán)碼循環(huán)碼n概念、性質(zhì)和多項式表示n生成多項式n生成矩陣與監(jiān)督矩陣n編碼器2.5 循環(huán)碼循環(huán)碼n概念及性質(zhì)n線性分組碼中最重要的一種子類，比較成熟n特點n代數(shù)結(jié)構(gòu)清晰：有嚴(yán)格的代數(shù)理論基礎(chǔ)n性能較好：可糾隨機(jī)錯誤和突發(fā)錯誤n編譯碼

25、簡單：特殊的代數(shù)性質(zhì)有助于按照要求的糾錯能力構(gòu)造，并且簡化譯碼算法n易于實現(xiàn)：很容易用帶反饋的移位寄存器實現(xiàn)n目前的計算機(jī)糾錯系統(tǒng)中廣泛使用的線性分組碼2.5 循環(huán)碼循環(huán)碼n概念及性質(zhì)（續(xù)）n例：設(shè)（7，4）漢明碼C的校驗矩陣和生成矩陣為 n得到16個碼組是：n（1000101）（0001011）（0010110）（0101100）n（1011000）（0110001）（1100010）n（0100111）（1001110）（0011101）（0111010）n（1110100）（1101001）（1010011）n（1111111）（0000000）n可以看到：如果Ci是C的碼組，則它的左右

26、移位都是C的碼組，具有這種特性的線性分組碼稱為循環(huán)碼循環(huán)碼 1101000011010011100101010001G100101101011100010111H2.5 循環(huán)碼循環(huán)碼n概念及性質(zhì)（續(xù)）n循環(huán)碼的性質(zhì)：n封閉性n任何許用碼組的線性和還是許用碼組。由此性質(zhì)可以得到：線性碼都包含全零碼線性碼都包含全零碼n最小碼重就是最小碼距最小碼重就是最小碼距n循環(huán)性n 任何許用的碼組循環(huán)移位后的碼組還是許用碼組 2.5 循環(huán)碼循環(huán)碼n概念及性質(zhì)（續(xù)）n多項式表示：n目的：用代數(shù)理論的方法研究循環(huán)碼的特性n定義：碼 的碼多項式如下 n其中，D為實變量、其冪次代表移位次數(shù)， nGF（2）表示2元域，只

27、有兩種元素0、1，且0、1滿足如下的運算規(guī)則：n0+0=0，0+1=1，1+0=1，1+1=0 （加法）n0 x0=0，0 x1=0，1x0=0，1x1=1。 （乘法） n例如：（1011000）的碼多項式為 ),.,(021cccCnni012211.)(cDcDcDcDCnnnni)2(GFci346DDDn左移一位n左移 位)()(102312)1(nnnnnaDaDaDaDA)(121ininininaaaaA)()(12211)(ininninniniaDaDaDaDAin若 是長度為n的循環(huán)碼組，則 在按模 進(jìn)行運算后，也是一個循環(huán)碼組，也就是 用 多項式除后所得之余式，即為所求的

28、碼組)(DA)(DADi)(DADi)(1012nnaaaaA2.5 循環(huán)碼循環(huán)碼1nD1nD2.5 循環(huán)碼循環(huán)碼n生成多項式n循環(huán)碼完全由其碼長n和生成多項式g（D）構(gòu)成n其中g(shù)（D）是一個能除盡Dn+1的r=n-k階多項式n階數(shù)低于n并能被g（D）除盡的一組碼多項式就構(gòu)成一個（n，k）循環(huán)碼n即階數(shù)小于或等于階數(shù)小于或等于n-1且能被且能被g（D）除盡的每個多項式）除盡的每個多項式都是循環(huán)碼的許用碼組都是循環(huán)碼的許用碼組 信息多項式為M(D),k 位，(k-1)次多項式 A(D)=M(D)g(D)2.5 循環(huán)碼循環(huán)碼n生成多項式（續(xù)）n例如，（7，4）循環(huán)碼的生成多項式n則階數(shù)低于n-1能

29、被g（D）除盡的多項式為n其中 ，i=0，1，2，3n假設(shè)n則對應(yīng)的循環(huán)碼多項式為n故對應(yīng)的循環(huán)碼組為（1111111） 1)(23DDDg)()(012233DgmDmDmDm1011)(0123mmmm1)() 1(23343563DDDDDDDDDgDD123456DDDDDD)2(GFmi2.5 循環(huán)碼循環(huán)碼n生成多項式的構(gòu)造n循環(huán)碼多項式表示及循環(huán)性質(zhì) n循環(huán)碼中任何碼組的循環(huán)移位還是許用碼組，可以表示成碼多項式的形式 n定理一：碼組 ，經(jīng)過移位i位，得到碼組 則可以證明： 即n證明： 利用多項式的長除法：可以得證 ),.,(021cccCnn).,.,(),.,(21011021i

30、nnnininnniccccccxxxC)() 1)()(DCDDQDCDini) 1mod()()(niiDDCDDC).()(02211cDcDcDDCDnnnniiiinninnDcDcDc02211.2.5 循環(huán)碼循環(huán)碼n生成多項式的構(gòu)造（續(xù)）n循環(huán)碼多項式表示及循環(huán)性質(zhì) n例：（7，4）循環(huán)碼（1000101）的碼多項式為 移位1位后變成 將它被 除，得到 因此，循環(huán)左移一位的余式為 其相對應(yīng)的碼組為（0001011），正好是（1000101）循環(huán)左移一位的結(jié)果 126 DDDDDDDD3726) 1(17D) 1() 1(3737DDDDDD13 DD2.5 循環(huán)碼循環(huán)碼n生成多項

31、式的構(gòu)造（續(xù)）n循環(huán)碼多項式的構(gòu)造n定理二：（n，k）循環(huán)碼的生成多項式g(D)一定是Dn+1的因式，即 反之，如果g(D)是一個n-k次多項式，且除盡Dn+1 ， 則此g(D)一定生成一個（n，k）循環(huán)碼 n證明：循環(huán)碼的碼組T（D）是g（D）的倍式，因此 而生成多項式g(D)本身也是一個碼組，該碼組的多項式次數(shù)為n-k次 由定理一，可以知道 也是循環(huán)碼組 而 所以， 即g（D）是Dn+1的因式n因式分解可以通過計算機(jī)分解的方式分解，也可以通過查表（已經(jīng)作好的因式分解表）得到)()(1DhDgDn)()()(DMDgDT)(DgDk)()(1)(1)(DgDMDDTDDgDnnk)()()(

32、)(1DgDhDgDMDDkn2.5 循環(huán)碼循環(huán)碼n生成多項式的構(gòu)造（續(xù)）n循環(huán)碼多項式的構(gòu)造n例， 因此，（7，4）循環(huán)碼的生成多項式可以選擇 或 而（7，3）循環(huán)碼的生成多項式可以選擇 或 n練習(xí)：請驗證以下結(jié)論練習(xí)：請驗證以下結(jié)論n（7，6）循環(huán)碼的生成多項式為D+1，實際上就是簡單的偶校驗碼n（7，1）循環(huán)碼的生成多項式為 ，實際上是7重重復(fù)碼 ) 1)(1)(1(13237DDDDDD123 DD13 DD) 1)(1(23DDD) 1)(1(3DDD) 1)(1(323DDDD2.5 循環(huán)碼循環(huán)碼n生成矩陣n根據(jù)n循環(huán)碼的碼組多項式是生成多項式g（D）的倍式n根據(jù)線性碼的生成矩陣的

33、特性，（n，k）碼的生成矩陣實際上可以由（n，k）碼中k個不相關(guān)的碼組構(gòu)成n可以挑選出k個循環(huán)碼組的碼多項式形成n非系統(tǒng)碼的生成矩陣n系統(tǒng)碼的生成矩陣2.5 循環(huán)碼循環(huán)碼n生成矩陣n非系統(tǒng)碼的生成矩陣n輸入信息碼元為 時， 相應(yīng)的循環(huán)碼組多項式為： 由上式得到的碼組不是系統(tǒng)碼)()()()(21DgDgDDgDDGkk).(021mmmkk)().,()(021DGmmmDTkk)().(02211DgmDmDmkkkk)()(DgDM2.5 循環(huán)碼循環(huán)碼n生成矩陣n系統(tǒng)碼的生成矩陣n系統(tǒng)碼定義：（系統(tǒng)碼定義：（n，k）系統(tǒng)碼的碼組中前k個比特是信息比特，后n-k個比特是監(jiān)督位n問題：已知生成

34、多項式g（D），如何構(gòu)造系統(tǒng)碼的生成矩陣？n 在系統(tǒng)碼中，碼組應(yīng)該具備如下的形式： n同時有n由上式可得 其中，r（D）的次數(shù)小于等于n-k-1n實際上上式表示了如何生成系統(tǒng)碼，即n將信息碼多項式升n-k次，然后以g（D）為模，求出余式r（D） )(.)(02211DrDmDmDmDTknnknk)()()().(02211DrDDMDrDmDmDmknknkkkk)(mod)()(DgDDMDrkn)()()(DgDMDT2.5 循環(huán)碼循環(huán)碼n生成矩陣n系統(tǒng)碼的生成矩陣n例： 已知（7，4）系統(tǒng)循環(huán)碼的生成多項式為 求生成矩陣n解：系統(tǒng)碼的生成矩陣形式肯定是 因此選擇信息多項式為 、1 將D

35、3提升n-k=3次，得到D6 ，求D6除以g（D）的余式得到 因此，系統(tǒng)生成矩陣為表示成矩陣形式，得到 1)(23DDDgQIkDDD、23)(mod26DgDDD)(mod15DgDD)(mod124DgDDD)(mod123DgDD111)(2324526DDDDDDDDDDDG1011000111010011000100110001G2.5 循環(huán)碼循環(huán)碼n監(jiān)督矩陣n由于g（D）能除盡Dn+1 ，即 （1式）n這里， 稱為生成多項式 n h(D)稱為監(jiān)督多項式 n由（1式）知道， )()(1DhDgDn01.)(gDgDgDgknkn01.)(hDhDhDhkk0.0.0.001111102110110021120011000kknkknknknknknknknknkhghghghghghghghghghghghghgghgh2.5 循