信息论与编码理论-第3章信道容量-习题解答-071102

1、第3章信道容量 习题解答 3-1设二进制对称信道的转移概率矩阵为 2/3 1/3 1/3 2/3 解:若 P(aJ 3/4,P(a2)1/4，求 H(X), H(Y), H(X |Y), H(Y|X)和 l(X;Y)。 H(X)= P(ai )log p(aj i=1 3 311 log( )log() 0.8113(bit/ 符号) 4 444 3 2117 p(b1)=p(a1)p(b1|aj+p(a2)p(b1|Y)=H(Y)H(Y|X)=0.97990.91830.0616(bit/ 符号) H(X|Y)=H(X)I(X;Y)=0.81130.06160.7497(bit/ 符号) (

2、2)求该信道的信道容量及其达到信道容量时的输入概率分布 二进制对称信息的信道容量 H(P)= -plog(p)-(1-p)log(1-p) 1122 C=1-H(P)=1+丄log( -) + log( )=0.0817(bit/符) 3333 BSC信道达到信道容量时，输入为等概率分布，即：， 注意单位 3-4设BSC信道的转移概率矩阵为 1)写出信息熵H(Y)和条件熵H(Y|X)的关于H( 1)和H( 2)表达式，其中 H( ) log (1 )log(1 )。 2)根据 H ( )的变化曲线，定性分析信道的容道容量，并说明当 12的 信道容量。 解：(1)设输入信号的概率颁布是 p,1-

3、p p(b1) p(a1) p(b1 |a1) p(a2) p(b1 |a2) p (1 1) (1 p) 2 p(b2) p(a1) p(b2 |a1) p(a2) p(b2 |a2) p1 (1 p) (1 2) H(Y) p(b1)log p(b1) p(b2)log p(b2) p (1 1) (1 p) 2 log p (1 1) (1 p) 2 p 1 (1 p) (1 2)log p 1 (1 p) (1 2 ) Hp (1 1) (1 p) 2 H(Y|X) 2 p(ai)p(bj |ai )log p(bj |ai) i ,j 1 p (1 1)log(1 1) 1log(

4、1) (1 p)(1 2)log(1 2)2 log( 2) p H ( 1) (1 p) H( 2) (2) H ( ) 的变化曲线，是一个上凸函数，当输入等概率分布时达到信道 容量。 C mp(ax)xI(X;Y) mp(ax)x H (Y ) H(Y |X) mp(ax)x H p (1 1) (1 p) 2 p H( 1) (1 p) H ( 2) 由于函数H ()(;) (;)(;)(;)(;) 4 44444444 0.35114030.0101100110011 所以算术编码为：0100 0011 0011 平均码长及编码效率如下： i逻 16 0.8125码元/符号 H(S)

5、p(1)log p(1) p(0)log p(0)0.8113 bit/ 符号 H(S) 0.9985 l (2)由于信源符号集中共有2个元素，因此只需要 log 21位二进制数就可以表示 其编码，该符号集的编码表如下: 符号 0 1 编码 0 1 按照分段规则，分段为：1 0 11 01 111 011 0111 短语数为7,可用n log 73位来表示段号； 每个信源符号编码长度为1，所以短语长度为：3+1=4,具体编码过程如下: 盹 1=1. 段号 短语 编码 1 1 0001 2 0 0000 3 11 0011 4 01 0101 5 111 0111 6 011 1001 7 01

6、11 1101 平均编码长度： i 7 (3 1) 1.75码元/符, 16 编码效率为： H(S) 0.8113 0 4636 l 1.75 失真矩阵：d Dmin 0, R(Dmin ) 1 0 转移矩阵:p H(X) H(1/2,1/2) Iog2 1bit/符号 0 1 2 Dmaxmn J 1,2 i - min2 0 J 1,2 2 Pidj丁郞口P2dn, p2 p2d22) 此时，转移矩阵:P R(D)定义域:0, 2,1 1 0 0 1 -0 min1,1 2 j 1,22 1 彳，R(Dmax)0 1 信道编码概述 习题答案 6-2 11 极大似然译码规则译码时，由转移概率

7、矩阵可知：第一列中 1，第二列中1，第三 22 1 列中丄为转移概率的最大值，所以平均错误概率为： 2 Pe 1111111111 -( )-( )-( )- 2 3 6 4 3 6 4 3 6 2 最小错误概率译码，输入 x与输出y的联合概率分布为: 1 1 1 4612 111 24 12 111 12,24,8 11111111 E 2412824121224 由于- 242 11 24 可以看出最佳译码为最小错误概率译码，平均错误概率为 6-4 (1) 求信息传输率； f log 4 1 “口 Rbit/符号 n 2 (2) 求平均错误译码概率。 可以分成 4个子集，分别为: 根据信道

8、的传输特性，可知可以输出24=16种序列, 必1二 =(0 0 2 2) 7(0 0 y a?二 =(0 1 1 2 1 2)(0 1 y 1 1 =(1 0 2 2)(1 0 y 1 1 必4： =(1 1 )(1 1 y y 3 y 3 y 3 3 y 4) 4) 4) 4) y3,y 4 (0 i) 传输信道如下所示: (0 0 2 2) 1 1 (0 1 ) 2 2 1 1 (1 0 丄) 2 2 1 1 (1 1 ) 1 1 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

9、1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 4 44 4 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 4444 1 1 译码规则为：f(y 1,y 2,y 3,y 4)=(y 1,y 2,二,二) 2 2 i)0 i=1、2、3、4 每个码字引起错误的概率：pep( | i) p(f( r 所以 PeP( i)Pe0 C 第7章线性分组码 习题答案 1.已知一个(5, 3)线性码C的生成矩阵为:

10、1 1 0 0 1 G0 1 1 0 1 0 0 1 1 1 (1)求系统生成矩阵； (2)列出C的信息位与系统码字的映射关系； (3) 求其最小Hamming距离，并说明其检错、纠错能力； (4) 求校验矩阵H; (5) 列出译码表，求收到 r=11101时的译码步骤与译码结果。 解： (1)线性码C的生成矩阵经如下行变换： 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 将第2、3加到第1行 0 1 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 将第劝卩到第2行 0 1 0 1 0 0 0 1 1 1 0 0 1

11、 1 1 得到线性码C的系统生成矩阵为 1 0 0 1 1 Gs 0 1 0 1 0 0 0 1 1 1 (2)码字c (Co，Ci， ,Cn 1)的编码函数为 c f (m) mo 1 0 0 1 1 mi 0 1 0 1 0 m2 0 0 1 1 1 生成了的8个码字如下 信息元 系统码字 000 00000 001 00111 010 01010 011 01101 100 10011 101 10100 110 11001 111 11110 (3) 最小汉明距离d=2，所以可检1个错，但不能纠错。 由 G In k,Ak (n k),H Ak (n J,ln k，得校验矩阵 1111

12、0 H 10 10 1 (5)消息序列 m=000,001,010,011,100,101,110,111，由 c=mGs 得码字序列 co=OOOOO, c1=00111, c2=01010, c3=01101, C4=10011, C5=10100, C6=11001, C7=11110 则译码表如下： 00000 00111 01010 01101 10011 10100 11001 11110 10000 101111 11010 11101 00011 r00100 01001 01110： 01000 01111 00010 00101 11011 11100 10001 1011

13、0 00001 00110 01011 01100 10010 10101 11000 11111： 当接收到r =(11101)时，查找码表发现它所在的列的子集头为(01101)，所以将它 译为 c=01101。 2 设(7, 3)线性码的生成矩阵如下 0 10 10 10 G 0 010111 10 0 110 1 (1) 求系统生成矩阵； (2) 求校验矩阵； (3) 求最小汉明距离； (4) 列出伴随式表。 解： (1)生成矩阵G经如下行变换 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 1 1 1 交换第1、行0 1 0 0 1 1

14、0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 1 交换第2、3行 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 得到系统生成矩阵: 1 0 0 1 1 0 1 Gs0 1 0 1 0 1 0 0 0 1 0 1 1 1 110 10 0 0 10 10 10 0 H 0 110 0 10 1 0 1 0 0 0 1 （3） 由于校验矩阵 H的任意两列线性无关，3列则线性相关，所以最小汉明距离 d=3。 （4） （7, 3）线性码的消息序列m=000,001,010,011,100,101,1

15、10,111，由 c=mGs 得码 字序列：cc=0000000，c1=0010111，c2=0101010，c3=0111101，c4=1001101, c5=1011010， C6=1100111, C7=1110000。又因伴随式有24=16种组合，差错图样为1的有 77种， 1 7tT T 差错图样为 2的有21种，而由HrT HeT，则计算陪集首的伴随式，构造伴 2 随表如下： 伴随式 陪集首 伴随式 陪集首 0000 0000000 0101 1001000 1101 1000000 1001 1000100 1010 0100000 1111 0011000 0111 00100

16、00 1100 0001100 1000 0001000 1110 0100100 0100 0000100 1011 0100001 0010 0000010 0011 0010100 0001 0000001 0110 0000110 3 .已知一个（6, 3）线性码C的生成矩阵为： 10 0 10 1 G0 10 0 11 0 0 1110 （1）写出它所对应的监督矩阵 H; （2）求消息M=（101）的码字； （3） 若收到码字为101010，计算伴随式，并求最有可能的发送码字。 解： （1）线性码C的生成矩阵G就是其系统生成矩阵 Gs,所以其监督矩阵 H直接得出: 10 110 0

17、H 011010 1 1 0 0 0 1 (2)消息 M=(m,mi,m2)=(101),则码字 c 为: c f (m) 10 0 10 1 0 0 1 1 1 0 10 10 11 (3)收到码字 r=(101010)，则伴随式 1 0 1 0 1 1 1 1 0 rHT 101010 g 001 1 0 0 0 1 0 0 0 1 又( 6, 3) 线性码的消息序列m=000,001,010,011,100,101,110,111，由 c=mGs 得 码字序列：co=000000, C1=001110, C2=010011 , C3=011101, C4=100101 , C5=1010

18、11 , C6=110110, C7=111OOO。伴随式有23=8种情况，则计算伴随式得到伴随表如下： 伴随式 陪集首 000 000000 101 100000 011 010000 110 001000 100 000100 010 000010 001 000001 111 100010 伴随式(001)对应陪集首为(000001)，而c=r+e，则由收到的码字 r=(101010)， 最有可能发送的码字c为：c=( 101011 )。 4 设(6, 3)线性码的信息元序列为X1X2X3，它满足如下监督方程组 X1 X2 X4 0 X2 X3 X5 0 X1 X3 X6 0 (1) 求校验矩阵，并校验 10110是否为一个码字； (2) 求生成矩阵，并