信息论与编码zjh201209第6章信道编码

1、1普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著3普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著4普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著6普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著7普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著8普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著9普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著01(1)(,),iiiiji nijVV

2、 VVVVF10普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著12,ikVVVV及1 122,()kiiiVaVa VaVaF1 1220,()iiiaVa VaVaF且不全为零11普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著12,nV VV12普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著1(000),(100)V2(000),(001),(010),(011)V13普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著14普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 消息消息k长长 (n , k) 码字码字n长长 qk 种种

3、 分组编码器分组编码器 qn种种 k维维k重矢量重矢量 n维维n重矢量重矢量 通常通常qn qk，分组编码的任务是，分组编码的任务是要在要在n维维n重矢量空间的重矢量空间的qn种可能组合种可能组合中选择其中的中选择其中的qk个构成一个个构成一个码空间码空间，其元素就是许用码的其元素就是许用码的码集码集。 15普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著16普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著17普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著()( )NMmPqc11( ) ( )( )NMNMqqNMeemmemmmPPPqPccc18普通

4、高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著11( ) ( )( )NMNMqqNMeemmemmmPPPqPccc( )emePPc( )emePPc0eP ( )0emPc19普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著eP0eP 20普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著()NE RePe21普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 E(R) C R 0 R0 -45 E(R)和和R的关系曲线的关系曲线22普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著23普通高等教育“十五”国家级规划教材信息论与编码 曹

5、雪虹等编著24普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著E(R) R0 R1 R2 C1 C2 增大增大E(R)的途径的途径()NE RePe25普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著26普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著12(,)NiiiiNc cccX27普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 消息组消息组mi 码字码字ci 接收码接收码r 估值估值 消息消息 icim编码器编码器 信道信道 译码译码 消息还原消息还原max (/ )iiPcc rmax( /)iiPcr c28普通高等教育“十五”国家

6、级规划教材信息论与编码 曹雪虹等编著()(/)(/),1,2,2( )KiiiPPPiPcrccrr29普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著1( /)(/)NijijjMaxPMaxP rcr c30普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 消息消息m (n , k) 码字码字c m=(mk-1,m1,m0) 分组编码器分组编码器 c=(cn-1,c1,c0) qk qn31普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著32普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著33普通高等教育“十五”国家级规划教材信息论与编码 曹

7、雪虹等编著34普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著(1)(1)(1)1(1)01(1)11100(1)01001000100001kn kkkn kn kppppppppp 35普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著36普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著37普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 n维维n重空间重空间V k维维k重重 k维维n重重 n-k维维 信息组信息组 码空间码空间 n重重H 空间空间m C38普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著39普通高等教育“十五”国家

8、级规划教材信息论与编码 曹雪虹等编著1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 40普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著码集与映射关系码集与映射关系信息 码字 系统码字000 000000 00000000101110100101101011000101011001110110001110110011101010011110110011110110011000101111000111101011011101041普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著二元二元(6,3)线性分组码编码器线性分组码编码器 m0m1m2 输入

9、输出 c0c1c242普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著43普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 44普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著45普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著(1)(1)(1)1(1)01(1)11100(1)0100Tn knn kn knnhhhhhhhhh 46普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著47普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著依据：依据：若若BSC信道的差错概率是信道的差错概率是p，则长度，则长度n的码中错误概率的

10、码中错误概率 ： 0个错个错 1个错个错 2个错个错 n个错个错 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn 由于由于p 出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻，的重量越轻，所以该译码方法实际上体现了最小距离译码准则，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。即最大似然译码。48普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著49普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2n2n50普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著S0 E0S1 E1 Sj Ej E0+C0= 0+0

11、= 0E0+C1= C1E0+Ci= CiE1+C0= E1 E1+Ci Ej+C0= EjEj+C1Ej+Ci 标准阵列译码表标准阵列译码表 E1+C1 11022n kn k ECE1122n kn k SE112n k EC12n ki EC1221n kk EC21kjEC121kEC02121kkECC51普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著52普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例 6-3 一个一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是G = 设收码设收码R = (10101)，构造标准阵列译码表，译出发码的估值，构

12、造标准阵列译码表，译出发码的估值解：解：(1)构造标准阵列译码表。分别以信息组构造标准阵列译码表。分别以信息组m= (00)、(01) 、(10)、(11)及已知的及已知的G求得求得4个许用码字为个许用码字为C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。求出校验矩阵：求出校验矩阵： H = PT I3 = 列出方程组：列出方程组：1011011101ic 242322212014131211100403020100111001001011001hhhhhhhhhhhhhhh24243232221 2102043214 143 132 1

13、21 110 104104043 032021 01000430se he he he he heeese he he he he heese he he he he heee53普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著伴随式有伴随式有2n-k238种组合，差错图案中代表无差错的有种组合，差错图案中代表无差错的有一种，代表一个差错的图案有一种，代表一个差错的图案有 种，已有种，已有6种。种。代表两个差错的图案有代表两个差错的图案有 种。只需挑选其中的两个，种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。先将挑选方法可有若干种，不是唯一的。先将Ej=(00000)、(

14、10000)、(01000)、(00100)、(00010)、(00001)代入上面的代入上面的线性方程组，解得对应的线性方程组，解得对应的Sj分别是分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，。剩下的伴随式中，(011)所对应的差所对应的差错图案是错图案是2k个即个即(00011)、(10100)、(01110)、(11001),其中其中(00011)和和(10100)并列重量最轻，任选其中一个如并列重量最轻，任选其中一个如(00011)。同样可得伴随式同样可得伴随式(110)所对应的最轻差错图案之一是所对应的最轻差错图案之一是(00110)

15、。 551 5102 例例 6-3 译码表的构成译码表的构成54普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101

16、111100例例 6-3 标准阵列译码表标准阵列译码表55普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例 6-3 将接收码将接收码R10101译码译码 可选以下三种方法之一译码：可选以下三种方法之一译码：n直接搜索码表，查得直接搜索码表，查得(10101)所在列的子集头是所在列的子集头是(10111)，因此译，因此译码输出取为码输出取为(10111)。n先求伴随式先求伴随式RHT = (10101) HT = (010) = S4，确定，确定S4所在行，所在行，再沿着行对码表作一维搜索找到再沿着行对码表作一维搜索找到(10101), 最后顺着所在列向上最后顺着所在列向上找出码

17、字找出码字(10111)。n先求出伴随式先求出伴随式RHT = (010) = S4并确定并确定S4所对应的陪集首（差所对应的陪集首（差错图案）错图案）E4=(00010)，再将陪集首与收码相加得到码字，再将陪集首与收码相加得到码字C= R+ E4= (10101)+ (00010)= (10111)。 上述三种方法由上而下，查表的时间下降而所需计算量增大，上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。实际使用时可针对不同情况选用。56普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 对上例作进一步分析，还可以看到，该对上例作进一步分析，还可以

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

19、字与全零码字(00000)的汉的汉明距离也是明距离也是2，为什么不能译成，为什么不能译成(00000)呢？事实上，码表呢？事实上，码表的第的第7、8行本身就不是唯一的。注意在码表计算过程中，行本身就不是唯一的。注意在码表计算过程中，伴随式伴随式(011)所对应的所对应的4个差错图案中有两个并列重量最轻，个差错图案中有两个并列重量最轻，如果当时选的不是如果当时选的不是(00011)而是而是(10100)，那么码表第，那么码表第7行就行就不是现在这样了。不是现在这样了。 对例对例 6-3的的分析分析57普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著58普通高等教育“十五”国家级规划教

20、材信息论与编码 曹雪虹等编著td=7dmin=3d=5C1C2C3C4C559普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著min12dtINT60普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著61普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著11101000111010110100162普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著63普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著02012tnkinnnnnti64普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著02tnkini65普通高等教育“十五”国家级规

21、划教材信息论与编码 曹雪虹等编著1011(21)22mmnkinni66普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著67普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例 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

22、 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 68普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著232323112369普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著70普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著71普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著72普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著73普通高等教育“十五”国家级规划教材信息论与编码

23、 曹雪虹等编著74普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著75普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著76普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著77普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著78普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著79普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著80普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例6.6 (7,3)循环码生成多项式是g(x)=x4+x3+x2+1，用式(6-3-35)产生系统循环码。解解：先以输入信息m=(011

24、)即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)(111)代入，可得全部码矢如表6-6。此表与表6-5对比，可见码集未变而映射规则变了，表6-6满足系统循环码要求。81普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著0001111 H82普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著83普通高等教育“十

25、五”国家级规划教材信息论与编码 曹雪虹等编著例：例：(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的第一列相乘结果，所以的第一列相乘结果，所以G的第的第一列应去掉；一列应去掉；m3去掉，而去

26、掉，而m3是与是与G的的第一行相乘，所以第一行相乘，所以G的第一行也去掉。的第一行也去掉。1000 10101001110010 110000101184普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著得到新的生成矩阵为得到新的生成矩阵为 G 36原来的校验矩阵原来的校验矩阵H为为 H 37校验时，计算校验时，计算rHT，因，因r的第一位已没有，故的第一位已没有，故HT的第一的第一行应去掉，即行应去掉，即H的第一列去掉。得到新的校验矩阵的第一列去掉。得到新的校验矩阵H为为 H dmin不变，为不变，为3。 36100111010110001011111010001110101101

27、00111010011101010100185普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著86普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著例例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+ x

28、8+ 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；反之，如果余式不等于零就说明一定有差错。 87普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著88普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著89普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著90普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 c0i信号入 m c1i C

29、 i 编码输出 c2i m0i m0i-1m1i m1i-1000000010200010111210 101 1gggGggg11110001021111011121 111 00gggGggg91普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著1 0 10 1 11 1 11 0 092普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著0Ll93普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著00010(1)10111(1)(1)0(1)1(1)(1)()()()()()()()()()NNKKKNgDgDgDgDgDgDgDgDgD11( )11D DDDDG0Ll94普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 c0i 信号入 m c1i 输出C i c2im0i m0i-1 m0i-295普通高等教育“十五”国