复旦 周小林 信息论 6.信道编码

1、1 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 Viterbi, CDMA之父之父 Berrou and Forney Gallager 6 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 7 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 8 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 9 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 10 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 11 普通高等教育“十五”国家级规划教材信息论

2、与编码 曹雪虹等编著 12 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 01(1) (,), iiiiji nij VV VVVVF 13 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 12 , ik VVVV及 1 122 ,() kiii VaVa VaVaF 1 122 0,() iii aVa VaVaF且不全为零 14 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 12 , n V VV 15 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 1 (000),(100)V 2 (000),(001),(010),(011)

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

4、五”国家级规划教材信息论与编码 曹雪虹等编著 20 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 () ( ) NM m Pq c 11 ( ) ( )( ) NMNM qq NM eemmem mm PPPqP ccc 21 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 11 ( ) ( )( ) NMNM qq NM eemmem mm PPPqP ccc ( ) eme PPc ( ) eme PPc 0 e P ( )0 em Pc 22 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 e P 0 e P 23 普通高等教育“十五”国家级规

5、划教材信息论与编码 曹雪虹等编著 ()NE R e Pe 24 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 E(R) C R 0 R0 -45 E(R)和和R的关系曲线的关系曲线 25 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 26 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 27 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 E(R) R 0 R1 R2 C1 C2 增大增大E(R)的途径的途径 ()NE R e Pe 28 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 29 普通高等教育“十五”国家级规

6、划教材信息论与编码 曹雪虹等编著 12 (,) N iiiiN c cccX 30 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 消息组消息组mi 码字码字ci 接收码接收码r 估值估值 消息消息 ic i m 编码器编码器 信道信道 译码译码 消息还原消息还原 max (/ ) ii Pcc r max( /) ii Pcr c 31 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 ()(/) (/),1,2,2 ( ) K ii i PP Pi P crc cr r 32 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 1 ( /)(/) N i

7、jij j MaxPMaxP rc r c 33 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 消息消息m (n , k) 码字码字c m=(mk-1,m1,m0) 分组编码器分组编码器 c=(cn-1,c1,c0) qk qn 34 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 35 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 36 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 37 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 (1)(1)(1)1(1)0 1(1)1110 0(1)0100 100 010

8、0001 kn kkk n k n k ppp ppp ppp 38 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 39 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 40 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 n维维n重空间重空间V k维维k重重 k维维n重重 n-k维维 信息组信息组 码空间码空间 n重重H 空间空间m C 41 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 42 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 43

9、普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 信息 码字 系统码字 000 000000 000000 001011101001011 010110001010110 011101100011101 100111010100111 101100111101100 110001011110001 111010110111010 44 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 m0m1m2 输入 输出 c0c1c2 45 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 46 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 47 普通高

10、等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 48 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 (1)(1)(1)1(1)0 1(1)1110 0(1)0100 T n knn kn k n n hhh hhh hhh 49 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 50 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 依据：依据：若若BSC信道的差错概率是信道的差错概率是p，则长度，则长度n 的码中错误概率的码中错误概率 ： 0个错个错 1个错个错 2个错个错 n个错个错 (1-p)n p(1-p)n-1 p2(1-p)n-2 p

11、n 由于由于p 出错越少的情况，发生概率越大，出错越少的情况，发生概率越大，E的重量越轻，的重量越轻， 所以该译码方法实际上体现了最小距离译码准则，所以该译码方法实际上体现了最小距离译码准则， 即最大似然译码。即最大似然译码。 51 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 52 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 2 n 2 n 53 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 S0 E0 S1 E1 Sj Ej E0+C0= 0+0= 0 E0+C1= C1 E0+Ci= Ci E1+C0= E1 E1+Ci Ej+C0= E

12、jEj+C1Ej+Ci 标准阵列译码表标准阵列译码表 E1+C1 1 1 0 2 2 n k n k EC E 11 22 n kn k SE 1 1 2n k EC 1 2n k i EC 1 221 n kk EC 21 k j EC 1 21 k EC 0 2121 kk ECC 54 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 55 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 例例 6-3 一个一个(5,2)系统线性码的生成矩阵是系统线性码的生成矩阵是G = 设收码设收码R = (10101)，构造标准阵列译码表，译出发码的估值，构造标准阵列译码表，

13、译出发码的估值 解：解：(1)构造标准阵列译码表。分别以信息组构造标准阵列译码表。分别以信息组m= (00)、(01) 、 (10)、(11)及已知的及已知的G求得求得4个许用码字为个许用码字为 C1 =(00000)、C2 = (10111) 、C3 = (01101)、C4 = (11010)。 求出校验矩阵：求出校验矩阵： H = PT I3 = 列出方程组：列出方程组： 10110 11101 i c 2423222120 1413121110 0403020100 11100 10010 11001 hhhhh hhhhh hhhhh 24243 232221 21020432 14

14、 143 132 121 110 1041 04043 032021 01000430 se he he hehe heee se he he hehe hee se he he hehe heee 56 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 伴随式有伴随式有2n-k238种组合，差错图案中代表无差错的有种组合，差错图案中代表无差错的有 一种，代表一个差错的图案有一种，代表一个差错的图案有 种，已有种，已有6种。种。 代表两个差错的图案有代表两个差错的图案有 种。只需挑选其中的两个，种。只需挑选其中的两个， 挑选方法可有若干种，不是唯一的。先将挑选方法可有若干种，不是唯

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

16、之一是所对应的最轻差错图案之一是(00110)。 5 5 1 5 10 2 例例 6-3 译码表的构成译码表的构成 57 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 S0=000E0+C0=00000C1=10111C2=01101C3=11010 S1=111E1=10000001111110101010 S2=101E2=01000111110010110010 S3=100E3=00100100110100111110 S4=010E4=00010101010111111000 S5=001E5=00001101100110011011 S6=011E6=0001110

17、1000111011001 S7=110E7=00110100010101111100 例例 6-3 标准阵列译码表标准阵列译码表 58 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 59 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 对上例作进一步分析，还可以看到，该对上例作进一步分析，还可以看到，该(5,2)码的码的 dmin=3, 纠错能力是纠错能力是t = INT(3-1)/2 = 1。因此，译码阵列中。因此，译码阵列中 只有前只有前6行具有唯一性、可靠性，真正体现了最大似然译行具有唯一性、可靠性，真正体现了最大似然译 码准则，而第码准则，而第7、8行的

18、差错图案行的差错图案(00011)和和(00110)中包含两中包含两 个个“1”，已超出了，已超出了t= 1的纠错能力，译码已不可靠。比如，的纠错能力，译码已不可靠。比如， 当收码当收码R(10100)时，根据码表译出的码字是时，根据码表译出的码字是(10111)，与，与 收码收码R的汉明距离是的汉明距离是2，然而收码，然而收码R与全零码字与全零码字(00000)的汉的汉 明距离也是明距离也是2，为什么不能译成，为什么不能译成(00000)呢？事实上，码表呢？事实上，码表 的第的第7、8行本身就不是唯一的。注意在码表计算过程中，行本身就不是唯一的。注意在码表计算过程中， 伴随式伴随式(011)

19、所对应的所对应的4个差错图案中有两个并列重量最轻，个差错图案中有两个并列重量最轻， 如果当时选的不是如果当时选的不是(00011)而是而是(10100)，那么码表第，那么码表第7行就行就 不是现在这样了。不是现在这样了。 对例对例 6-3的的分析分析 60 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 61 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 t d=7 dmin=3 d=5 C1 C2 C3 C4 C5 62 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 min 1 2 d tINT 63 普通高等教育“十五”国家级规划教材信息论与编

20、码 曹雪虹等编著 64 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 1110100 0111010 1101001 65 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 66 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 0 2 012 t nk i nnnnn ti 67 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 0 2 t nk i n i 68 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 1 0 11(21)22 mmnk i n n i 69 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编

21、著 70 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 例例 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 1 0 1 G = I4

22、P = 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 71 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 232323 1 123 72 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 73 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 74 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 75 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 76 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 77 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 202

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

24、为例， . 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满足系统循 环码要求。 85 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 0 0 0 1111 H 86 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 87 普通高等教育“十五

25、”国家级规划教材信息论与编码 曹雪虹等编著 例：例：(7,4)码的生成矩阵为码的生成矩阵为 47 1000 101 0100111 0010 110 0001011 m3m2m1 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的第的第 一列应去掉；一列应去掉；m

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

27、11 1110100 0111010 1101001 110100 111010 101001 89 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 90 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 例例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(

28、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；反之，如果余式不等于零就说明一 定有差错。 91 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 92 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 93 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 94

29、普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 c0i 信号入 m c1i C i 编码输出 c2i m0i m0i-1 m1i m1i-1 000 0000102 000 101112 10 1 01 1 ggg G ggg 111 1000102 111 101112 1 11 1 00 ggg G ggg 95 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 1 0 1 0 1 1 1 1 1 1 0 0 96 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 0 L l 97 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 00010(1) 10111(1) (1)0(1)1(1)(1) ()()() ()()() ()()() N N KKKN gDgDgD gDgDgD gDgDgD 11 ( ) 11 D DD D D G 0 L l 98 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 c0i 信号入 m c1i 输出C i c2i m0i m0i-1 m0i-2 99 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著 0/000 S0 1/111 0/001 1/110 S2 S1 0/011 1/100