信息与编码理论课后习题答案

1、2.1 莫尔斯电报系统中，若采用点长为0.2s，1划长为0.4s，且点和划出现的概率分别为2/3和1/3，试求它的信息速率(bits/s)。解: 平均每个符号长为:秒 每个符号的熵为比特/符号所以，信息速率为比特/秒2.2 一个8元编码系统，其码长为3，每个码字的第一个符号都相同(用于同步)，若每秒产生1000个码字，试求其信息速率(bitss)。 解: 同步信号均相同不含信息,其余认为等概,每个码字的信息量为 3*2=6 比特；所以，信息速率为比特/秒2.3 掷一对无偏的骰子，若告诉你得到的总的点数为：(a) 7；(b) 12。试问各得到了多少信息量? 解: (a)一对骰子总点数为7的概率是

2、 所以，得到的信息量为 比特 (b) 一对骰子总点数为12的概率是 所以，得到的信息量为 比特2.4 经过充分洗牌后的一付扑克(含52张牌)，试问：(a) 任何一种特定排列所给出的信息量是多少?(b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量? 解: (a)任一特定排列的概率为, 所以，给出的信息量为 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为 所以，得到的信息量为 比特.2.5 设有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点出现时所给出的信息量，并求掷一次平均得到的信息量。 解:易证每次出现i点的概率为,所以2.6 园丁植树一行，若有

3、3棵白杨、4棵白桦和5棵梧桐。设这12棵树可随机地排列，且每一种排列都是等可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关于树的排列的信息? 解: 可能有的排列总数为 没有两棵梧桐树相邻的排列数可如下图求得， Y X Y X Y X Y X Y X Y X Y X Y 图中X表示白杨或白桦，它有种排法，Y表示梧桐树可以栽种的位置，它有种排法，所以共有*=1960种排法保证没有两棵梧桐树相邻，因此若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为=3.822 比特2.7 某校入学考试中有1/4考生被录取，3/4考生未被录取。被录取的考生中有50%来自本市，而落榜考生中有10来自本市，所有本

4、市的考生都学过英语，而外地落榜考生中以及被录取的外地考生中都有40%学过英语。 (a) 当己知考生来自本市时，给出多少关于考生是否被录取的信息? (b) 当已知考生学过英语时，给出多少有关考生是否被录取的信息? (c) 以x表示是否落榜，y表示是否为本市学生，z表示是否学过英语，x、y和z取值为0或1。试求H(X)，H(Y|X)，H(Z|YZ)。 解: X=0表示未录取，X=1表示录取； Y=0表示本市，Y=1表示外地；Z=0表示学过英语，Z=1表示未学过英语，由此得2.8 在A、B两组人中进行民意测验，组A中的人有50%讲真话(T)，30%讲假话(F)，20%拒绝回答(R)。而组B中有30%

5、讲真话，50%讲假话和20%拒绝回答。设选A组进行测验的概率为p，若以I(p)表示给定T、F或R条件下得到的有关消息来自组A或组B的平均信息量，试求I(p)的最大值。 解:令，则2.9 随机掷三颗骰子，以X表示第一颗骰子抛掷的结果，以Y表示第一和第二颗骰子抛掷的点数之和，以Z表示三颗骰子的点数之和。试求H(Z|Y)、H(X|Y)、H(Z|XY)，H(XZ|Y)和H(Z|X)。 解:令X=X1,Y=X1+X2,Z=X1+X2+X3, H(X1)=H(X2)=H(X3)= 比特 H(X)= H(X1) =2.585 比特 H(Y)= H(X2+X3)= = 3.2744比特H(Z)= H(X1+X

6、2+X3) = 3.5993 比特所以 H(Z/Y)= H(X3)= 2.585 比特 H(Z/X) = H(X2+X3)= 3.2744比特H(X/Y)=H(X)-H(Y)+H(Y/X) = 2.585-3.2744+2.585 =1.8955比特H(Z/XY)=H(Z/Y)= 2.585比特 H(XZ/Y)=H(X/Y)+H(Z/XY) =1.8955+2.585 =4.4805比特2.12 计算习题2.9中的I (Y；Z)，I (X；Z)，I (XY；Z)，I (Y；Z|X)和I (X；Z|Y)。解:I(Y;Z)=H(Z)-H(Z/Y) =H(Z)- H(X3)= 3.5993-2.58

7、5 =1.0143比特I(X;Z)=H(Z)-H(Z/X)=3.5993- 3.2744=0.3249比特I(XY;Z)=H(Z)-H(Z/XY) =H(Z)-H(Z/Y) =1.0143比特I(Y;Z/X)=H(Z/X)-H(Z/XY)= H(X2+X3)-H(X3) =3.2744-2.585 =0.6894比特I(X;Z/Y)=H(Z/Y)-H(Z/XY)=H(Z/Y)-H(Z/Y) =02.10 设有一个系统传送10个数字：0, 1, , 9。奇数在传送时以0.5的概率错成另外的奇数，而其它数字总能正确接收。试求收到一个数字平均得到的信息量。 解:设系统输出10个数字X等概,接收数字为

8、Y,显然 ， H(Y)=log10所以 I(X;Y)= 比特2.11 令ul, u2, , u8为一等概消息集，各消息相应被编成下述二元码字:ul=0000，u2=0011，u3=0101，u4=0110 u5=1001，u6=1010，u7=1100，u8=1111通过转移概率为p的BSC传送。试求：(a) 接收的第一个数字0与ul之间的互信息量。(b) 接收的前二个数字00与ul之间的互信息量。(c) 接收的前三个数字000与ul之间酌互信息量。(d) 接收的前四个数字0000与ul之间的互信息量。 解:（a）接收前一个数字为0的概率 （b）同理 （c）同理 （d）同理 2.13 令X、Y

9、、Z是概率空间，试证明下述关系式成立。(a) H(YZ|X)H(Y|X)H(Z|X)，给出等号成立的条件。(b) H(YZ|X)=H(Y|X)H(Z|XY)。(c) H(Z|XY)H(Z|X)，给出等号成立的条件。 解: (b) (c)（由第二基本不等式）或（由第一基本不等式）所以 ，等号成立的条件为,对所有,即在给定X条件下Y与Z相互独立。(a) 等号成立的条件为,对所有,即在给定X条件下Y与Z相互独立。2.14 对于任意概率事件集X、Y、Z，证明下述三角不等式成立。H(X|Y)H(Y|Z)H(X|Z) H(X|Y)/H(XY)H(Y|Z)/H(YZ)H(X|Z)/H(XZ) 解: (a)

10、(b) 注：2.15 令d(X，Y)=H(X|Y)H(Y|X)为X和Y的信息距离，令(X，Y)=H(X|Y)H(Y|X)/H(XY)为X和Y的信息距离系数。试证明有关距离的三个公理： d(X，X)=0 d(X，Y)0d(X，Y)=d(Y，X) d(X，Y)d(Y，Z)d(X，Z) 解: (a) (b) (c)2.16 定义S(X，Y)=1(X，Y)=I(X；Y)/H(XY)为X和Y之间的信息相似度，证明：0S(X，Y)1 S(X，X)=1 S(X，Y)=0，X和Y独立时。 解:(a) 又由互信息的非负性，即，有，所以 (b) (c) 当且仅当X和Y独立时，I（X；Y）=0，所以，当且仅当X和Y

11、独立时，。2.17 令XYZ为马尔可夫链，证明：I(X；Z|Y)=0 I(XY；Z)=I(Y；Z) I(Y；Z|X)=I(Y|Z)I(X；Z) I(Y；Z|X)I(Y；Z)解: XYZ为马尔可夫链，有p(z/xy)=p(z/y),对所有x,y,z。 2.18 若三个随机变量有如下关系：xy=z，其中x和y独立。试证明：H(X)H (Z) H(Y)H(Z) H(XY)H(Z)I(X；Z)=H(Z)H(Y) I(XY；Z)=H(Z) I(X；YZ)=H(X) I(Y；Z|X)=H(Y) I(X；Y|Z)=H(X|Z)=H(Y|Z)解: (a) H(X)H (Z) (b) H(Y)H(Z)(c) H

12、(XY)H(Z)(d) I(X；Z)=H(Z)H(Y) I(X;Z)=H(Z)-H(Z/X)=H(Z)-H(Y)(e) I(XY；Z)=H(Z)(f) I(X；YZ)=H(X)(g) I(Y；Z|X)=H(Y)H(Y/XZ)=0I(Y;Z/X)=H(Y/X)-H(Y/XZ)=H(Y/X)=H(Y)(h) I(X；Y|Z)=H(X|Z)=H(Y|Z)I(X;Y/Z)=H(X/Z)-H(X/YZ)=H(Y/Z)-H(Y/XZ)而 H(X/YZ)=0,H(Y/XZ)=0所以 I（X；Y/Z）=H(X/Z）=H(Y/Z) #2.19 证明是概率矢量的上凸函数，即对，01和矢量P1和P2有 证明： 2.

13、20 用拉格朗日乘因子法求解下述泛函的极值。 Hn(pl, p2, , pn)， 。解：2.22 令U是非负整数集合，事件kU的概率为p(k)，且(常数)。试求使H(U)为最大的分布p(k)。解：2.23 设X是在1，1上为均匀分布的随机变量。试求Hc(X)，Hc(X 2)和Hc(X 3)。 解: (a) (b) 令(c)令2.24设连续随机变量X和Y的联合概率密度为试求Hc(X)，Hc(Y)，Hc(XY)及I(X；Y)。解：2.25 设X和Y为连续随机变量，且X的概率密度为 ，条件概率密度为其中x，y。试求Hc(X)，Hc(Y/X)，Hc(X/Y)和I(X；Y)。解：2.27 设x为0，上分

14、布的连续随机变量，且满足=S，求实现最大微分熵的分布及相应的熵值。解：2.28 令概率空间，令Y是连续随机变量。已知条件概率率密度为试求(a) Y的概率密度(y) (b) I(X；Y) (c) 若对Y作如下的硬判决： 求I(X；Y)，并对结果进行解释。 解:(a) 由已知，（b）(c)由可求得V的分布为再由及可求得V的条件分布为第三章 离散信源无失真编码3.1解:长为n码字的数目为Dn ,因此长为N的D元不等长码至多有： 3.2 解: 3.4 解:3.5解:（a）二元Huffman编码（b）三元Huffman编码注意：K=10为偶数，需要添一个概率为零的虚假符号3.6解:二元Huffman编码

15、（a）二元Huffman编码（b）（c）3.13 解: (a)根据唯一可译码的判断方法可知,输出二元码字为异字头码,所以它是唯一可译码。 比特(b)因为信源是二元无记忆信源，所以有 其中可计算每个中间数字相应的信源数字的平均长度 信源符号/中间数字(c) 根据表有可计算每个中间数字所对应的平均长度二元码/中间数字由 二元码/信源符号编码效率为0.4756/0.469=98.6%信道及其容量4.1解：(a) 对称信道(b) 对称信道(c) 和信道(课堂教学例题)!4.3解： (a): 可先假设一种分布,利用信道其容量的充要条件来计算(课堂教学例题) (b): 准对称信道！4.5解：课堂教学例题4

16、.8解：该题概率有误，应把1/32改为1/64。每个符号的熵为采样频率Fs为Fs=2W=8000 Hz所以信息速率R为4.9解：每象点8电平量化认为各级出现的概率相等，即H(U)=3 bits所以信息速率R为4.10解：4.12解：高斯信道的信道容量为第五章 离散信道编码定理习题5.1解：DMC信道有因为所以 最大后验概率译码为： 。译码错误概率为：若按最大似然译码准则译码为： 译码错误概率为：可见,最大似然译码的译码错误概率大于最大后验概率译码的译码错误概率。第七章 信道编码1. 设(7,3)码的生成矩阵为(1) 写出该码的一致校验矩阵H；(2) 写出该码的所有许用码字；(3) .写出该码的

17、“译码表”-标准译码表或简化(伴随式)译码表；(4) 写出接收矢量R=1000001的错误图样,并译相应的许用码字；(5) 写出该码在BSC(错误转移概率为p)中传输的(平均)正确译码概率pc的表达式；(6) 写出该码在BSC(错误转移概率为p)中传输的漏检概率Pud(也称不可检测错误概率)的表达式.解: (1) G不为系统码形式,我们通过初等行变换变为系统码形式 因此(2) 由C=MG得该码的许用码字为0000000,0111001,1101010,1010011,1011100,1100101,0110110,0001111该码的最小汉明距离为4。(3) 该码的标准阵由16个陪集构成, 在

18、BSC(错误转移概率为p1/2)应将重量最小的错误图样选作陪集首, 故该码的标准译码表为许用码字0000000(陪集首)0111001110101010100111011100110010101101100001111禁用码字0000001011100011010111010010101110111001000110111000111000000100111011110100010100011011110110011101101000001101000010001111011101110101011110110001100001011001000010110001000011000111000

19、101011011101010011011010111110000011100100000101001111101010000111001100111010101001100011111010000000110011001010111001111111001000101001011001011111000000111100101010100010011001110001001011110110100111100000110111010110100110100001011111110011001101010001100000010101111001101111101011010110011100

20、00001100110001010000100101100001100011101101010101011101100011111100001100010001010100011110111000010100110111101000100111001111001000010011000100101111100101111101100010000101110101110100000111110000101011001001000111010100100111011110011101001000111000101000100011011001010001011011111110100011111100001001001001101001000110101100001010110001101111111译码规则为若接收矢量在第i列出现,