第十章-差錯(cuò)控制編碼學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1第十章第十章-差錯(cuò)控制編碼差錯(cuò)控制編碼(bin m)第一頁，共67頁。2022-4-14210.1 差錯(cuò)控制編碼(bin m)的基本原理發(fā)生誤碼原因：系統(tǒng)特性不理想（乘性干擾），數(shù)字信號(hào)通過系統(tǒng)時(shí) 產(chǎn)生(chnshng)波形失真，在接收端判決時(shí)會(huì)產(chǎn)生(chnshng)判決錯(cuò)誤。信道中的噪聲（加性干擾），這種干擾隨機(jī)地與信號(hào) 疊加，使信號(hào)波形產(chǎn)生(chnshng)失真，引起判決錯(cuò)誤。 解決辦法：（1）適當(dāng)增加發(fā)送信號(hào)功率。 (2) 選擇抗噪聲性能好的調(diào)制解調(diào)方式。 (3) 采用(ciyng)最佳接收 。（4）采用(ciyng)差錯(cuò)控制編碼。 第1頁/共67頁第二頁，共67頁。2022-4

2、-14310.1 差錯(cuò)控制編碼(bin m)的基本原理信源編碼目的：提高通信系統(tǒng)(xtng)的有效性。差錯(cuò)控制編碼（信道編碼、抗干擾編碼或糾錯(cuò)編碼）目的：提高通信的可靠性。 差錯(cuò)控制編碼方法：通過人為地加入多余度，使信 號(hào)在一定的干擾條件(tiojin)下，具有 檢測或糾正錯(cuò)碼的能力。第2頁/共67頁第三頁，共67頁。2022-4-14410.1 差錯(cuò)控制編碼(bin m)的基本原理信道分類：隨機(jī)(su j)信道、突發(fā)信道、混合信道。 （1 ） 隨機(jī)信道：錯(cuò)碼出現(xiàn)互不相關(guān)、統(tǒng)計(jì)獨(dú)立。 如：高斯白噪聲引起的錯(cuò)碼。（2）突發(fā)信道：錯(cuò)碼的出現(xiàn)前后相關(guān)。錯(cuò)碼出現(xiàn)時(shí)， 在短時(shí)間內(nèi)有一連串的錯(cuò)碼，而該時(shí)間

3、過后又 有較長的時(shí)間無錯(cuò)碼。如：隨機(jī)的強(qiáng)突發(fā)脈沖 干擾引起的錯(cuò)碼。（3）混合(hnh)信道：產(chǎn)生的錯(cuò)碼既有隨機(jī)錯(cuò)碼又有突發(fā) 錯(cuò)碼。第3頁/共67頁第四頁，共67頁。2022-4-14510.1 差錯(cuò)控制編碼(bin m)的基本原理常用(chn yn)的差錯(cuò)控制方式1. ARQ(Automatic Repeat Request)方式(自動(dòng)(zdng)請求重發(fā)或檢錯(cuò)重發(fā)) 發(fā)端發(fā)送出可以發(fā)現(xiàn)錯(cuò)誤的碼字。經(jīng)過傳輸?shù)浇邮斩俗g碼后，如果沒有發(fā)現(xiàn)錯(cuò)誤，則輸出。如果發(fā)現(xiàn)錯(cuò)誤，則自動(dòng)請求發(fā)端重發(fā)，直到正確接收到碼字為止。第4頁/共67頁第五頁，共67頁。2022-4-14610.1 差錯(cuò)控制編碼(bin m)

4、的基本原理ARQ系統(tǒng)(xtng)組成特點(diǎn)：設(shè)備簡單(jindn)、雙向信道、傳輸效率低。第5頁/共67頁第六頁，共67頁。2022-4-14710.1 差錯(cuò)控制編碼(bin m)的基本原理2.反饋(fnku)校驗(yàn)方式 接收端收到碼字后，立即將接收到的碼字返回發(fā)送端。發(fā)送端將返回的碼字與發(fā)端緩沖存儲(chǔ)器中相應(yīng)的碼字比較，若發(fā)現(xiàn)與發(fā)送碼不同，即認(rèn)為(rnwi)產(chǎn)生了錯(cuò)誤，就重發(fā)上一次的碼字。 特點(diǎn)：設(shè)備簡單、雙向信道、傳輸效率低。第6頁/共67頁第七頁，共67頁。2022-4-14810.1 差錯(cuò)控制編碼(bin m)的基本原理 發(fā)送端發(fā)出的碼字不僅能夠發(fā)現(xiàn)錯(cuò)誤，而且(r qi)能夠糾正錯(cuò)誤。在接收

5、端譯碼后，若沒有錯(cuò)誤則直接輸出。若有錯(cuò)誤，則在接收端自動(dòng)糾正后，再輸出。 特點(diǎn)：不需要反向信道、實(shí)時(shí)性好、傳輸效率高。 但糾錯(cuò)編譯碼方法復(fù)雜。第7頁/共67頁第八頁，共67頁。2022-4-14910.1 差錯(cuò)控制編碼(bin m)的基本原理 將ARQ方式和前向糾錯(cuò)方式結(jié)合使用。傳輸錯(cuò)碼較少時(shí)，采用前向糾錯(cuò)方式，自動(dòng)(zdng)糾正錯(cuò)碼。在錯(cuò)碼較多時(shí)，采用ARQ方式自動(dòng)(zdng)請求重發(fā)。 4.HEC（Hybrid Error Control,混合糾錯(cuò)(ji cu)）方式第8頁/共67頁第九頁，共67頁。2022-4-141010.1 差錯(cuò)控制編碼(bin m)的基本原理 在有擾信道中只要信

6、息的傳輸速率R小于信道容量C，總可以找一種編碼方法，使信息以任意(rny)小的差錯(cuò)概率通過信道傳送到接收端，即誤碼率Pe可以任意(rny)小，而且傳輸速率R可以接近信道容量C。但若R C，在傳輸過程中必定帶來不可糾正錯(cuò)誤，不存在使差錯(cuò)概率任意(rny)小的編碼。 香農(nóng)有擾信道編碼定理(dngl)： 香農(nóng)有擾信道的編碼定理本身并未給出具體的糾錯(cuò)編碼方法，但它為信道編碼奠定了理論基礎(chǔ)。從理論上指出了信道編碼的發(fā)展方向。第9頁/共67頁第十頁，共67頁。2022-4-141110.1 差錯(cuò)控制編碼(bin m)的基本原理誤碼率： 式中，n為編碼的碼字長度(chngd)(簡稱碼長)； E(R)為誤碼指

7、數(shù)。第10頁/共67頁第十一頁，共67頁。2022-4-141210.1 差錯(cuò)控制編碼(bin m)的基本原理減小誤碼率Pe的兩種途徑(tjng)：（2）在C及 R一定的情況(qngkung)下，增加n可以使Pe指數(shù)減小。（1）n 及 R一定時(shí)，增加信道容量C。由圖可見，E(R) 隨C的增加而增大。由信道容量公式知， 增加C， 可通過增加S和B來實(shí)現(xiàn)；第11頁/共67頁第十二頁，共67頁。2022-4-141310.1 差錯(cuò)控制編碼(bin m)的基本原理重復(fù)編碼的例子：天氣預(yù)報(bào)消息(xio xi)發(fā)布晴 雨 糾檢錯(cuò)能力(nngl) 第一種編碼方法許用碼、禁用碼、最大似然準(zhǔn)則糾檢錯(cuò)能力 第二種

8、編碼方法可檢1位錯(cuò)（01、10）、糾錯(cuò)能力 第三種編碼方法可檢2位錯(cuò)、糾1位錯(cuò)（001、010、100 000 011、101、110 111 ）第12頁/共67頁第十三頁，共67頁。2022-4-141410.1 差錯(cuò)控制編碼(bin m)的基本原理碼間距離d 及檢錯(cuò)糾錯(cuò)(ji cu)能力碼字：由信息位和監(jiān)督(jind)位組成的一組碼元。 用C = ( cn-1 cn-2 c0 )表示。 碼元： 組成碼字的元素，用Ci表示。碼長：碼字中碼元的個(gè)數(shù)，用n表示。（許用碼、禁用碼）碼組：由多個(gè)許用碼組成的一組碼字。 第13頁/共67頁第十四頁，共67頁。2022-4-1415碼間距離(jl)d（c

9、ode distances）10,()nijipjppd c ccc10.1 差錯(cuò)控制編碼(bin m)的基本原理第14頁/共67頁第十五頁，共67頁。2022-4-1416碼間距離的幾何(j h)意義10.1 差錯(cuò)控制編碼(bin m)的基本原理最小碼間距離(jl)d0：碼組中各碼字之間最小的碼距。第15頁/共67頁第十六頁，共67頁。2022-4-141710.1 差錯(cuò)控制編碼(bin m)的基本原理最小碼間距離(jl)d0與檢錯(cuò)糾錯(cuò)能力的關(guān)系第16頁/共67頁第十七頁，共67頁。2022-4-141810.1 差錯(cuò)控制編碼(bin m)的基本原理第17頁/共67頁第十八頁，共67頁。20

10、22-4-141910.1 差錯(cuò)控制編碼(bin m)的基本原理第18頁/共67頁第十九頁，共67頁。2022-4-1420差錯(cuò)控制編碼(bin m)的效果 在碼長為n的碼字中剛好發(fā)生(fshng)r個(gè)錯(cuò)誤的概率為： 1n rrrnnP rC PP10.1 差錯(cuò)控制編碼(bin m)的基本原理P7(1)710-3 P7(2)2.110-5 P7(3)3.510-8當(dāng)n =7，P=10-3 時(shí)，有：第19頁/共67頁第二十頁，共67頁。2022-4-1421糾錯(cuò)(ji cu)編碼的分類 10.1 差錯(cuò)控制編碼(bin m)的基本原理第20頁/共67頁第二十一頁，共67頁。2022-4-14221

11、0.1 差錯(cuò)控制編碼(bin m)的基本原理knrnn編碼(bin m)效率K：碼字的信息(xnx)碼元個(gè)數(shù)r：監(jiān)督碼元個(gè)數(shù)n: 碼元總的個(gè)數(shù)（總碼長）nkr第21頁/共67頁第二十二頁，共67頁。2022-4-142310.2常用的簡單(jindn)編碼1.奇偶(q u)監(jiān)督碼2.二維奇偶(q u)監(jiān)督碼3.恒比碼（等重碼）第22頁/共67頁第二十三頁，共67頁。2022-4-142410.2常用(chn yn)的簡單編碼廣泛應(yīng)用于計(jì)算機(jī)數(shù)據(jù)傳輸中。偶監(jiān)督(jind)碼：給信息位后增加一位監(jiān)督(jind)位，使碼字中“1” 的數(shù)目為偶數(shù)。編碼規(guī)則：在每個(gè)分組的信息位后增加監(jiān)督位，無論 信息位

12、有多少(dusho)位，監(jiān)督位只有一位。上式為偶監(jiān)督碼的監(jiān)督關(guān)系，也稱為校驗(yàn)方程。檢測能力：檢測奇數(shù)個(gè)錯(cuò)。12100nnCCCC1.奇偶監(jiān)督碼（奇偶校驗(yàn)碼）第23頁/共67頁第二十四頁，共67頁。2022-4-142510.2常用的簡單(jindn)編碼奇監(jiān)督碼：給信息位后增加一位監(jiān)督位，使碼字 中“1”的數(shù)目(shm)為奇數(shù)。其校驗(yàn)方程為 奇偶監(jiān)督碼的編碼效率較高，尤其是當(dāng)碼長 n 較大時(shí)這一特點(diǎn)更為明顯。121010nnCCCC 第24頁/共67頁第二十五頁，共67頁。2022-4-142610.2常用的簡單(jindn)編碼2.二維奇偶(q u)監(jiān)督碼（方陣碼、行列監(jiān)督碼或水平垂直奇偶(

13、q u)監(jiān)督碼）編碼方法：把m 個(gè)信息碼字排列成一個(gè)方陣，每個(gè)碼字構(gòu)成方陣的一行，在每一行的最后按奇偶(q u)監(jiān)督規(guī)則增加一位水平監(jiān)督位，再按列的方向每列增加一位垂直監(jiān)督位（包括行監(jiān)督位的列）第25頁/共67頁第二十六頁，共67頁。2022-4-1427可以檢測每行的奇數(shù)個(gè)錯(cuò)和每列的奇數(shù)個(gè)錯(cuò)；行列交叉可以檢測每行或每列的偶數(shù)個(gè)錯(cuò)；但 當(dāng)發(fā)生的錯(cuò)誤為剛好(gngho)構(gòu)成矩形的四個(gè)錯(cuò)碼時(shí)， 則不能檢測出錯(cuò)誤。檢測(jin c)能力：10.2常用(chn yn)的簡單編碼 只有一行出現(xiàn)奇數(shù)個(gè)錯(cuò)碼時(shí)，按行檢測可以判斷出錯(cuò)在那一行，按列檢測可以確定該行的那一列發(fā)生了錯(cuò)誤，行列交叉可以判斷錯(cuò)誤的位置，

14、即可糾錯(cuò)。此外，此種編碼的效率較高。糾錯(cuò)能力：第26頁/共67頁第二十七頁，共67頁。2022-4-14283.恒比碼（等重碼(zhn m)） 每個(gè)許用碼含有相同數(shù)目的“1”。碼字中“1”與“0”的個(gè)數(shù)之比是恒定的，故稱恒比碼。碼字中“1”的個(gè)數(shù)稱為(chn wi)碼重，因此恒比碼又稱等重碼。 對于某種特定(tdng)的恒比碼，當(dāng)碼長確定后，其“1”的個(gè)數(shù)就確定了。所以在檢測中只要計(jì)算“1”的個(gè)數(shù)就可以確定是否發(fā)生錯(cuò)誤。恒比碼多用于電傳機(jī)中。 我國電傳機(jī)傳輸漢字采用的是“5中取3” 恒比碼，其碼長為5，碼字中“1”的個(gè)數(shù)為3。這種碼我國稱為保護(hù)電碼。碼長為5的二進(jìn)制數(shù)共有32種組合，選擇其中含

15、有3個(gè)“1”的組合作為許用碼，為10個(gè)。10.2常用的簡單編碼第27頁/共67頁第二十八頁，共67頁。2022-4-1429 我國的保護(hù)電碼(dinm)與國際電碼(dinm)阿拉伯阿拉伯?dāng)?shù)字?jǐn)?shù)字保護(hù)電保護(hù)電碼碼國際電國際電碼碼阿拉伯阿拉伯?dāng)?shù)字?jǐn)?shù)字保護(hù)電保護(hù)電碼碼國際電國際電碼碼00110101101500111000011010111110161010110101211001110017111001110031011010000801110011004110100101091001100011 10.2常用(chn yn)的簡單編碼第28頁/共67頁第二十九頁，共67頁。2022-4-1430

16、10.3 線性分組碼一、線性分組碼概念(ginin) 線性分組碼是指信息位和監(jiān)督(jind)位滿足一組線性方程，即其編碼規(guī)則可用一組線性方程來描述的分組碼。信息(xnx)位k信息位k 監(jiān)督位r記為（n, k）nkrn: 碼元總的個(gè)數(shù)（總碼長）第29頁/共67頁第三十頁，共67頁。2022-4-143110.3 線性分組碼系統(tǒng)碼：碼字的前一部分是連續(xù)k 位信息碼元，后一部 分是連續(xù)r 位監(jiān)督碼元，具有這種結(jié)構(gòu)的線性 分組碼稱為(chn wi)系統(tǒng)碼。否則稱為(chn wi)非系統(tǒng)碼。 糾錯(cuò)(ji cu)原理n 位長的二進(jìn)制碼共有(n yu) 碼字。2nk 位長的二進(jìn)制碼共有 碼字, 故 個(gè)信息段

17、僅構(gòu)成 個(gè)n 位長的碼字，稱為許用碼字而其他 個(gè)碼字為禁用碼字，當(dāng)出現(xiàn)禁用碼字時(shí)就可以發(fā)現(xiàn)或糾正錯(cuò)誤。2k2k2k22nk第30頁/共67頁第三十一頁，共67頁。2022-4-143210.3 線性分組碼二、線性分組碼的一致檢驗(yàn)(jinyn)（監(jiān)督矩陣）矩陣HH矩陣是用來(yn li)說明監(jiān)督碼元與信息碼元之間關(guān)系的矩陣。以（7，3）碼 ( k=3, r =4, n =7) 為例：碼字矢量(shling) C= c6c5c4c3c2c1c0 信息碼元： c6c5c4 監(jiān)督碼元 ：c3c2c1c0監(jiān)督方程為：3642654165054ccccccccccccc64365426515400000c

18、cccccccccccc第31頁/共67頁第三十二頁，共67頁。2022-4-143310.3 線性分組碼65432101 0 1 1 0 0 001 1 1 0 1 0 001 1 0 0 0 1 000 1 1 0 0 0 10ccccccc 4 7 ()rn7 14 3 ()Pr k444()Irr將上方程(fngchng)系數(shù)寫為矩陣形式第32頁/共67頁第三十三頁，共67頁。2022-4-143410.3 線性分組碼1 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1令 H=稱H為線性分組碼的一致檢驗(yàn)(jinyn)矩陣（監(jiān)督矩陣）。

19、H=P I4 0TTHC 0TCH第33頁/共67頁第三十四頁，共67頁。2022-4-143510.3 線性分組碼（1）H是 階矩陣，即行數(shù)為監(jiān)督碼元個(gè)數(shù)， 列數(shù)為碼長。 H中每行元素(yun s)表明監(jiān)督方程 中線性相關(guān)的碼元系數(shù)。故若H已知，則碼 元之間的監(jiān)督關(guān)系唯一確定。()rn（2）H=P I4，即H由兩部分組成，前半部稱 為P矩陣 ，后 半部稱為(chn wi)I矩陣 。 此時(shí)，稱 H為典型矩陣，只有系統(tǒng)碼才具有。()rk()rr（3）H是接收端檢錯(cuò)的依據(jù)。 0TRH第34頁/共67頁第三十五頁，共67頁。2022-4-143610.3 線性分組碼三、線性分組碼的生成(shn ch

20、n)矩陣GG矩陣是在給定信息位的條件下，如何(rh)生成碼字的矩陣。仍以（7，3）碼 ( k=3, r =4, n =7) 為例：碼字矢量(shling) C= c6c5c4c3c2c1c0 信息碼元： c6c5c4 ；監(jiān)督碼元 ：c3c2c1c0在監(jiān)督方程基礎(chǔ)上，加上信息碼元方程。3642654165054ccccccccccccc監(jiān)督方程第35頁/共67頁第三十六頁，共67頁。2022-4-143710.3 線性分組碼3642654165054ccccccccccccc6655443642654165054ccccccccccccccccccc 6541 0 00 1 00 0 11 0

21、11 1 11 1 00 11TccCc 第36頁/共67頁第三十七頁，共67頁。2022-4-143810.3 線性分組碼 6541 0 00 1 00 0 11 0 11 1 11 1 00 11TccCc 6 5 41 0 0 1 11 00 1 0 0 11 10 0 1 1 10 1c c cC生成(shn chn)矩陣G碼字矩陣(j zhn) 6 5 4c c cGC第37頁/共67頁第三十八頁，共67頁。2022-4-143910.3 線性分組碼 1 0 0 1 11 00 1 0 0 11 10 0 1 1 10 1kGIQ生成(shn chn)矩陣3 7 ()kn3 3 ()

22、kIk k3 4 ()Qk r第38頁/共67頁第三十九頁，共67頁。2022-4-144010.3 線性分組碼（1）G是 階矩陣，即行數(shù)為信息碼元個(gè)數(shù)， 列數(shù)為碼長。 故若G給定，則在已知信息碼 元的情況(qngkung)下，就可得到碼字（生成矩陣）。()kn（2）G=IK Q為標(biāo)準(zhǔn)生成矩陣，G中每行是互相(h xing) 獨(dú)立的（線性不相關(guān)）。實(shí)際上，G中每行就是 一個(gè)許用碼字。推論：由K互相獨(dú)立的碼字可構(gòu)成生成矩陣。第39頁/共67頁第四十頁，共67頁。2022-4-144110.3 線性分組碼（3）G與H的 關(guān)系(gun x)G=IK QH=P Ir TQP TPQ 1 0 11 1

23、11 1 00 1 1P 1 1 1 00 1 1 11 1 0 1Q第40頁/共67頁第四十一頁，共67頁。2022-4-144210.3 線性分組碼（4）對偶(du u)碼將一碼組（A）中的H當(dāng)作(dn zu)另一碼組（B）中的G，或反之，則稱B為A的對偶碼。 7,37,4HG 7,37,4GH則（7，4）為（7，3）的對偶碼。（5）封閉性 線性分組碼組中，任意兩個(gè)碼字之和仍是此碼組中的一個(gè)碼字。第41頁/共67頁第四十二頁，共67頁。2022-4-144310.3 線性分組碼四、線性分組碼的譯碼及伴隨(bn su)式1.譯碼譯碼是判斷(pndun)接收碼字是否為許用碼，即根據(jù) 0TCH判

24、斷接收碼字 是否(sh fu)滿足 120,nnRrrr 0TRH定義 為錯(cuò)誤圖樣， ECR 0E 當(dāng) 時(shí)，無誤碼。第42頁/共67頁第四十三頁，共67頁。2022-4-144410.3 線性分組碼 110, ,nEee e當(dāng) 時(shí)，認(rèn)為(rnwi)第i 位發(fā)生了誤碼。1ie RCE 0TRH將 代入 中，得： 1TTTrCHEHEHS稱 為伴隨(bn su)式，又稱校驗(yàn)子。 110, ,rSss s 10,0nE 10,0rS當(dāng) 時(shí)， 無錯(cuò)誤(cuw)出現(xiàn)。第43頁/共67頁第四十四頁，共67頁。2022-4-144510.3 線性分組碼21r當(dāng) 時(shí)，認(rèn)為(rnwi)第i 位發(fā)生了誤碼。1ie

25、 由 伴隨(bn su)式可檢測 個(gè)錯(cuò)誤。 110, ,rSss s此時(shí)(c sh)， 為 中的第i列（從右起），故可用 的列來表示誤碼位置。H 1TrSEHH第44頁/共67頁第四十五頁，共67頁。2022-4-144610.3 線性分組碼21r當(dāng) 時(shí)，認(rèn)為(rnwi)第i 位發(fā)生了誤碼。1ie 由 伴隨式可檢測(jin c) 個(gè)錯(cuò)誤。 110, ,rSss s要糾正小于或等于(dngy)t 個(gè)錯(cuò)，必須滿足此時(shí)， 為 中的第i列（從右起），故可用 的列來表示誤碼位置。H 1TrSEHH1221rtnnnCCC 02triniC或第45頁/共67頁第四十六頁，共67頁。2022-4-14471

26、0.3 線性分組碼編碼(bin m)效率 漢明碼是一種可以(ky)糾正單個(gè)隨機(jī)錯(cuò)誤的線性分組碼。它是一種完備碼，編碼效率很高。漢明碼21rn ,21 , 21rrn kr 21112121rrrknrrrrnnn第46頁/共67頁第四十七頁，共67頁。2022-4-144810.3 線性分組碼例：7 ,21 127,120127,120rrnknr 457%7kn3,217,47, 4rrnknr 12094%127kn第47頁/共67頁第四十八頁，共67頁。2022-4-144910.3 線性分組碼（4）編碼(bin m)效率高。 （1）漢明碼長漢明碼特點(diǎn)(tdin)21,3rnr（2）信息

27、(xnx)位21rknrr （3）最小碼距 ，糾錯(cuò)能力為 。03d 1t n第48頁/共67頁第四十九頁，共67頁。2022-4-145010.4 循環(huán)碼一、 循環(huán)碼的基本概念及碼多項(xiàng)式定義(dngy)：具有循環(huán)性的線性分組碼。循環(huán)(xnhun)性：碼組中任一許用碼字（全“0”碼除外）循環(huán)(xnhun)左移 （或循環(huán)(xnhun)右移）后所得到的碼字仍為該循環(huán)(xnhun)碼組 中的另一許用碼字。 1210,nnCccc c121023010121,nnnnnnccc cccc cc cc c第49頁/共67頁第五十頁，共67頁。2022-4-145110.4 循環(huán)碼一種(y zhn)（7，3

28、）循環(huán)碼序序號(hào)號(hào)移移位位次次數(shù)數(shù)信信 息息 位位監(jiān)監(jiān) 督督 位位序序號(hào)號(hào)移移位位次次數(shù)數(shù)信信 息息 位位監(jiān)監(jiān) 督督 位位000000004610011101 10 000111015410100112 25 501001116311010013 31 10111010721110100第50頁/共67頁第五十一頁，共67頁。2022-4-145210.4 循環(huán)碼碼多項(xiàng)式：把循環(huán)碼中的碼字用多項(xiàng)式來表示(biosh)，碼字中各 碼元的取值作為碼多項(xiàng)式的系數(shù)。 1210,nnCccc c 121210nnnnT xcxcxc x c 6321001110T xxxxx7,3例：對 碼第51頁/共6

29、7頁第五十二頁，共67頁。2022-4-145310.4 循環(huán)碼碼多項(xiàng)式運(yùn)算(yn sun)： 4321T xxxx定理定理 若若T (x )是長為是長為n 的循環(huán)碼中某個(gè)的循環(huán)碼中某個(gè)(mu )許用碼字許用碼字的碼的碼 多項(xiàng)式，則多項(xiàng)式，則xi T(x) 在按模在按模 xn +1運(yùn)算下，也運(yùn)算下，也是該是該 循環(huán)碼中一個(gè)許用碼字的碼多項(xiàng)式。循環(huán)碼中一個(gè)許用碼字的碼多項(xiàng)式。 ( )( )( )r xF xQ xN xN x ( )( )F xQ x N xr x如：（7，3）循環(huán)碼中許用碼字0011101的碼多項(xiàng)式為則 3653771111x T xxxxxx （模 運(yùn)算(yn sun)）(

30、)N x第52頁/共67頁第五十三頁，共67頁。2022-4-145410.4 循環(huán)碼71x 36531x T xxxx（模 運(yùn)算(yn sun)） 對應(yīng)(duyng)的碼字為1101001，它是該（7，3）循環(huán)碼中的一另一許用碼字，它是循環(huán)碼0011101左移3次后形成的。1356xxx第53頁/共67頁第五十四頁，共67頁。2022-4-145510.4 循環(huán)碼定理定理 在循環(huán)碼（在循環(huán)碼（n，k）中，）中，n-k 次冪的碼多項(xiàng)式有一次冪的碼多項(xiàng)式有一 個(gè)，且僅有一個(gè)，用個(gè)，且僅有一個(gè)，用g(x)表示表示(biosh)。稱這唯。稱這唯一的一的n-k次次 多項(xiàng)式多項(xiàng)式g(x)為循環(huán)碼的生成多

31、項(xiàng)式。為循環(huán)碼的生成多項(xiàng)式。g(x)的常數(shù)的常數(shù)項(xiàng)項(xiàng) 不為零。不為零。生成(shn chn)多項(xiàng)式及生成(shn chn)矩陣 一旦g(x)確定，則該（n，k）循環(huán)碼就被確定了。g(x)是循環(huán)碼中冪次最低的碼多項(xiàng)式。由它左移就可產(chǎn)生其它碼多項(xiàng)式。比如xg(x)、x2g(x)、x3g(x)等。用k個(gè)互相獨(dú)立的碼多項(xiàng)式g(x)、xg(x)、x2g(x) xk-1g(x)可以(ky)構(gòu)造出循環(huán)碼的生成矩陣G(x)為第54頁/共67頁第五十五頁，共67頁。2022-4-145610.4 循環(huán)碼 121kkxg xxg xG xx g xg x生成(shn chn)矩陣第55頁/共67頁第五十六頁，共6

32、7頁。2022-4-145710.4 循環(huán)碼例如，（7，3）循環(huán)碼中最高次冪為n-k次的碼字為0010111， 其生成(shn chn)多項(xiàng)式g(x)= x4+ x2+x+1。則利用上式可得其 生成(shn chn)矩陣G(x)為 21101110001011100010111x g xG xx g xG xg x 上式不符合典型生成矩陣的形式，所以它不是典型生成矩陣，由它編出的碼字不是系統(tǒng)碼。但是對此矩陣作線性變化(binhu)可以變換成典型生成矩陣的形式。第56頁/共67頁第五十七頁，共67頁。2022-4-145810.4 循環(huán)碼例如，（7，3）循環(huán)碼中最高次冪為n-k次的碼字為0010

33、111， 其生成(shn chn)多項(xiàng)式g(x)= x4+ x2+x+1。則利用上式可得其 生成(shn chn)矩陣G(x)為 21101110001011100010111x g xG xx g xG xg x 上式不符合典型生成矩陣(j zhn)的形式，所以它不是典型生成矩陣(j zhn)，由它編出的碼字不是系統(tǒng)碼。但是對此矩陣(j zhn)作線性變化可以變換成典型生成矩陣(j zhn)的形式。第57頁/共67頁第五十八頁，共67頁。2022-4-145910.4 循環(huán)碼定理定理(dngl) 循環(huán)碼（循環(huán)碼（n，k）的生成多項(xiàng)式）的生成多項(xiàng)式g(x)是是xn +1的一個(gè)因式。的一個(gè)因式。

34、 產(chǎn)生g(x)的方法(fngf)：對（xn+1）進(jìn)行因式分解，從中找出一個(gè)最 高次冪為（n -k）次且常數(shù)項(xiàng)不為零的因式， 作為生成多項(xiàng)式g(x)。例如(lr)：對于（7，3）循環(huán)碼，g(x)的最高次冪為4?？蓮模▁7+1） 中分解得到g(x)。x7+1=（x+1）（x3+x2+1）（x3+x+1）生成多項(xiàng)式可選為g1(x)=（x+1）（x3+x2+1）=x4+x2+x+1或g2(x)=（x+1）（x3+x+1）=x4+ x3+x2+第58頁/共67頁第五十九頁，共67頁。2022-4-146010.4 循環(huán)碼循環(huán)碼的編碼(bin m)及解碼1. 編碼(bin m)設(shè)信息(xnx)碼多項(xiàng)式為m(x) m(x)=mk-1 x k-1+ mk-2 x k-2+ m1 x+ m0 m(x)的最高次冪為k-1。 將m(x)左移n-k位成為xn-km(x)，其最高次冪為n-1。xn-km(x)的前一部分為連續(xù)k位信息碼，后一部分為r=n-k位的“0”，r正好是監(jiān)督碼的位數(shù)。所以在它的后一