通信原理差錯(cuò)控制編碼

1、1聯(lián)合戰(zhàn)術(shù)通信教研組張偉明理 工 大 學(xué) 通 信 工 程 學(xué) 院理 工 大 學(xué) 通 信 工 程 學(xué) 院2第第7 7章章 差錯(cuò)控制編碼差錯(cuò)控制編碼7.1 概述7.2 糾錯(cuò)編碼的基本原理糾錯(cuò)編碼的基本原理7.3 常用的簡(jiǎn)單編碼7.4 線性分組碼線性分組碼7.5 循環(huán)碼7.6 卷積碼7.7 偽隨機(jī)序列 7.8 現(xiàn)代編碼技術(shù) 37-1 概述n信源編碼：為了提高數(shù)字信號(hào)的有效性而采取的編碼，又稱有效性編碼；n信道編碼：為了提高數(shù)字通信的可靠性而采取的編碼，又稱可靠性編碼、抗干擾編碼、糾錯(cuò)編碼或差錯(cuò)控制編碼。n信道編碼原理信道編碼原理：在原始數(shù)字信號(hào)中加入帶有規(guī)律性的碼元，：在原始數(shù)字信號(hào)中加入帶有規(guī)律性

2、的碼元，信道譯碼器利用這些規(guī)律性來鑒別是否發(fā)生錯(cuò)誤，或進(jìn)行信道譯碼器利用這些規(guī)律性來鑒別是否發(fā)生錯(cuò)誤，或進(jìn)行錯(cuò)誤糾正。錯(cuò)誤糾正。47-1 概述編碼的本質(zhì)本質(zhì)：增加冗余度冗余度，犧牲有效性以提高可靠性。編碼的方法方法：對(duì)原信息進(jìn)行變換，加入附加信息附加信息(即監(jiān)督碼)。例例: (4,1)重復(fù)重復(fù)碼碼 0: 00001: 11115隨機(jī)錯(cuò)誤：零星分布的錯(cuò)誤突發(fā)錯(cuò)誤：集中出現(xiàn)的錯(cuò)誤突發(fā)信道：以突發(fā)錯(cuò)誤為主隨機(jī)信道：以隨機(jī)錯(cuò)誤為主混合信道：兩種錯(cuò)誤均較明顯對(duì)錯(cuò)誤的處理方式：檢錯(cuò)、糾錯(cuò)、糾檢結(jié)合一、差錯(cuò)及信道分類一、差錯(cuò)及信道分類6發(fā)端收端前向糾錯(cuò)FEC糾錯(cuò)碼發(fā)端收端檢錯(cuò)重發(fā)ARQ(Automatic

3、Repeat reQuest)檢錯(cuò)碼確認(rèn)信號(hào)ACK發(fā)端收端信息反饋IF信息信號(hào)信息信號(hào)發(fā)端收端混合糾錯(cuò)HEC檢錯(cuò)和糾錯(cuò)碼確認(rèn)信號(hào)ACK二、差錯(cuò)控制的基本工作方式二、差錯(cuò)控制的基本工作方式77-2 糾錯(cuò)編碼的基本原理 用兩位編碼可表示4種天氣： 信息位晴00云01陰10雨11監(jiān)督位0110增加1位監(jiān)督位，則可檢測(cè)1位錯(cuò)誤。3位編碼共有8個(gè)碼組，上述4種為許用碼組（合法碼組），其它4種為禁用碼組。8（1） 碼長(zhǎng)、碼重和碼距n碼長(zhǎng)n：碼組(碼字)中碼元的數(shù)目。n碼重w：碼組中非0碼元的數(shù)目。n碼距d：兩個(gè)等長(zhǎng)碼組之間對(duì)應(yīng)位不同的數(shù)目稱為這兩個(gè)碼組的的漢明距離，簡(jiǎn)稱碼距。例如碼組C1=11010，則碼

4、長(zhǎng)n=5，碼重w=3； C1=11010與碼組C2=10100之間的距離為d=3。n兩個(gè)二進(jìn)制碼組模二相加得到的新碼組的重量就是這兩個(gè)碼組之間的距離。1.糾錯(cuò)碼的基本概念92.分組碼的糾（檢）錯(cuò)能力與d0的關(guān)系最小碼距d0：所有碼組之間的最小碼距，決定碼的糾檢錯(cuò)能力。01ed（1）檢測(cè)e個(gè)隨機(jī)錯(cuò)誤：021td（2）糾正t個(gè)隨機(jī)錯(cuò)誤：01ted（3）糾正t個(gè)同時(shí)檢測(cè)e（t）個(gè)隨機(jī)錯(cuò)誤：ABd0e.AABd0tt.ABd0ABet.AB102.分組碼的糾（檢）錯(cuò)能力與d0的關(guān)系以（n,1)重復(fù)碼為例：A、B兩種消息用“1”、“0”表示，編為(2,1)重復(fù)碼為“11”及“00”d0為2，可檢測(cè)1位錯(cuò)

5、編為(3,1)重復(fù)碼為“111”及“000”d0為3，用于檢錯(cuò)時(shí)，可檢出2位錯(cuò)用于糾錯(cuò)時(shí)，根據(jù)最大似然準(zhǔn)則，可糾正1位錯(cuò)編為(4,1)重復(fù)碼為“1111”及“0000”d0為4，用于檢錯(cuò)時(shí)，可檢出3位錯(cuò)用于糾錯(cuò)時(shí)，可糾正1位錯(cuò)的同時(shí)檢出2位錯(cuò)11對(duì)糾錯(cuò)碼的基本要求是：n糾錯(cuò)和檢錯(cuò)能力盡量強(qiáng)；n編碼效率盡量高；n碼長(zhǎng)盡量短；n編碼規(guī)律盡量簡(jiǎn)單。3.對(duì)糾錯(cuò)編碼的基本要求及效用編碼效率：碼元中信息元所占的比例，通常用R=k/n來表示124.糾錯(cuò)編碼的效用采用差錯(cuò)控制編碼，即使僅能檢測(cè)或糾正碼組中12個(gè)錯(cuò)誤，也可以使誤碼率下降幾個(gè)數(shù)量級(jí)。這就表明，即使是較簡(jiǎn)單的差錯(cuò)控制編碼也具有較大實(shí)際應(yīng)用價(jià)值。 碼

6、長(zhǎng)為n的碼組中恰好發(fā)生r個(gè)錯(cuò)碼的概率為 ：!( )(1)!()!rrn rrnneeenP rC pppr nr當(dāng)碼長(zhǎng)n7，pe=103時(shí)，則有 37257387(1)77 10(2)212.1 10(3)353.5 10eeePpPpPp131.奇偶監(jiān)督碼(奇偶校驗(yàn)碼）：在n1個(gè)信息元后面附加一個(gè)監(jiān)督元，使得長(zhǎng)n的碼子中1的個(gè)數(shù)保持為奇數(shù)或偶數(shù)的碼稱為奇偶監(jiān)督碼。7.3 常用的簡(jiǎn)單編碼 1200mod2nnaaa加1201mod2nnaaa加偶校驗(yàn)碼監(jiān)督方程：奇校驗(yàn)碼監(jiān)督方程：d0=2，可檢測(cè)1位錯(cuò)及其它奇數(shù)個(gè)錯(cuò)14碼長(zhǎng)為5的偶監(jiān)督碼序號(hào) 碼 字序號(hào) 碼 字信 息 碼 元 監(jiān) 督 元信息碼元

7、 監(jiān) 督 元 0 0 0 0 00 810001 1 0 0 0 11 91 0 0 10 2 0 0 1 01101 0 1 00 3 0 0 1 10111 0 1 11 4 0 1 0 01121 1 0 00 5 0 1 0 10131 1 0 11 6 0 1 1 00141 1 1 01 7 0 1 1 11151 1 1 1015又稱行列監(jiān)督碼或矩陣碼。它同時(shí)對(duì)水平方向及垂直方向的碼元實(shí)施奇偶監(jiān)督。2.二維奇偶監(jiān)督碼1 1 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0 10 1 1 1 1 0 0 0 0 11 0 0 1 1 1 0 0 0 01 0 1 0

8、 1 0 1 0 1 0001011 1 0 0 0 1 1 1 1 00L5，m10的行列監(jiān)督碼16突發(fā)錯(cuò)誤：逐行傳輸時(shí)，能檢測(cè)長(zhǎng)度b m+1=11的突發(fā)錯(cuò)誤;逐列傳輸時(shí),能檢測(cè)長(zhǎng)度bL+1=6的突發(fā)錯(cuò)誤；2.二維奇偶監(jiān)督碼1 1 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0 10 1 1 1 1 0 0 0 0 11 0 0 1 1 1 0 0 0 01 0 1 0 1 0 1 0 1 0001011 1 0 0 0 1 1 1 1 00隨機(jī)錯(cuò)誤：所有1、2、3及其它奇數(shù)個(gè)錯(cuò)；大部分偶數(shù)個(gè)錯(cuò)； 不能檢矩形4個(gè)頂點(diǎn)的偶數(shù)個(gè)錯(cuò)173.恒比碼：數(shù)字碼 字01234567890

9、1101010111100110110110100011110101111000111010011又稱等重碼或定1碼，碼字中1和0的位數(shù)保持恒定比例。我國(guó)電傳通信采用3：2數(shù)字保護(hù)碼，也稱為5中取3恒比碼。3：2數(shù)字保護(hù)碼能夠檢測(cè)所有奇數(shù)個(gè)錯(cuò)誤及部分偶數(shù)個(gè)錯(cuò)誤；不能檢測(cè) “1”錯(cuò)為“0”與“0”錯(cuò)為“1”成對(duì)出現(xiàn)的錯(cuò)碼。 實(shí)際使用經(jīng)驗(yàn)表明，它能使差錯(cuò)減至原來的十分之一左右。187.4 線性分組碼（系統(tǒng)）分組碼的結(jié)構(gòu) 120(.)nnAaaa一般用（n,k)表示分組碼，碼組197.4 線性分組碼7.4.1 7.4.1 線性分組碼的特點(diǎn)線性分組碼的特點(diǎn)碼字用 表示，監(jiān)督碼元與信息碼元之間的關(guān)系可用

10、如下線性方程組表示(以（7，3）分組碼為例)： 線性分組碼的封閉性線性分組碼的封閉性：碼字集中任意兩個(gè)碼字對(duì)應(yīng)位模2加后得到的組合仍然是該碼字集中的一個(gè)碼字。 因此，線性分組碼的最小碼距必等于碼字集中非全0碼字的最小重量。0123456aaaaaaaA 4505614562463aaaaaaaaaaaaa（7 7，3 3）碼的碼字表）碼的碼字表序號(hào) 碼 字信息元監(jiān)督元00 0 00 0 0 010 0 11 1 0 120 1 00 1 1 130 1 11 0 1 041 0 01 1 1 051 0 10 0 1 161 1 01 0 0 171 1 10 1 0 00, ),()(min

11、0iknAAWdii207.4.2 線性分組碼的編碼線性分組碼的編碼 簡(jiǎn)記為：00001000110010001100101110001101000001234560451562456346aaaaaaaaaaaaaaaaaaaaTTOAHOHAT1000110010001100101110001101H監(jiān)督方程組改寫為：此（7，3）分組碼的監(jiān)督矩陣：217.4.2 線性分組碼的編碼線性分組碼的編碼4505614562463aaaaaaaaaaaaa) (456aaa445566aaaaaa) (0123456aaaaaaa101110011100100111001227.4.2 線性分組碼的

12、編碼線性分組碼的編碼 線性分組碼的監(jiān)督矩陣H由r行n列組成，r=n-k，且這r行是線性無關(guān)的。監(jiān)督矩陣具有形式： ，其中 為 的單位矩陣。P是 的矩陣。從而可通過以下矩陣運(yùn)算由信息元求監(jiān)督元： 或rPIH rIrr kr110011111101P1000010000100001rI4560123aaaPaaaa 3210654TaaaaaaaP1000110010001100101110001101H237.4.2 線性分組碼的編碼線性分組碼的編碼 線性分組碼的典型生成矩陣為: ,其中 是 的單位矩陣。所以有由典型生成矩陣生成的碼是系統(tǒng)碼: 如 時(shí)，通過生成矩陣求得的碼字為 :TkPIG kI

13、kk 101110011100100111001GGMA001M1011100101110011100100111001001A110011111101P247.4.2 線性分組碼的編碼線性分組碼的編碼 例：例：已知（7，3）線性分組碼監(jiān)督矩陣為0d求：（1）監(jiān)督元與信息元之間的關(guān)系式；（2）生成矩陣；（3）此碼的全部碼字；（4）此碼的碼距 及糾、檢錯(cuò)能力；（5）此碼的編碼效率。1000011010010100101110001110H257.4.2 線性分組碼的編碼線性分組碼的編碼 1000011010010100101110001110H解：解：4個(gè)監(jiān)督元和個(gè)監(jiān)督元和3個(gè)信息元之間的關(guān)系為

14、個(gè)信息元之間的關(guān)系為 5604614562453aaaaaaaaaaaaa序號(hào)碼 字信息元監(jiān)督元00 0 00 0 0 010 0 11 1 1 020 1 01 1 0 130 1 10 0 1 141 0 00 1 1 151 0 11 0 0 161 1 01 0 1 071 1 10 1 0 0生成矩陣生成矩陣 011110010110101110001GGMA1000 111110010110111010100011110A除全零碼字以外的除全零碼字以外的7個(gè)碼字的重量最小值即為此個(gè)碼字的重量最小值即為此（7，3）分組碼的最小碼距。最小碼距）分組碼的最小碼距。最小碼距 40d如：如：

15、267.4.2 線性分組碼的編碼線性分組碼的編碼 例：例：重復(fù)碼是最簡(jiǎn)單的一類線性分組碼。（n，1）重復(fù)碼總共只有2個(gè)碼字，一個(gè)全0碼字，另一個(gè)是全1碼字。如（5，1）重復(fù)碼的兩個(gè)碼字分別為“00000”和“11111”。試求出（5，1）重復(fù)碼的監(jiān)督矩陣和生成矩陣。01234aaaaaA 解：解：34241404aaaaaaaa434241400000aaaaaaaa410001010010010100011PIH111111TTkPIPIG277.4.3 線性分組碼的譯碼線性分組碼的譯碼 S是1行r列矩陣，它與錯(cuò)誤圖樣有對(duì)應(yīng)關(guān)系，而與發(fā)送碼字無關(guān)。故能確定傳輸中是否發(fā)生了錯(cuò)誤及錯(cuò)誤的位置。0

16、121. aaaaAnn0121. bbbbBnnEBABAE0121. eeeeEnnOHAT()TTTBAB HAEHE HOTTHEHBS發(fā)送碼字發(fā)送碼字：接收碼字接收碼字：發(fā)送碼字和接收碼字之差發(fā)送碼字和接收碼字之差：錯(cuò)誤圖樣錯(cuò)誤圖樣 ：碼字與監(jiān)督矩陣約束關(guān)系碼字與監(jiān)督矩陣約束關(guān)系：若傳輸發(fā)生錯(cuò)誤時(shí)：伴隨式伴隨式：287.4.3 線性分組碼的譯碼線性分組碼的譯碼 以前面所列舉的（7，3）碼為例：1求出錯(cuò)誤圖樣E與伴隨式S之間的關(guān)系。錯(cuò)1位的7種錯(cuò)誤圖樣所對(duì)應(yīng)的伴隨式，剛好對(duì)應(yīng) 中的7行。1000110010001100101110001101H 編編 號(hào)號(hào) 錯(cuò)碼位置錯(cuò)碼位置E ES S

17、 1 11000000100000011101110 2 20100000010000001110111 3 30010000001000011011101 4 40001000000100010001000 5 50000100000010001000100 6 60000010000001000100010 7 70000001000000100010001伴隨式和錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系:6b5b4b3b2b1b0bTH1110011111011000010000100001TH297.4.3 線性分組碼的譯碼線性分組碼的譯碼 2計(jì)算接收碼字的伴隨式，然后查上面表得錯(cuò)誤圖樣。 如接收碼字為B1

18、100111，則其伴隨式為： 111001111101110011111101000010000100001TSB H010011110000001100111EBA查上面表得錯(cuò)誤圖樣E1000000 ，可見接收碼字中b6有錯(cuò)誤。3用錯(cuò)誤圖樣糾正接收碼字中的錯(cuò)誤。 307.4.3 線性分組碼的譯碼線性分組碼的譯碼 例：例：已知（7,3）線性分組碼監(jiān)督矩陣為（1）檢驗(yàn)“1100111”是否為碼字；（2）當(dāng)譯碼器接收到“1100111”時(shí)，求譯碼器的輸出。 1000011010010100101110001110H011111011110110011111010000100001000010000

19、1S不是碼字00010000001001000000100100000010010000001000111000100001101010000001111000000SESESESESESESE11010100000SE100011101000001100111 EB糾正后的碼字：糾正后的碼字： 譯碼器輸出：前譯碼器輸出：前3位信息碼元位信息碼元“100”。317.4.4 漢明碼漢明碼31n(1)加多少位監(jiān)督元可滿足要求，最經(jīng)濟(jì)？加多少位監(jiān)督元可滿足要求，最經(jīng)濟(jì)？n(2)r位監(jiān)督元如何加？有沒有一般規(guī)則？位監(jiān)督元如何加？有沒有一般規(guī)則？n以以r=3為例為例編碼器k位信息元位信息元n位碼字位碼字

20、110nn kn kAaaaa k位信息元n-k=r位監(jiān)督元21rn取取“”號(hào)號(hào)最經(jīng)濟(jì)：在糾最經(jīng)濟(jì)：在糾1位錯(cuò)情況下冗余最小位錯(cuò)情況下冗余最小326510324Aa a a a a a aa4錯(cuò)a3錯(cuò)無錯(cuò)a2錯(cuò)a1錯(cuò)a6錯(cuò)a5錯(cuò)a0錯(cuò)s2 s1 s01 1 11 1 01 0 10 1 11 0 00 0 00 1 00 0 121rnr=3n=7, k=4信道編碼器?4位信息元位信息元7位發(fā)送碼組位發(fā)送碼組對(duì)應(yīng)標(biāo)識(shí)對(duì)應(yīng)標(biāo)識(shí)譯碼器7位接收碼組位接收碼組7.4.4 漢明碼漢明碼336510324Aa a a a a a aa4錯(cuò)a3錯(cuò)無錯(cuò)a2錯(cuò)a1錯(cuò)a6錯(cuò)a5錯(cuò)a0錯(cuò)s2 s1 s01 1 11

21、 1 01 0 10 1 11 0 00 0 00 1 00 0 121rnr=3n=7, k=4S2=a6+a5+a4+a2S1=a6+a5+a3+a1S0=a6+a4+a3+a0a6+a5+a4+a20a6+a5+a3+a10a6+a4+a3+a00a2a6+a5+a4a1a6+a5+a3a0a6+a4+a31、列出所有差錯(cuò)情況；、列出所有差錯(cuò)情況；2、確定一一對(duì)應(yīng)標(biāo)識(shí)；、確定一一對(duì)應(yīng)標(biāo)識(shí)；3、找出監(jiān)督碼元與信息碼元關(guān)系；、找出監(jiān)督碼元與信息碼元關(guān)系；S2=a6+a5+a4+a2S1=a6+a5+a3+a1S0=a6+a4+a3+a07.4.4 漢明碼漢明碼343434序號(hào)碼字序號(hào)碼字信息

22、元監(jiān)督元信息元監(jiān)督元00000000810001111000101191001100200101011010100103001111011101100140100110121100001501011011311010106011001114111010070111000151111111編碼效率：47kn(7,4)漢明碼所有漢明碼所有16個(gè)碼字個(gè)碼字357.4.4 漢明碼漢明碼 漢明碼漢明碼：一種高效率的糾單個(gè)錯(cuò)誤的線性分組碼。其特點(diǎn)是最小碼距，碼長(zhǎng)n與監(jiān)督元個(gè)數(shù)r滿足關(guān)系式。所以有（7，4）、（15，11）、（31，26）等漢明碼。30d12 rn654265316430000aaaaaaa

23、aaaaa0001001101010101100101110123456aaaaaaa1（7，4）漢明碼的編碼監(jiān)督元與信息元之間的關(guān)系：111010011010101011001H從而：從而：367.4.4 漢明碼漢明碼編碼編碼由漢明碼監(jiān)督矩陣：3100110101010110010111PIH110110110111P11010001010100011001011100014TPIG可得：可得：從而：從而：377.4.4 漢明碼漢明碼編碼編碼由，可得漢明碼16個(gè)碼字：1000111010011000101010001011GGMA 序序 號(hào)號(hào) 碼碼 字字 序序 號(hào)號(hào) 碼碼 字字 信信 息息

24、元元 監(jiān)監(jiān) 督督 元元 信信 息息 元元 監(jiān)監(jiān) 督督 元元 0 00 0 0 00 0 0 0 0 0 0 0 0 0 8 81 0 0 01 0 0 0 1 1 1 1 1 1 1 10 0 0 10 0 0 1 0 1 1 0 1 1 9 91 0 0 11 0 0 1 1 0 0 1 0 0 2 20 0 1 00 0 1 0 1 0 1 1 0 1 10 101 0 1 01 0 1 0 0 1 0 0 1 0 3 30 0 1 10 0 1 1 1 1 0 1 1 0 11 111 0 1 11 0 1 1 0 0 1 0 0 1 4 40 1 0 00 1 0 0 1 1 0 1

25、1 0 12 121 1 0 01 1 0 0 0 0 1 0 0 1 5 50 1 0 10 1 0 1 1 0 1 1 0 1 13 131 1 0 11 1 0 1 0 1 0 0 1 0 6 60 1 1 00 1 1 0 0 1 1 0 1 1 14 141 1 1 01 1 1 0 1 0 0 1 0 0 7 70 1 1 10 1 1 1 0 0 0 0 0 0 15 151 1 1 11 1 1 1 1 1 1 1 1 1387.4.4 漢明碼漢明碼譯碼譯碼2 2漢明碼的譯碼：漢明碼的譯碼：碼長(zhǎng)為7的碼字中至少加入3位監(jiān)督元才能糾單個(gè)錯(cuò)誤，（7，4）漢明碼在7位碼字中只有3位監(jiān)

26、督元，因此（7，4）漢明碼是一種糾單個(gè)錯(cuò)誤的編碼效率最高的線性分組碼。 6b5b4b3b2b1b0b （7，4）漢明碼伴隨式和錯(cuò)誤圖樣的對(duì)應(yīng)關(guān)系： 編 號(hào) 錯(cuò)碼位置 E S 1 1000000 111 2 0100000 110 3 0010000 101 4 0001000 011 5 0000100 100397.4.4 漢明碼漢明碼譯碼譯碼（7,4）漢明碼的7種錯(cuò)誤圖樣與7個(gè)伴隨式之間的關(guān)系只要一一對(duì)應(yīng)就不會(huì)影響碼的糾、檢錯(cuò)能力。所以改變上表的對(duì)應(yīng)關(guān)系，即得到不同的（7，4）漢明碼的監(jiān)督關(guān)系。如改變上表的對(duì)應(yīng)關(guān)系為： 100010001111110011101TH100110101011

27、100011011H000034613452356aaaaaaaaaaaa從而監(jiān)督矩陣為得到另一個(gè)（7，4）漢明碼的監(jiān)督關(guān)系方程組為： 按此方法還可構(gòu)造出其它不同的（按此方法還可構(gòu)造出其它不同的（7，4）漢明碼的監(jiān)督關(guān)系，進(jìn)而得到不同）漢明碼的監(jiān)督關(guān)系，進(jìn)而得到不同的（的（7，4）漢明碼。盡管碼字集不同，但它們具有相同的性能，即編碼效率）漢明碼。盡管碼字集不同，但它們具有相同的性能，即編碼效率相同，糾、檢錯(cuò)能力相同。相同，糾、檢錯(cuò)能力相同。 40作業(yè)n計(jì)算機(jī)處理信息一般以字節(jié)（8bit）或字（16bit或32bit）為單位。為便于處理，信息編碼后最好為8、16或32bit。請(qǐng)?jiān)O(shè)計(jì)一種（8，4）

28、線性分組碼，給出H、G、全部碼字、最小碼距d0及糾檢錯(cuò)能力。41線性分組碼小結(jié)生成矩陣生成矩陣G監(jiān)督矩陣監(jiān)督矩陣H4505614562463aaaaaaaaaaaaa4505614562463aaaaaaaaaaaaa445566 aaaaaa編碼信道編碼信道信息信息M碼組碼組ABAE錯(cuò)誤圖樣錯(cuò)誤圖樣EA=M GS=B HT碼組碼組B伴隨式伴隨式SEABE42線性分組碼,任一碼組循環(huán)移位所得的序列仍在該碼組集中。7-5 循環(huán)碼信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0碼組編號(hào) 12340000010100110000011111101001碼組編號(hào) 5678信息位監(jiān)督

29、位1001011101111011110001010010(7,3)循環(huán)碼舉例0010111000000043121210( ).nnnnT xaxaxa xa1、碼多項(xiàng)式例：A110100165432653( )11010011T xxxxxxxxxx 碼多項(xiàng)式的系數(shù)表示碼元值（取0或1），變量的指數(shù)表示碼元位置：x442、多項(xiàng)式除法及模運(yùn)算例：對(duì)于二進(jìn)制編碼，碼多項(xiàng)式的系數(shù)按模2運(yùn)算。53225252111(1) mod (1)(1)(mod1)xxxxxxxxxxxxxx又如：又如：331(mod1)xx422311(mod1)xxxxx 453、生成多項(xiàng)式循環(huán)碼中，除全0碼字外，次數(shù)最

30、低的碼字多項(xiàng)式稱為生成多項(xiàng)式，并用g(x)表示。g(x)具有如下特性：（1） g(x)是xn+1的一個(gè)因子；（2） g(x)是r=n-k次多項(xiàng)式；（3） g(x)的常數(shù)項(xiàng)為1。如某(7,3)循環(huán)碼生成多項(xiàng)式為1)(234xxxxg循環(huán)碼完全由其碼字長(zhǎng)度n及生成多項(xiàng)式所決定。可知xn+1=g(x)h(x) ，且，且g(x)是前(k-1)位都是0的碼字的碼多項(xiàng)式：g(x)=xr +gr-1xr-1 +gr-2xr-2 + +g1x +1463、生成多項(xiàng)式例：對(duì)于n=7的循環(huán)碼，有：x7+1 = (x+1 ) (x3+ x2 +1 ) (x3+x+1 )(7,4)循環(huán)碼:g(x)=(x3+ x2 +

31、1 )或g(x)=(x3+x+1 )(7,3)循環(huán)碼:g(x)=(x4+x2+x+1 )或g(x)=(x4+x3+x2+1 )生成多項(xiàng)式尋找：生成多項(xiàng)式尋找： 對(duì)對(duì)xn+1進(jìn)行因式分解，找出r=n-k次因式，也即尋找符合上述三個(gè)條件的多項(xiàng)式。474、生成矩陣G若T(x)是一長(zhǎng)為n的碼字多項(xiàng)式，則xiT(x) mod xn+1相當(dāng)于碼字T(x)循環(huán)左移i位，因而也是一個(gè)碼字。如：碼長(zhǎng)如：碼長(zhǎng)n=7 n=7 的碼多項(xiàng)式的碼多項(xiàng)式T(x)=(x6+x5+x2+1 )，對(duì)應(yīng)的碼字為1100101，則3365298535327( )(1)(mod1)x T xxxxxxxxxxxxxx對(duì)應(yīng)的碼字為010

32、1110484、生成矩陣G由前面討論的線性分組碼可知，生成矩陣由前面討論的線性分組碼可知，生成矩陣G G由由k k個(gè)線性無關(guān)的碼個(gè)線性無關(guān)的碼字組成，字組成，G G是一是一k k行行n n列矩陣。列矩陣。又知又知g(x),xg(x),xg(x),xg(x),xk-1k-1g(x)g(x)都是碼字，且是線性不相關(guān)的，都是碼字，且是線性不相關(guān)的，因此可以構(gòu)成循環(huán)碼的生成矩陣：因此可以構(gòu)成循環(huán)碼的生成矩陣：)()()()()(21xgxgxxgxxgxxGkk494、生成矩陣G例：例：(7,3)循環(huán)碼信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0碼組編號(hào) 12340000010

33、100110000011111101001碼組編號(hào) 5678信息位監(jiān)督位1001011101111011110001010010r=4r=4次碼多項(xiàng)式為次碼多項(xiàng)式為x4+x2+x+1，故有：2( )1011100( )( )0101110( )0010111x g xG xxg xGg x505、循環(huán)碼的編碼由生成矩陣可生成循環(huán)碼的所有碼字：2( )1011100( )( )0101110( )0010111x g xG xxg xGg x22654654( )( )( )( )() ( )( ) ( )( )x g xT xMG xa a axg xa xa xag xm x g xg x結(jié)

34、論：所有碼多項(xiàng)式T(x)都可被g(x)整除；所有小于n次的g(x)的倍式都是碼多項(xiàng)式。 即T(x)是次數(shù)n的多項(xiàng)式，則： 已知生成矩陣：T(x)能被g(x)整除T(x)是碼多項(xiàng)式515、循環(huán)碼的編碼（1）用xn-k乘m(x)，即信息碼后附加上（nk）個(gè)“0”。T(x)能被g(x)整除T(x)是碼多項(xiàng)式系統(tǒng)編碼方法三步:（2）用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即 )()()()()(xgxrxQxgxmxkn( )( )( ) ( )n kxm xr xQ x g x（3）編出的碼組T(x)為：)()()(xrxmxxTkn如(7,3)碼g(x)=x4+ x2+ x+1

35、，設(shè) m(x)x2+x，即信息碼為110： （1）xn-km(x)x4（x2+x）= x6+x5 （2）2( )( )mod( )1n kr xxm xg xx（3）T(x)1100000+1011100101 525、循環(huán)碼的編碼多項(xiàng)式除法：g(x)除xn-km(x)，求余式r(x)的實(shí)現(xiàn)。mf 011ef 1010輸入移存器反饋輸出mabcdef0000000110111010011010111000001010010000100000101（1）開關(guān)S倒向下方，輸入信息位。信息位輸出的同時(shí)做除法運(yùn)算。（2）信息位全部進(jìn)入除法器后，開關(guān)轉(zhuǎn)向上。此時(shí)反饋端為0，移存器中即為除法余項(xiàng)。 g(x

36、)=x4+ x2+ x+1 的除法電路:536、循環(huán)碼的譯碼原理糾錯(cuò)與檢錯(cuò)S(x) = R(x) mod g(x)= E(x) mod g(x)除法電路S到E的轉(zhuǎn)換(查表或電路)檢錯(cuò)：檢測(cè)余式是否為0。糾錯(cuò)：余式與錯(cuò)誤圖樣對(duì)應(yīng)54譯碼器的大致結(jié)構(gòu)除法電路(計(jì)算S)組合邏輯(S到E的轉(zhuǎn)換)SEBA55循環(huán)碼譯碼器方案循環(huán)碼譯碼器方案(7,3)循環(huán)碼,g(x)= x4+x2+ x +1567-5-3縮短循環(huán)碼 采用縮短循環(huán)碼的原因：q在系統(tǒng)設(shè)計(jì)中，碼長(zhǎng)n、信息位數(shù)k和糾錯(cuò)能力常常是預(yù)先給定的。q并不是所有長(zhǎng)度n和k上都能找到相應(yīng)的滿足某糾錯(cuò)能力的循環(huán)碼。這時(shí)若將循環(huán)碼縮短，即可滿足n、k和糾錯(cuò)碼能

37、力的要求，且有循環(huán)碼編譯碼簡(jiǎn)單的特點(diǎn)。 57信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0碼組編號(hào) 12340000010100110000011111101001碼組編號(hào) 5678信息位監(jiān)督位1001011101111011110001010010(7,3)循環(huán)碼縮短循環(huán)碼的構(gòu)成 取首位信息碼為0的碼組去掉固定為0的首位信息碼(6,2)縮短循環(huán)碼58交織碼又稱交錯(cuò)碼，是一種能糾正突發(fā)錯(cuò)誤的碼，它是以交錯(cuò)的方法來構(gòu)造碼的。 把糾隨機(jī)錯(cuò)誤的（n，k）線性分組碼的m個(gè)碼字，排成m行的一個(gè)碼陣，該碼陣稱為交錯(cuò)碼陣。一個(gè)交錯(cuò)碼陣就是交錯(cuò)碼的一個(gè)碼子。碼陣在傳輸時(shí)按列的次序進(jìn)行，這

38、樣可以將突發(fā)錯(cuò)誤變?yōu)殡S機(jī)錯(cuò)誤加以糾正。7-5-4 交織技術(shù) 59交織碼糾突發(fā)錯(cuò)的原理 例：(7,4)漢明碼，4行，按列傳輸。a16a15a14a13a12a11a10a26a25a24a23a22a21a20a36a35a34a33a32a31a30a46a45a44a43a42a41a40607-6 卷積碼 初始態(tài)：00輸入：11010000輸出：(2,1,2)卷積碼(n,k,m)卷積碼m:編碼存儲(chǔ)(m+1):約束度n(m+1):約束長(zhǎng)度C C1 1=S=S1 1+S+S2 2+S+S3 3，C C2 2=S=S1 1+S+S3 3S111010000S3S20001111001100000

39、C1C21101010010110000狀態(tài)狀態(tài)（S3S2）abdcbcaa61卷積碼圖解法： 狀態(tài)圖 樹圖 格圖 卷積碼的表示方法(2,1,2) 碼的狀態(tài)圖 01C C1 1=S=S1 1+S+S2 2+S+S3 3，C C2 2=S=S1 1+S+S3 362(2,1,2) 卷積碼的樹圖 01630100a:00000000000011b:01c:10d:1111111111111111111010101010110101010101010101010000000010101010(2,1,2) 卷積碼的格狀圖 64卷積碼的譯碼卷積碼譯碼可分為：代數(shù)譯碼。代數(shù)譯碼是利用生成矩陣和監(jiān)督矩陣來

40、譯碼，最主要的方法是大數(shù)邏輯譯碼大數(shù)邏輯譯碼。概率譯碼。概率譯碼比較實(shí)用的有兩種：維特維特比譯碼比譯碼和序列譯碼序列譯碼。維特比譯碼思路： 把接收碼字與所有可能的碼字比較，選擇一種碼距最小的碼字作為解碼輸出。65收碼： 01 01 01 10 10 01 0100a:00000000000011b:01c:10d:111111111111111111101010101011010101010101010101000000001010101011223133424413維特比譯碼(1)發(fā)送碼字：發(fā)送碼字：11 01 01 00 10 11 發(fā)送信息：發(fā)送信息：110100 66維特比譯碼(2)677-7 偽隨機(jī)序列確知序列確知序列：有規(guī)律、可控、可復(fù)現(xiàn)序列隨機(jī)序列隨機(jī)序列：無規(guī)律、不可控、不可復(fù)現(xiàn)序列偽隨機(jī)序列偽隨機(jī)序列：具有隨機(jī)特性的確知序列m m序列序列 -由線性反饋移位