信息論與編碼原理 信道編碼

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長長 (n , k) 碼字碼字n長長 qk 種種 分組編碼器分組編碼器 qn種種 k維維k重矢量重矢量 n維維n重矢量重矢量 通常通常qn qk，分組編碼的任務(wù)是，分組編碼的任務(wù)是要在要在n維維n重矢量空間的重矢量空間的qn種可能組合種可能組合中選擇其中的中選擇其中的qk個構(gòu)成一個個構(gòu)成一個碼空間碼空間，其元素就是許用碼的其

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 碼集與映射關(guān)系碼集與映射關(guān)系信息 碼字 系統(tǒng)碼字000 000000 000000001011101001011010110001010110011101100011101100111010100111101100111101100110001011110001111010110111010二元二元(6,3)線性分組碼編碼器線性分組碼編碼器 m0m1m2 輸入 輸出 c0c1c2 (1)(1)(1)1(1)01(1)11100(1)0100Tn knn kn knnhhhhhhhhh 依據(jù)：依據(jù)：若若BSC信道的差錯概率是信道的差錯概率是p，則長度，則長度n的碼中錯誤概率的碼中錯誤概率

5、 ： 0個錯個錯 1個錯個錯 2個錯個錯 n個錯個錯 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于由于p 出錯越少的情況，發(fā)生概率越大，出錯越少的情況，發(fā)生概率越大，E的重量越輕，的重量越輕，所以該譯碼方法實際上體現(xiàn)了最小距離譯碼準(zhǔn)則，所以該譯碼方法實際上體現(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

6、k SE112n k EC12n ki EC1221n kk EC21kjEC121kEC02121kkECC例例 6-3 一個一個(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個許用碼字為個許用碼字為C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。求出校驗矩陣：求出校

7、驗矩陣： H = PT I3 = 列出方程組：列出方程組：1011011101ic 242322212014131211100403020100111001001011001hhhhhhhhhhhhhhh24243232221 2102043214 143 132 121 110 104104043 032021 01000430se he he he he heeese he he he he heese he he he he heee伴隨式有伴隨式有2n-k238種組合，差錯圖案中代表無差錯的有種組合，差錯圖案中代表無差錯的有一種，代表一個差錯的圖案有一種，代表一個差錯的圖案有 種，已有

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

9、0011)和和(10100)并列重量最輕，任選其中一個如并列重量最輕，任選其中一個如(00011)。同樣可得伴隨式同樣可得伴隨式(110)所對應(yīng)的最輕差錯圖案之一是所對應(yīng)的最輕差錯圖案之一是(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=00

10、001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例例 6-3 標(biāo)準(zhǔn)陣列譯碼表標(biāo)準(zhǔn)陣列譯碼表例例 6-3 將接收碼將接收碼R10101譯碼譯碼 可選以下三種方法之一譯碼：可選以下三種方法之一譯碼：n直接搜索碼表，查得直接搜索碼表，查得(10101)所在列的子集頭是所在列的子集頭是(10111)，因此譯，因此譯碼輸出取為碼輸出取為(10111)。n先求伴隨式先求伴隨式RHT = (10101) HT = (010) = S4，確定，確定S4所在行，所在行，再沿著行對碼表作一維搜索找到再沿著行對碼

11、表作一維搜索找到(10101), 最后順著所在列向上最后順著所在列向上找出碼字找出碼字(10111)。n先求出伴隨式先求出伴隨式RHT = (010) = S4并確定并確定S4所對應(yīng)的陪集首（差所對應(yīng)的陪集首（差錯圖案）錯圖案）E4=(00010)，再將陪集首與收碼相加得到碼字，再將陪集首與收碼相加得到碼字C= R+ E4= (10101)+ (00010)= (10111)。 上述三種方法由上而下，查表的時間下降而所需計算量增大，上述三種方法由上而下，查表的時間下降而所需計算量增大，實際使用時可針對不同情況選用。實際使用時可針對不同情況選用。 對上例作進一步分析，還可以看到，該對上例作進一步

12、分析，還可以看到，該(5,2)碼的碼的dmin=3, 糾錯能力是糾錯能力是t = INT(3-1)/2 = 1。因此，譯碼陣列中。因此，譯碼陣列中只有前只有前6行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯碼準(zhǔn)則，而第碼準(zhǔn)則，而第7、8行的差錯圖案行的差錯圖案(00011)和和(00110)中包含兩中包含兩個個“1”，已超出了，已超出了t= 1的糾錯能力，譯碼已不可靠。比如，的糾錯能力，譯碼已不可靠。比如，當(dāng)收碼當(dāng)收碼R(10100)時，根據(jù)碼表譯出的碼字是時，根據(jù)碼表譯出的碼字是(10111)，與，與收碼收碼R的漢明距離是的漢明距離是2，然而收碼，然而收

13、碼R與全零碼字與全零碼字(00000)的漢的漢明距離也是明距離也是2，為什么不能譯成，為什么不能譯成(00000)呢？事實上，碼表呢？事實上，碼表的第的第7、8行本身就不是唯一的。注意在碼表計算過程中，行本身就不是唯一的。注意在碼表計算過程中，伴隨式伴隨式(011)所對應(yīng)的所對應(yīng)的4個差錯圖案中有兩個并列重量最輕，個差錯圖案中有兩個并列重量最輕，如果當(dāng)時選的不是如果當(dāng)時選的不是(00011)而是而是(10100)，那么碼表第，那么碼表第7行就行就不是現(xiàn)在這樣了。不是現(xiàn)在這樣了。 對例對例 6-3的的分析分析td=7dmin=3d=5C1C2C3C4C5min12dtINT11101000111

14、010110100102012tnkinnnnnti02tnkini1011(21)22mmnkinni例例 6.4 構(gòu)造一個構(gòu)造一個m=3的二元的二元(7，4)漢明碼。漢明碼。解：先利用漢明碼的特性構(gòu)造一個解：先利用漢明碼的特性構(gòu)造一個(7，4)漢明碼的校驗漢明碼的校驗矩陣矩陣H，再通過列置換將它變?yōu)橄到y(tǒng)形式：，再通過列置換將它變?yōu)橄到y(tǒng)形式： 0 0 0 1 1 1 1 列置換列置換 1 1 1 0 1 0 0 H = 0 1 1 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

15、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)碼生成多項式是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)，得余式(x3+ x). C(x) = xn-k m(x) + r (x)( x5+ x4)+ (x3+ x), 對應(yīng)碼矢(0111010)。依次將(000)(11

16、1)代入，可得全部碼矢如表6-6。此表與表6-5對比，可見碼集未變而映射規(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 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 CimG m3m2m1m0 碼字中的碼字中的c6去掉，去掉，c6是信息位是信息位m與與G的第一列

17、相乘結(jié)果，所以的第一列相乘結(jié)果，所以G的第的第一列應(yīng)去掉；一列應(yīng)去掉；m3去掉，而去掉，而m3是與是與G的的第一行相乘，所以第一行相乘，所以G的第一行也去掉。的第一行也去掉。1000 10101001110010 1100001011得到新的生成矩陣為得到新的生成矩陣為 G 36原來的校驗矩陣原來的校驗矩陣H為為 H 37校驗時，計算校驗時，計算rHT，因，因r的第一位已沒有，故的第一位已沒有，故HT的第一的第一行應(yīng)去掉，即行應(yīng)去掉，即H的第一列去掉。得到新的校驗矩陣的第一列去掉。得到新的校驗矩陣H為為 H dmin不變，為不變，為3。 3610011101011000101111101000

18、1110101101001110100111010101001例例610 某CRC碼的生成多項式 g(x)=x4+ x+1。如果想發(fā)送一串信息110001的前6位并加上CRC校驗，發(fā)碼應(yī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( 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，對應(yīng)的碼字是 (1100011100)。 接收端的CRC校驗實際上就是做除法。如果收碼無誤，R(x)除以g(x)應(yīng)得余式0；反之，如果余式不等于零就說明一定有差錯。 c0i信號入 m c1i C i 編碼輸出 c2i m0i m0i-1m1i m1i-1000000010200010111210 101 1gggGgg