信息论与编码理论

1、第3章信道容量习题解答3-1设二进制对称信道的转移概率矩阵为2/3 1/31/3 2/3解：(1) 若 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(aji=13 311log( )log() 0.8113(bit/ 符号)4 4443 2117p(b1)=p(a1)p(b1|aj+p(a2)p(b1|&)=4 3 4 3123 1125p(b2)=p(a1)p(b2|aj+p(a2)p(b2|a2)=4 3 4 312H(Y)=p(bj)log(bj)=j=10.9799(bit/

2、 符号)22H(Y|X)=p(q ,bj)logp(bj|ajp(bj|aj)logp(bj|aji,jjI log(|) 1 log(1) 0.9183(bit/符号)I(X;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)求该信道的信道容量及其达到信道容量时的输入概率分布二进制对称信息的信道容量H(P)= -plog(p)-(1-p)log(1-p)1122C=1-H(P)=1+丄log( -) + log( )=0.0817(bit/符)3333BSC言道达到

3、信道容量时，输入为等概率分布，即：0.5，0.5注意单位3-4设BSC信道的转移概率矩阵为1)写出信息熵H(Y)和条件熵H(Y|X)的关于H( 1)和H( 2)表达式，其中H( ) log (1 )log(1 )。2)根据 H ( )的变化曲线，定性分析信道的容道容量，并说明当 12的信道容量。解：(1)设输入信号的概率颁布是 p,1-pp(b1)p(a1)p(b1 |a1)p(a2)(b1 |a2)p (11)(1 p) 2p(b2)p(a1)p(b2 |a1)p(a2)p(b2 |a2)p1(1p) (1 2)H(Y)p(b1)log p(b1)p(b2)logp(b2)p(1 1) (1

4、 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)2H(Y|X)2p(ai)p(bj |ai )logp(bj |ai)i ,j 1p (1 1)log(11) 1log( 1)(1 p)(1 2)log(12) 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 (

5、 2) 由于函数H (& )是一个凸函数，有一个性质：f ( 1 (1 ) 2) f( 1) (1 ) f( 2)可知：C假设12 时此信道是一个二元对称信道，转移概率分布为：1 Q1信道容量：1 2C 1- log -(1- )log(1-)1-H()3-10电视图像由30万个像素组成，对于适当的对比度，一个像素可取 10 个可辨别的亮度电平，假设各个像素的10个亮度电平都以等概率出现，实 时传送电视图像每秒发送30帧图像。为了获得满意的图像质量，要求信号 与噪声的平均功率比值为30dB,试计算在这些条件下传送电视的视频信号 所需的带宽。解：I (X) log103.32bit/ 像

6、素1秒可以传送的信息量为：3.3219bit/ 像素 30 10000像 素 30=2.9897 107bitC Blog(1 善),已知:10log1°(善)30dB1032.9897 107Blog(1 103)可得：B 2.9995 106HZ3-11 一通信系统通过波形信道传送信息，信道受双边功率谱密度N°/20.5 10 8 W/Z Hz的加性高斯白噪声的干扰，信息传输速率R 24 kbit/s，信号功率 P 1W1)若信道带宽无约束，求信道容量；解：带限的加性高斯白噪声波形信道的信道容量为无带宽约束时:PS N0WPSC lim Ct limlog（1 ）ww

7、No FSNoW昱 loge 1.4427 108bit/sNo2）若信道的频率围为 0到3KHz求信道容量和系统的频带利用率 R/W （bps/Hz）（注：W为系统带宽）；对同样的频带利用率，保证系统可靠传 输所需的最小Eb/N。是多少dB?W=3KHZ在最大信息速率条件下，每传输1比特信息所需的信号能量记为&Eb=CSC W log(1_FLN0WWlog(1SNR)3000 log(11 10 83000)4.5074 104bps24kbit/s3KHz8bps/Hz33.47dBFs1N。3）若信道带宽变为N0C 1 10 8 4.5074 104 100KHz欲保持与2）相

8、同的信道容量，则此时的信噪比为多少dB？信号功率要变化多数dB?W 100KHZ4.5074 104bps Wlog(1 电)105log(1笙)N0WN0WSNR -F0.3667即:4.3654dBN°WFs' 0.3667 105 10 80.3667 10 3w信号功率的变化为:Fs'0.3667 10 310log1° 亠 10log1°34.3569dBFs1第4章无失真信源编码习题参考答案4-1 :611111IaP(Si )li3(- -i 12416 161661111lBP(Si )li123i 1241616符号61111lC

9、P(Si)li123i 1241616符号61111IeP(Si)li12(-i 1241616(1) A、B、C E编码是唯一可译码。(2) A、C E码是及时码。(3)唯一可译码的平均码长如下:4-3 :(1)1丄)3码元/信源符号16114 丄5 丄 62.125码元/信源161611一4562.125码元/信源16161 11) 42码元/信源符号6 168H(X)=- p(x i)logp(x i)i=111 11 1=-_log - log - log22 44 81111 ,1- log - log - 8 1616 323211 11- log - log 6464 12812

10、81log1281128平均码长：_ 6lP(s)hi 11111118163264128128)3码元/信源符号所以编码效率:H(X)0.6615(3)仙农编码:信源符号Si符号概率p(Si)加概率码长码字Si10102S21121042S313311084S41741110168115S55111103216S613161111106432S716371111110128641127S871111111128128费诺码:信源符号Si符号概率p(Si)编码码字码长S112001S2140102S31801103S4丄16011104S5132110111105S6丄641101111106

11、S7112811011111107S811281111111174-5 :(1)霍夫曼编码：对X的霍夫曼编码如下:信符号编码过程码长码源 符 号Si概率p(Si)字S0.20.2叩.26JF0.350.39J0.6101020.190.190.20.26y6.350声91112S0.180.180.190.20 i/ 0.2610003S0.170.1710.18!00.1910013S0.150.1500.1710103S60.100 #.0.11101104S0.01101114l 0.2 20.19 20.183 0.17 3 0.15 3 0.1 4 0.01 42.72 码元 /信源

12、符号7H(X)i 1Pi log Pi2.61码元/符号H(X)2.610.9596l2.72Y的二元霍夫曼编码:信 源 符 号Si符号 概率P(Si)编码过程码字码 长S10.49丿0.490.490.490.49/0.490.49.0.51011S20.140.140.140.140.1410.230.280.4910003S30.140.140.140.140.140.14 /0.2310013S40.070.070.070.09f,0.140.14101004S50.070.070.07/r 0.07 丄0.09101014S60.040.0490500.07101114S70.02胃

13、0.03/00.041011015S80.0200.0210110006S90.0110110016平均码长:r 0.49 10.14 3 2 0.07 4 2 0.04 4 0.02 5 0.02 6 0.01 62.23码元/信源符9H(Y) Pi log Pi 2.31 码元 / 符号i 1H (Y)2.31编码效率：0.9914l 2.33仙农编码：对X的仙农编码:信源符号S符号概率P(Si)和概率码长码字S0.203000S0.190.23001S30180.393011S40.170.573100S50.150.743101S60.100.8941110S70.010.997111

14、1110平均码长:l 0.2 3 0.19 3 0.18 3 0.17 3 0.15 3 0.1 4 0.01 73.14码兀/信源符H(X)l2.613.140.8312对Y的仙农编码:信源符号S符号概率P(Si)和概率码长码字S10.490200S20.140.493011S30.140.633101S40.070.7741100S50.070.8441101S60.040.91511101S70.020.956111100S80.020.976111110S90.010.9971111110平均编码长度:l 0.49 2 0.14 2 0.07 4 2 0.04 5 0.02 6 2 0

15、.02 6 0.01 72.89码元/信源符H(Y) 2.31编码效率：一0 7993l 2.89费诺编码：对X的费诺编码:信源符号Si符号概率p(Si)编码码字码长S10.200002S20.19100103S30.1810113S40.170102S50.15101103S60.1011011104S70.01111114平均编码长度:l 0.2 2 0.19 3 0.18 3 0.17 2 0.15 3 0.1 4 0.01 42.74码元/信源符号编码效率：261 0.9526l 2.74对Y进行费诺编码:信源符号Si符号概率p(Si)编码码字码长S10.49001S20.140010

16、03S30.1411013S40.070011004S50.071111014S60.041011104S70.0210111105S80.021101111106S90.0111111116平均码长:l 0.49 10.14 2 3 0.07 4 2 0.04 4 0.02 5 0.02 6 0.01 62.33码元/信源符号编码效率:H(Y) 2.310.9914l 2.33(4)由三种编码的编码效率可知：仙农编码的编码效率为最低，平均码长最长；霍夫曼编码的编码长度最短，编码 效率最高，费诺码居中。4-7 : 由三元编码方式可知：R=t> B=R-i(K 2)+2由本题可知D=3,

17、K=8, R=2,所以，首先合并最后两个信源概率，其中一种编码 方式如下：信源符号S符号概率p(Si)编码码字码 长S10.40.40.40.4001S20.20.20.2*0.4121S30.10.1.0.2厂0.22112S40.10.1/0.1彳122S50.05,0.1/0.121013S60.05/ 0.05f11023S0.050?0.05210004S80.051100144-21 :(1)符号概率分布区间00.250,0.2510.750.25,1由题目可知信源符号为:1011 0111 1011 0111p(s 1011 0111 1011 01110.00012371243

18、 12 1 4p(1) p(0) (3)G算术码的码长丨 log p(s)13由序列S的分布函数F( S)由二元整树图来计算：F(S) 13 23厶13 8 12310 13312 141 (：)(：) (；)(：)(；)(；)(；)4 44444444所以算术编码为：0100 0011 0011平均码长及编码效率如下:1空160.8125码元/符号H(S)p(1)log p(1) p(0)log p(0)0.8113 bit/ 符号H(S) 0.9985l(2)由于信源符号集中共有 2个元素，因此只需要log 21位二进制数就可以表示其编码，该符号集的编码表如下:符号01编码01按照分段规则

19、，分段为：1 0 11 01 111 011 0111短语数为7,可用n log 73位来表示段号；每个信源符号编码长度为1，所以短语长度为：3+1=4,具体编码过程如下:盹 1=1. 段号短语编码110001200000311001140101015111011160111001701111101平均编码长度：i 7 (31)1.75码元/符16编码效率为：H(S)0.8113 0 46361.755.21失真矩阵：d020p2d22)-2Dmin O,R(Dmin) H(X) H(1/2,1/2) log2 1bit/符号转移矩阵:p2Dmax mnPidjPzd?" p

20、9;2j 1,2 i 1j 1,21 0m1n2 0此时，转移矩阵:P0 1，R(Dmax)01R(D)定义域:0,-第6章信道编码概述习题答案6-211极大似然译码规则译码时，由转移概率矩阵可知：第一列中1，第二列中1，第三221列中丄为转移概率的最大值，所以平均错误概率为:2Pe1 (1 丄)2 3 61)1 (16431)最小错误概率译码，输入 x与输出y的联合概率分布为:1 1 14'61211124® 1211112,24,811111111E 2412824121224由工111由于-1124242可以看出最佳译码为最小错误概率译码，平均错误概率为6-4(1) 求

21、信息传输率；f log 4 1 “口Rbit/符号2根据信道的传输特性，可知可以输出24=16种序列，可以分成 4个子集，分别为:a1=(0 0a2=(0 1a3=(1 0a4=(1 11 1)一(0 0 y2 21 1-)-(0 1 y2 21 1)(1 0 y2 2)1) - (1 1 y3 y 4)3 y 4)3 y 4)3 y 4)y3,y 4 (0 1)传输信道如下所示:(0 0(0 1(1 0(1 112)1)1)0000 00010010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 11111111000

22、 0 0 000 000 04444000011 1100 000 0 00444411110000000000 0 044441111000000000 0 0 044441 1译码规则为：f(y 1,y 2,y 3,y 4)=(y 1,y 2,二,二)i)0 i=1、2、3、42 2每个码字引起错误的概率：pep( | i) p(f(r所以PeP( i)Pe 0C第7章线性分组码习题答案1.已知一个(5, 3)线性码C的生成矩阵为:11001G0110100111(1)求系统生成矩阵；(2)列出C的信息位与系统码字的映射关系；(3) 求其最小Hamming距离，并说明其检错、纠错能力；(4

23、) 求校验矩阵H;(5) 列出译码表，求收到 r=11101时的译码步骤与译码结果。解：(1)线性码C的生成矩阵经如下行变换：110011001101101将第2、3加到第1行011010011100111100111001101101将第劝卩到第2行010100011100111得到线性码C的系统生成矩阵为10011Gs0101000111(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个码字如下信息元系统码字000000000010011101001010011011011001

24、0011101101001101100111111110(3) 最小汉明距离d=2，所以可检1个错，但不能纠错。(4) 由 G In k，Ak (n k)，H Ak(nk)T，ln k】，得校验矩阵11110H10 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则译码表如下：00000001110101001101100111010011001111101000010

25、11111010111010001100100010010111001000011110001000101110111110010001101100000100110010110110010010101011100011111当接收到r =（11101）时，查找码表发现它所在的列的子集头为（01101）,它译为C=01101。2 设（7, 3 ）线性码的生成矩阵如下0101010G 00101111001101（1）求系统生成矩阵；（2）求校验矩阵；（3）求最小汉明距离；（4）列出伴随式表。解：（1）生成矩阵G经如下行变换010101010011010010111交换第1、行001011110

26、011010101010100110110011010010111交换第2、行°10101001010100010111得到系统生成矩阵:1001101Gs01010100010111 由 G In k，Ak（n k），H Ak （n k）T,ln k，得校验矩阵为110 10 0 010 10 10 0 H0 110 0 101 0 1 0 0 0 1(3) 由于校验矩阵 H的任意两列线性无关，3列则线性相关，所以最小汉明距离 d=3。(4) (7, 3)线性码的消息序列mF000,001,010,011,100,101,110,111，由 c=mGs得码字序列：6=0000000

27、, C1=0010111，C2=0101010，C3=0111101, C4=1001101, c5=1011010，C6=1100111, C7=1110000。又因伴随式有24=16种组合，差错图样为1的有77种，17tT T差错图样为 2的有21种，而由HrT HeT，则计算陪集首的伴随式，构造伴2随表如下：伴随式陪集首伴随式陪集首000000000000101100100011011000000100110001001010010000011110011000011100100001100000110010000001000111001001000100000010010110100001001000000100011001010000010000001011000001103 .已知一个(6, 3)线性码C的生成矩阵为:100101G010011 .001110(1)写出它所对应的监督矩阵H；