信息論與編碼6 信道編碼

1、01(1)(,),iiiiji nijVV VVVVF12,ikVVVV及1 122,()kiiiVaVa VaVaF1 1220,()iiiaVa VaVaF且不全為零12,nV VV1(000),(100)V2(000),(001),(010),(011)V 消息消息k長(zhǎng)長(zhǎng) (n , k) 碼字碼字n長(zhǎng)長(zhǎng) qk 種種 分組編碼器分組編碼器 qn種種 k維維k重矢量重矢量 n維維n重矢量重矢量 通常通常qn qk，分組編碼的任務(wù)是，分組編碼的任務(wù)是要在要在n維維n重矢量空間的重矢量空間的qn種可能組合種可能組合中選擇其中的中選擇其中的qk個(gè)構(gòu)成一個(gè)個(gè)構(gòu)成一個(gè)碼空間碼空間，其元素就是許用碼的其

2、元素就是許用碼的碼集碼集。 ()( )NMmPqc11( ) ( )( )NMNMqqNMeemmemmmPPPqPccc11( ) ( )( )NMNMqqNMeemmemmmPPPqPccc( )emePPc( )emePPc0eP ( )0emPceP0eP ()NE RePe E(R) C R 0 R0 -45 E(R)和和R的關(guān)系曲線的關(guān)系曲線E(R) R0 R1 R2 C1 C2 增大增大E(R)的途徑的途徑()NE RePe12(,)NiiiiNc cccX 消息組消息組mi 碼字碼字ci 接收碼接收碼r 估值估值 消息消息 icim編碼器編碼器 信道信道 譯碼譯碼 消息還原消息

3、還原max (/ )iiPcc rmax( /)iiPcr c()(/)(/),1,2,2( )KiiiPPPiPcrccrr1( /)(/)NijijjMaxPMaxP rcr c 消息消息m (n , k) 碼字碼字c m=(mk-1,m1,m0) 分組編碼器分組編碼器 c=(cn-1,c1,c0) qk qn n維維n重空間重空間V k維維k重重 k維維n重重 信息組信息組 碼空間碼空間 空間空間m C(1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1

4、0 1 信息 碼字 系統(tǒng)碼字000 000000 000000001011101001011010110001010110011101100011101100111010100111101100111101100110001011110001111010110111010 m0m1m2 輸入 輸出 c0c1c2 (1)(1)(1)1(1)01(1)11100(1)0100Tn knn kn knnhhhhhhhhh 依據(jù)：依據(jù)：若若BSC信道的差錯(cuò)概率是信道的差錯(cuò)概率是p，則長(zhǎng)度，則長(zhǎng)度n的碼中錯(cuò)誤概率的碼中錯(cuò)誤概率 ： 0個(gè)錯(cuò)個(gè)錯(cuò) 1個(gè)錯(cuò)個(gè)錯(cuò) 2個(gè)錯(cuò)個(gè)錯(cuò) n個(gè)錯(cuò)個(gè)錯(cuò) (1-p)n p(1-p

5、)n-1 p2(1-p)n-2 pn 由于由于p 出錯(cuò)越少的情況，發(fā)生概率越大，出錯(cuò)越少的情況，發(fā)生概率越大，E的重量越輕，的重量越輕，所以該譯碼方法實(shí)際上體現(xiàn)了最小距離譯碼準(zhǔn)則，所以該譯碼方法實(shí)際上體現(xiàn)了最小距離譯碼準(zhǔn)則，即最大似然譯碼。即最大似然譯碼。2n2nS0 E0S1 E1 Sj Ej E0+C0= 0+0= 0E0+C1= C1E0+Ci= CiE1+C0= E1 E1+Ci Ej+C0= EjEj+C1Ej+Ci 標(biāo)準(zhǔn)陣列譯碼表標(biāo)準(zhǔn)陣列譯碼表 E1+C1 11022n kn k ECE1122n kn k SE112n k EC12n ki EC1221n kk EC21kjEC

6、121kEC02121kkECC例例 6-3 一個(gè)一個(gè)(5,2)系統(tǒng)線性碼的生成矩陣是系統(tǒng)線性碼的生成矩陣是G = 設(shè)收碼設(shè)收碼R = (10101)，構(gòu)造標(biāo)準(zhǔn)陣列譯碼表，譯出發(fā)碼的估值，構(gòu)造標(biāo)準(zhǔn)陣列譯碼表，譯出發(fā)碼的估值解：解：(1)構(gòu)造標(biāo)準(zhǔn)陣列譯碼表。分別以信息組構(gòu)造標(biāo)準(zhǔn)陣列譯碼表。分別以信息組m= (00)、(01) 、(10)、(11)及已知的及已知的G求得求得4個(gè)許用碼字為個(gè)許用碼字為C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。求出校驗(yàn)矩陣：求出校驗(yàn)矩陣： H = PT I3 = 列出方程組：列出方程組：1011011101

7、ic 242322212014131211100403020100111001001011001hhhhhhhhhhhhhhh24243 232221 2102043214 143 132 121 110 104104043 032021 01000430se he he hehe heeese he he hehe heese he he hehe heee伴隨式有伴隨式有2n-k238種組合，差錯(cuò)圖案中代表無(wú)差錯(cuò)的有種組合，差錯(cuò)圖案中代表無(wú)差錯(cuò)的有一種，代表一個(gè)差錯(cuò)的圖案有一種，代表一個(gè)差錯(cuò)的圖案有 種，已有種，已有6種。種。代表兩個(gè)差錯(cuò)的圖案有代表兩個(gè)差錯(cuò)的圖案有 種。只需挑選其中的兩個(gè)

8、，種。只需挑選其中的兩個(gè)，挑選方法可有若干種，不是唯一的。先將挑選方法可有若干種，不是唯一的。先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的代入上面的線性方程組，解得對(duì)應(yīng)的線性方程組，解得對(duì)應(yīng)的Sj分別是分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，。剩下的伴隨式中，(011)所對(duì)應(yīng)的差所對(duì)應(yīng)的差錯(cuò)圖案是錯(cuò)圖案是2k個(gè)即個(gè)即(00011)、(10100)、(01110)、(11001),其中其中(00011)和和(10100)并列重量最輕，任選其中一個(gè)如并列重量最輕，任選其中一個(gè)

9、如(00011)。同樣可得伴隨式同樣可得伴隨式(110)所對(duì)應(yīng)的最輕差錯(cuò)圖案之一是所對(duì)應(yīng)的最輕差錯(cuò)圖案之一是(00110)。 551 5102 例例 6-3 譯碼表的構(gòu)成譯碼表的構(gòu)成S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111

10、011001S7=110E7=00110100010101111100例例 6-3 標(biāo)準(zhǔn)陣列譯碼表標(biāo)準(zhǔn)陣列譯碼表 對(duì)上例作進(jìn)一步分析，還可以看到，該對(duì)上例作進(jìn)一步分析，還可以看到，該(5,2)碼的碼的dmin=3, 糾錯(cuò)能力是糾錯(cuò)能力是t = INT(3-1)/2 = 1。因此，譯碼陣列中。因此，譯碼陣列中只有前只有前6行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯碼準(zhǔn)則，而第碼準(zhǔn)則，而第7、8行的差錯(cuò)圖案行的差錯(cuò)圖案(00011)和和(00110)中包含兩中包含兩個(gè)個(gè)“1”，已超出了，已超出了t= 1的糾錯(cuò)能力，譯碼已不可靠。比如，的糾錯(cuò)能力，譯碼已不可

11、靠。比如，當(dāng)收碼當(dāng)收碼R(10100)時(shí)，根據(jù)碼表譯出的碼字是時(shí)，根據(jù)碼表譯出的碼字是(10111)，與，與收碼收碼R的漢明距離是的漢明距離是2，然而收碼，然而收碼R與全零碼字與全零碼字(00000)的漢的漢明距離也是明距離也是2，為什么不能譯成，為什么不能譯成(00000)呢？事實(shí)上，碼表呢？事實(shí)上，碼表的第的第7、8行本身就不是唯一的。注意在碼表計(jì)算過(guò)程中，行本身就不是唯一的。注意在碼表計(jì)算過(guò)程中，伴隨式伴隨式(011)所對(duì)應(yīng)的所對(duì)應(yīng)的4個(gè)差錯(cuò)圖案中有兩個(gè)并列重量最輕，個(gè)差錯(cuò)圖案中有兩個(gè)并列重量最輕，如果當(dāng)時(shí)選的不是如果當(dāng)時(shí)選的不是(00011)而是而是(10100)，那么碼表第，那么碼表

12、第7行就行就不是現(xiàn)在這樣了。不是現(xiàn)在這樣了。 對(duì)例對(duì)例 6-3的的分析分析td=7dmin=3d=5C1C2C3C4C5min12dtINT11101000111010110100102012tnkinnnnnti02tnkini1011(21)22mmnkinni例例 6.4 構(gòu)造一個(gè)構(gòu)造一個(gè)m=3的二元的二元(7，4)漢明碼。漢明碼。解：先利用漢明碼的特性構(gòu)造一個(gè)解：先利用漢明碼的特性構(gòu)造一個(gè)(7，4)漢明碼的校驗(yàn)漢明碼的校驗(yàn)矩陣矩陣H，再通過(guò)列置換將它變?yōu)橄到y(tǒng)形式：，再通過(guò)列置換將它變?yōu)橄到y(tǒng)形式： 0 0 0 1 1 1 1 列置換列置換 1 1 1 0 1 0 0 H = 0 1 1

13、0 0 1 1 0 1 1 1 0 1 0 = PT I3 1 0 1 0 1 0 1 1 1 0 1 0 0 1再得生成矩陣再得生成矩陣G為為 1 0 0 0 1 0 1 G = I4 P = 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 2323231123例例6.6 (7,3)循環(huán)碼生成多項(xiàng)式是g(x)=x4+x3+x2+1，用式(6-3-35)產(chǎn)生系統(tǒng)循環(huán)碼。解解：先以輸入信息m=(011)即m(x) = ( x +1)為例，. xn-k m(x) = x4( x +1) = x5+ x4 . ( x5+ x4)除以(x4+ x3+ x2+ 1)，

14、得余式(x3+ x). C(x) = xn-k m(x) + r (x)( x5+ x4)+ (x3+ x), 對(duì)應(yīng)碼矢(0111010)。依次將(000)(111)代入，可得全部碼矢如表6-6。此表與表6-5對(duì)比，可見碼集未變而映射規(guī)則變了，表6-6滿足系統(tǒng)循環(huán)碼要求。0001111 H例：例：(7,4)碼的生成矩陣為碼的生成矩陣為 47 1000 10101001110010 1100001011m3m2m1 m0ci2ci1ci0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1

15、 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 CimG m3m2m1m0 碼字中的碼字中的c6去掉，去掉，c6是信息位是信息位m與與G的第一列相乘結(jié)果，所以的第一列相乘結(jié)果，所以G的第的第一列應(yīng)去掉；一列應(yīng)去掉；m3去掉，而去掉，而m3是與是與G的的第一行相乘，所以第一行相乘，所以G的第一行也去掉。的第一行也去掉。1000 10101001110010 1100001011得到新的生成矩陣為得到新的生成矩陣為 G 36原來(lái)的校驗(yàn)矩陣原來(lái)的校驗(yàn)矩陣H為為 H 37校驗(yàn)時(shí)，計(jì)算校驗(yàn)時(shí)，計(jì)算rHT，因，因r的第一位已沒(méi)有，故的第一位已沒(méi)有，故HT的第一的第一行應(yīng)去掉，即行應(yīng)去掉，

16、即H的第一列去掉。得到新的校驗(yàn)矩陣的第一列去掉。得到新的校驗(yàn)矩陣H為為 H dmin不變，為不變，為3。 36100111010110001011111010001110101101001110100111010101001例例610 某CRC碼的生成多項(xiàng)式 g(x)=x4+ x+1。如果想發(fā)送一串信息110001的前6位并加上CRC校驗(yàn)，發(fā)碼應(yīng)如何安排？收碼又如何檢驗(yàn)？解：解：本題信息多項(xiàng)式 m(x)= x5+ x4+1,即k = 6，因此n = 10 ，degg(x)= 4 = n-k 。 將xn-k m(x)除以g(x),得余式 r(x)=xn-k m(x) mod g(x) = x4(

17、 x5+ x4+1) mod g(x) =(x9+ x8+ x4) mod g(x) = x3+ x2 于是發(fā)碼C(x)= xn-k m(x) + r (x) = x9+ x8+ x4 +x3 +x2，對(duì)應(yīng)的碼字是 (1100011100)。 接收端的CRC校驗(yàn)實(shí)際上就是做除法。如果收碼無(wú)誤，R(x)除以g(x)應(yīng)得余式0；反之，如果余式不等于零就說(shuō)明一定有差錯(cuò)。 c0i信號(hào)入 m c1i C i 編碼輸出 c2i m0i m0i-1m1i m1i-1000000010200010111210 101 1gggGggg11110001021111011121 111 00gggGggg1 0 10 1 11 1 11 0 00Ll00010(1)10111(1)(1)0(1)1(1)(1)()()()()()()()()()NNKKKNgDgDgDgDgDgDgDgDgD11( )11D DDDDG0Ll c0i 信號(hào)入 m c1i 輸出C i c2im0i m0i-1 m0i-2 0/000 S0 1/111 0/001 1/110 S2 S1 0/011 1/100 0/010 S3 1/101 1/1100/0110/0101/1010/0001/1000/0000/0000/0000/0000/0000/0000/0111/1101/100輸入信息序列是10110，