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

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

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

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

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

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

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

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

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

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

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

12、個比特一組的碼字（碼組），記為（n，k）碼n由于輸入有 2k種組合，因此（n，k）碼應該有2k個碼字n碼重、碼距n碼重：碼字中1的個數。如碼字11000的碼重為2n碼距：碼字C1與碼字C2之間不同的比特數（又稱漢明距） 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奇偶監督碼（奇偶校驗）n設奇偶監督碼的碼字表示為： n則偶校驗碼： （即偶數個1） 奇校驗碼： （即奇數個1）n可見這種碼的最小碼距為2，只能檢1個錯 ),.,(021aaann0.021aaann1.021aaann 奇偶監督碼的編碼可以用軟件實現，也可用硬奇偶監督碼的編碼可以用軟件實現，也可用硬

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

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

16、310110801110411010910011500111001101 2.3 常用的簡單編碼常用的簡單編碼 nISBN國際統一圖書編號n國際圖書的發行中，用編碼的方式來防止書號在通信過程中發生錯誤 n如通信原理的書號是ISBN 7-118-01429-Xn其中第一位數字“7”表示“中國”，“118”表示出版社，“01429”表示書名編號，最后一位“X”表示校驗位（它是羅馬數字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性質n基本原理n校驗矩陣（監督矩陣）n生成矩陣n校正子（伴隨式）n漢明碼2.4 線性分組碼線性分組碼n定義：n將信息碼分組，為每組信息位附加若干監督位，且信息位和監督位間的關系可由線性方程組表示的編碼n即可用線性方程組表述碼的規律性的分組碼 n線性分組碼（n，k）的性質n許用碼字（組）為2k個n定義線性分組碼的加法為模2加，乘法為二進制乘法。即有n1+1=0、1+0=1、0+1=1、0+0=0 n1x1 = 1, 1x 0 =0, 0 x0 =0, 0 x1 =0n且碼字與碼字的運算是各相應比特位上符合上

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

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

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

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

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

23、110100010101000110010111000111010001010100011001011100013456345634560123456GGAaaaaGaaaaaaaaaaaaaaa或2.4 線性分組碼線性分組碼n生成矩陣（續）n典型生成矩陣GnGIk Q n其中，其中，QPT為為kr階矩陣，階矩陣，Ik為為kk階單位方陣階單位方陣nPQTn由典型生成矩陣G可以得到系統碼n各行線性無關n非典型形式生成矩陣可以經過行運算化為典型形式2.4 線性分組碼線性分組碼n校正子（伴隨式）n發送碼組A在傳輸過程中可能發生誤碼n設接收到的碼組為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間有確定的關系iiiiab, 1ab, 0當當ie2.4 線性分組碼線性分組碼n漢明碼n上述方法構造的糾正單個錯誤的線性分組碼n特點n碼長：n2m1n信息碼位：k=2m-m-1n監督碼位：r=n-k=mn最小碼距：d=3n糾錯能力：t=12.5 循環碼循環碼n概念、性質和多項式表示n生成多項式n生成矩陣與監督矩陣n編碼器2.5 循環碼循環碼n概念及性質n線性分組碼中最重要的一種子類，比較成熟n特點n代數結構清晰：有嚴格的代數理論基礎n性能較好：可糾隨機錯誤和突發錯誤n編譯碼

25、簡單：特殊的代數性質有助于按照要求的糾錯能力構造，并且簡化譯碼算法n易于實現：很容易用帶反饋的移位寄存器實現n目前的計算機糾錯系統中廣泛使用的線性分組碼2.5 循環碼循環碼n概念及性質（續）n例：設（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的碼組，具有這種特性的線性分組碼稱為循環碼循環碼 1101000011010011100101010001G100101101011100010111H2.5 循環碼循環碼n概念及性質（續）n循環碼的性質：n封閉性n任何許用碼組的線性和還是許用碼組。由此性質可以得到：線性碼都包含全零碼線性碼都包含全零碼n最小碼重就是最小碼距最小碼重就是最小碼距n循環性n 任何許用的碼組循環移位后的碼組還是許用碼組 2.5 循環碼循環碼n概念及性質（續）n多項式表示：n目的：用代數理論的方法研究循環碼的特性n定義：碼 的碼多項式如下 n其中，D為實變量、其冪次代表移位次數， nGF（2）表示2元域，只

27、有兩種元素0、1，且0、1滿足如下的運算規則：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的循環碼組，則 在按模 進行運算后，也是一個循環碼組，也就是 用 多項式除后所得之余式，即為所求的

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

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

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

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

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

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

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

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