信息论与编码原理 信道编码

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，分组编码的任务是，分组编码的任务是要在要在n维维n重矢量空间的重矢量空间的qn种可能组合种可能组合中选择其中的中选择其中的qk个构成一个个构成一个码空间码空间，其元素就是许用码的其

2、元素就是许用码的码集码集。 ()( )NMmPqc11( ) ( )( )NMNMqqNMeemmemmmPPPqPccc11( ) ( )( )NMNMqqNMeemmemmmPPPqPccc( )emePPc( )emePPc0eP ( )0emPceP0eP ()NE RePe E(R) C R 0 R0 -45 E(R)和和R的关系曲线的关系曲线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 码集与映射关系码集与映射关系信息 码字 系统码字000 000000 000000001011101001011010110001010110011101100011101100111010100111101100111101100110001011110001111010110111010二元二元(6,3)线性分组码编码器线性分组码编码器 m0m1m2 输入 输出 c0c1c2 (1)(1)(1)1(1)01(1)11100(1)0100Tn knn kn knnhhhhhhhhh 依据：依据：若若BSC信道的差错概率是信道的差错概率是p，则长度，则长度n的码中错误概率的码中错误概率

5、 ： 0个错个错 1个错个错 2个错个错 n个错个错 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于由于p 出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻，的重量越轻，所以该译码方法实际上体现了最小距离译码准则，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。即最大似然译码。2n2nS0 E0S1 E1 Sj Ej E0+C0= 0+0= 0E0+C1= C1E0+Ci= CiE1+C0= E1 E1+Ci Ej+C0= EjEj+C1Ej+Ci 标准阵列译码表标准阵列译码表 E1+C1 11022n kn k ECE1122n kn

6、k SE112n k EC12n ki EC1221n kk EC21kjEC121kEC02121kkECC例例 6-3 一个一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是G = 设收码设收码R = (10101)，构造标准阵列译码表，译出发码的估值，构造标准阵列译码表，译出发码的估值解：解：(1)构造标准阵列译码表。分别以信息组构造标准阵列译码表。分别以信息组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)代入上面的代入上面的线性方程组，解得对应的线性方程组，解得对应的Sj分别是分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，。剩下的伴随式中，(011)所对应的差所对应的差错图案是错图案是2k个即个即(00011)、(10100)、(01110)、(11001),其中其中(0

9、0011)和和(10100)并列重量最轻，任选其中一个如并列重量最轻，任选其中一个如(00011)。同样可得伴随式同样可得伴随式(110)所对应的最轻差错图案之一是所对应的最轻差错图案之一是(00110)。 551 5102 例例 6-3 译码表的构成译码表的构成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 标准阵列译码表标准阵列译码表例例 6-3 将接收码将接收码R10101译码译码 可选以下三种方法之一译码：可选以下三种方法之一译码：n直接搜索码表，查得直接搜索码表，查得(10101)所在列的子集头是所在列的子集头是(10111)，因此译，因此译码输出取为码输出取为(10111)。n先求伴随式先求伴随式RHT = (10101) HT = (010) = S4，确定，确定S4所在行，所在行，再沿着行对码表作一维搜索找到再沿着行对码

11、表作一维搜索找到(10101), 最后顺着所在列向上最后顺着所在列向上找出码字找出码字(10111)。n先求出伴随式先求出伴随式RHT = (010) = S4并确定并确定S4所对应的陪集首（差所对应的陪集首（差错图案）错图案）E4=(00010)，再将陪集首与收码相加得到码字，再将陪集首与收码相加得到码字C= R+ E4= (10101)+ (00010)= (10111)。 上述三种方法由上而下，查表的时间下降而所需计算量增大，上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。实际使用时可针对不同情况选用。 对上例作进一步分析，还可以看到，该对上例作进一步

12、分析，还可以看到，该(5,2)码的码的dmin=3, 纠错能力是纠错能力是t = INT(3-1)/2 = 1。因此，译码阵列中。因此，译码阵列中只有前只有前6行具有唯一性、可靠性，真正体现了最大似然译行具有唯一性、可靠性，真正体现了最大似然译码准则，而第码准则，而第7、8行的差错图案行的差错图案(00011)和和(00110)中包含两中包含两个个“1”，已超出了，已超出了t= 1的纠错能力，译码已不可靠。比如，的纠错能力，译码已不可靠。比如，当收码当收码R(10100)时，根据码表译出的码字是时，根据码表译出的码字是(10111)，与，与收码收码R的汉明距离是的汉明距离是2，然而收码，然而收

13、码R与全零码字与全零码字(00000)的汉的汉明距离也是明距离也是2，为什么不能译成，为什么不能译成(00000)呢？事实上，码表呢？事实上，码表的第的第7、8行本身就不是唯一的。注意在码表计算过程中，行本身就不是唯一的。注意在码表计算过程中，伴随式伴随式(011)所对应的所对应的4个差错图案中有两个并列重量最轻，个差错图案中有两个并列重量最轻，如果当时选的不是如果当时选的不是(00011)而是而是(10100)，那么码表第，那么码表第7行就行就不是现在这样了。不是现在这样了。 对例对例 6-3的的分析分析td=7dmin=3d=5C1C2C3C4C5min12dtINT11101000111

14、010110100102012tnkinnnnnti02tnkini1011(21)22mmnkinni例例 6.4 构造一个构造一个m=3的二元的二元(7，4)汉明码。汉明码。解：先利用汉明码的特性构造一个解：先利用汉明码的特性构造一个(7，4)汉明码的校验汉明码的校验矩阵矩阵H，再通过列置换将它变为系统形式：，再通过列置换将它变为系统形式： 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)循环码生成多项式是g(x)=x4+x3+x2+1，用式(6-3-35)产生系统循环码。解解：先以输入信息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), 对应码矢(0111010)。依次将(000)(11

16、1)代入，可得全部码矢如表6-6。此表与表6-5对比，可见码集未变而映射规则变了，表6-6满足系统循环码要求。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、相乘结果，所以的第一列相乘结果，所以G的第的第一列应去掉；一列应去掉；m3去掉，而去掉，而m3是与是与G的的第一行相乘，所以第一行相乘，所以G的第一行也去掉。的第一行也去掉。1000 10101001110010 1100001011得到新的生成矩阵为得到新的生成矩阵为 G 36原来的校验矩阵原来的校验矩阵H为为 H 37校验时，计算校验时，计算rHT，因，因r的第一位已没有，故的第一位已没有，故HT的第一的第一行应去掉，即行应去掉，即H的第一列去掉。得到新的校验矩阵的第一列去掉。得到新的校验矩阵H为为 H dmin不变，为不变，为3。 3610011101011000101111101000

18、1110101101001110100111010101001例例610 某CRC码的生成多项式 g(x)=x4+ x+1。如果想发送一串信息110001的前6位并加上CRC校验，发码应如何安排？收码又如何检验？解：解：本题信息多项式 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 于是发码C(x)= xn-k m(x) + r (x) = x9+ x8+ x4 +x3 +x2，对应的码字是 (1100011100)。 接收端的CRC校验实际上就是做除法。如果收码无误，R(x)除以g(x)应得余式0；反之，如果余式不等于零就说明一定有差错。 c0i信号入 m c1i C i 编码输出 c2i m0i m0i-1m1i m1i-1000000010200010111210 101 1gggGgg