信息论与编码第五章习题参考答案

信息论与编码第五章答案本页仅作为文档封面，使用时可以删除This document is for reference only-rar21 year.March设信源「x ]=严①①①勺% 5 “(X)」[0.2 0.19 0.18 0.17 0.15 0.1 0.01(1) 求信源爛H(X)；(2) 编二进制香农码；(3) 计算平均码长和编码效率.解：(1)H(X)= -另/Xt/Jlogn p(di)i・l=-0.2 x log 三02 - 0」9 x log 0」9-0.18xlog20.18-0.17xlog20.17-0.15xlog20.15-0.1xlog20.1-0.01xlog2 0.01=2.609”〃 / symbol斤=》&°a)= 0・2x3 + 0」9x3 + 0」8x3 + 0」7x3 + 0」5x3 +0.1x4 + 0.01x7= 3.141Z7 = ^y M2 = H(X)/^ = 2.609^3.141 =83.1%对习题的信源编二进制费诺码，计算编码效率. 解：=M_2% r = 2fc /X^) = 2xO_2+3xO_19+3xO_18+2xO_17+3xO_15+ 4x01+4x001 = 274H(X) _ _ 2-609 R ~ X ~ 2-74对信源l/cxj I 0-2 o w 01g 017 015 01编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率.解：二进制哈夫曼码:r = 2fc /X^) = 2xO_2 + 2xO_19+3xO_18+3xOJ7+3xO_15+ 4x01+4x001 =2_72R K 2_72三进制哈夫曼码:=914%= 1x0-2 +2x(019+ 0.18+0J7 +0.15+OJ+O-Ol)=L8H(X) HQXi 2.609 4=豪= =l_8xlDg 23 V，D82O T设信源⑴求信源H(X)；⑵编二进制香农码和二进制费诺码；⑶计•算二进制香农码和二进制费诺码的平均码长和编码效率； ⑷编三进制费诺码；⑸计算三进制费诺码的平均码长和编码效率； 解： ⑴更3)=-送>(对如B 2 Pg)i-1=—xk>g 2 2+—5clog 2 4+—xlog 28+—xlog 316 +—xk>g 332+—xlog 264 + ^—xlog 3128 + ^—： 224 X 2 16 32 64 128 128 = 1_984 Iriifsymbol⑵二进制香农码:XiP (Xi)P<M ki码字X11 0 X22 10 X33 110 X44 1110 X55 11110 X66 111110 X77 1111110 X871111111二进制费诺码:xiP (Xi)编码码字k Xi1 X2102211103屯耳七总 X, £ [1111118 16 32 64 128 128香农编码效率：r = yfcX^) = -xl + lx2+lx3+Ax4+Ax5 +—X6+—X7 + —X7T £2 4 8 16 32 64 128 128=1.9&4R K 1_984费诺编码效率：r = yfcX^) = -^l + ix2+ix3+Ax4+Ax5 +—x6+—x7 + —x7 T 2 4 8 16 3264128 128=1_984R K 1_984⑷⑸^=Sfc;X^) = -xl+-xU-x2+ —x2+—X3+A X3+X X4+X X4V 2 4 & 16 3264 128 12S=1328R X 1328x1^,3~ X]J Q r设无记忆二进制信源|_切」I0-9 01先把信源序列编成数字0, 1, 2 ............... .. 8,再替换成二进制变长码字，如下表所示.(1) 验证码字的可分离性；(2) 求对应于一个数字的信源序列的平均长度热;(3) 求对应于一个码字的信源序列的平均长度不;⑷计算耳，并讣算编码效率；⑸若用4位信源符号合起来编成二进制哈夫曼码，求它的平均码长疋, 并计算编码效率.p(0/0) = , p(l/l)=,码，求新符号的平均码字长度和编码效率.对题的信源进行游程编码•若“0”游程长度的截至值为16, “1”游程长度的截至值为&求编码效率.选择帧长A/ = 64(1) 对00000000000000000000000000000000000000 遍L・D 码；(2) 对000000000010 遍L-D 码再译码;⑶对0000000000000000000000000000000000000000000000000000000000000000遍L-D码；⑷对0遍L-D码；(5)对上述结果进行讨论.。

信息论与编码习题参考答案 第一章 单符号离散信源同时掷一对均匀的子，试求：(1)“2和6同时出现”这一事件的自信息量； (2)“两个5同时出现”这一事件的自信息量； (3)两个点数的各种组合的熵； (4)两个点数之和的熵；(5)“两个点数中至少有一个是1”的自信息量。

解：bitP a I N n P bit P a I N n P c c N 17.536log log )(361)2(17.418log log )(362)1(36662221111616==-=∴====-=∴===⨯==样本空间：(3)信源空间：bit x H 32.436log 3616236log 36215)(=⨯⨯+⨯⨯=∴ (4)信源空间：bitx H 71.3636log 366536log 3610 436log 368336log 366236log 36436log 362)(=⨯⨯+⨯+⨯+⨯⨯=∴＋＋ (5) bit P a I N n P 17.11136log log )(3611333==-=∴==如有6行、8列的棋型方格，若有两个质点A 和B ，分别以等概落入任一方格内，且它们的坐标分别为（Xa ，Ya ）, （Xb ，Yb ）,但A ，B 不能同时落入同一方格内。

（1） 若仅有质点A ，求A 落入任一方格的平均信息量； （2） 若已知A 已落入，求B 落入的平均信息量； （3） 若A ，B 是可辨认的，求A ，B 落入的平均信息量。

解：bita P a P a a P a I a P A i 58.548log )(log )()(H 48log )(log )(481)(:)1(481i i i i i ==-=∴=-=∴=∑=落入任一格的概率bitb P b P b b P b I b P A i 55.547log )(log )()(H 47log )(log )(471)(:B ,)2(481i i i i i ==-=∴=-=∴=∑=落入任一格的概率是落入任一格的情况下在已知bitAB P AB P AB H AB P AB I AB P AB i i i i i i i 14.11)4748log()(log )()()(log )(471481)()3(47481=⨯=-=-=∴⨯=∑⨯=是同时落入某两格的概率从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为%.如果你问一位男士：“你是否是红绿色盲”他的回答可能是：“是”，也可能“不是”。

信息论与编码习题参考答案 第一章 单符号离散信源1.1同时掷一对均匀的子，试求：(1)“2和6同时出现”这一事件的自信息量； (2)“两个5同时出现”这一事件的自信息量； (3)两个点数的各种组合的熵； (4)两个点数之和的熵；(5)“两个点数中至少有一个是1”的自信息量。

解：bitP a I N n P bit P a I N n P c c N 17.536log log )(361)2(17.418log log )(362)1(36662221111616==-=∴====-=∴===⨯==样本空间：(3)信源空间：bit x H 32.436log 3662log 3615)(=⨯⨯+⨯⨯=∴ bitx H 71.3636log 366536log 3610 436log 368336log 366236log 36436log 362)(=⨯⨯+⨯+⨯+⨯⨯=∴＋＋ (5) bit P a I N n P 17.11136log log )(3611333==-=∴==1.2如有6行、8列的棋型方格，若有两个质点A 和B ，分别以等概落入任一方格，且它们的坐标分别为（Xa ，Ya ）, （Xb ，Yb ）,但A ，B 不能同时落入同一方格。

（1） 若仅有质点A ，求A 落入任一方格的平均信息量； （2） 若已知A 已落入，求B 落入的平均信息量； （3） 若A ，B 是可辨认的，求A ，B 落入的平均信息量。

解：bita P a P a a P a I a P A i 58.548log )(log )()(H 48log )(log )(481)(:)1(481i i i i i ==-=∴=-=∴=∑=落入任一格的概率Θbitb P b P b b P b I b P A i 55.547log )(log )()(H 47log )(log )(471)(:B ,)2(481i i i i i ==-=∴=-=∴=∑=落入任一格的概率是落入任一格的情况下在已知ΘbitAB P AB P AB H AB P AB I AB P AB i i i i i i i 14.11)4748log()(log )()()(log )(471481)()3(47481=⨯=-=-=∴⨯=∑⨯=是同时落入某两格的概率1.3从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为0.5%.如果你问一位男士：“你是否是红绿色盲？”他的回答可能是：“是”，也可能“不是”。

信息论与编码习题参考答案 第一章 单符号离散信源同时掷一对均匀的子，试求：(1)“2和6同时出现”这一事件的自信息量； (2)“两个5同时出现”这一事件的自信息量； (3)两个点数的各种组合的熵； (4)两个点数之和的熵；(5)“两个点数中至少有一个是1”的自信息量。

解：bitP a I N n P bit P a I N n P c c N 17.536log log )(361)2(17.418log log )(362)1(36662221111616==-=∴====-=∴===⨯==样本空间：(3)信源空间：bit x H 32.436log 3662log 3615)(=⨯⨯+⨯⨯=∴ (4)信源空间： bitx H 71.3636log 366536log 3610 436log 368336log 366236log 36436log 362)(=⨯⨯+⨯+⨯+⨯⨯=∴＋＋ (5) bit P a I N n P 17.11136log log )(3611333==-=∴==如有6行、8列的棋型方格，若有两个质点A 和B ，分别以等概落入任一方格内，且它们的坐标分别为（Xa ，Ya ）, （Xb ，Yb ）,但A ，B 不能同时落入同一方格内。

（1） 若仅有质点A ，求A 落入任一方格的平均信息量； （2） 若已知A 已落入，求B 落入的平均信息量； （3） 若A ，B 是可辨认的，求A ，B 落入的平均信息量。

解：bita P a P a a P a I a P A i 58.548log )(log )()(H 48log )(log )(481)(:)1(481i i i i i ==-=∴=-=∴=∑=落入任一格的概率Θbitb P b P b b P b I b P A i 55.547log )(log )()(H 47log )(log )(471)(:B ,)2(481i i i i i ==-=∴=-=∴=∑=落入任一格的概率是落入任一格的情况下在已知ΘbitAB P AB P AB H AB P AB I AB P AB i i i i i i i 14.11)4748log()(log )()()(log )(471481)()3(47481=⨯=-=-=∴⨯=∑⨯=是同时落入某两格的概率从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为%.如果你问一位男士：“你是否是红绿色盲”他的回答可能是：“是”，也可能“不是”。

第5章 有噪信道编码5.1 基本要求通过本章学习，了解信道编码的目的，了解译码规则对错误概率的影响，掌握两种典型的译码规则：最佳译码规则和极大似然译码规则。

掌握信息率与平均差错率的关系，掌握最小汉明距离译码规则，掌握有噪信道编码定理（香农第二定理）的基本思想，了解典型序列的概念，了解定理的证明方法，掌握线性分组码的生成和校验。

5.2 学习要点5.2.1 信道译码函数与平均差错率5.2.1.1 信道译码模型从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为F 。

信道译码模型如图5.1所示。

5.2.1.2 信道译码函数信道译码函数F 是从输出符号集合B 到输入符号集合A 的映射：*()j j F b a A =∈，1,2,...j s =其含义是：将接收符号j b B ∈译为某个输入符号*j a A ∈。

译码函数又称译码规则。

5.2.1.3 平均差错率在信道输出端接收到符号j b 时，按译码规则*()j j F b a A =∈将j b 译为*j a ，若此时信道输入刚好是*j a ，则称为译码正确，否则称为译码错误。

j b 的译码正确概率是后验概率：*(|)()|j j j j P X a Y b P F b b ⎡⎤===⎣⎦ （5.1）j b 的译码错误概率：(|)()|1()|j j j j j P e b P X F b Y b P F b b ⎡⎤⎡⎤=≠==-⎣⎦⎣⎦ （5.2）平均差错率是译码错误概率的统计平均，记为e P ：{}1111()(|)()1()|1(),1()|()s se j j j j j j j ssj j j j j j j P P b P e b P b P F b b P F b b P F b P b F b ====⎡⎤==-⎣⎦⎡⎤⎡⎤⎡⎤=-=-⎣⎦⎣⎦⎣⎦∑∑∑∑ （5.3）5.2.2 两种典型的译码规则两种典型的译码规则是最佳译码规则和极大似然译码规则。

5.1设有信源()12345670.20.190.180.170.150.10.01X a a a a a a a P X ⎛⎫⎧⎫=⎨⎬ ⎪⎩⎭⎝⎭ (1)求信源熵()H X ; (2)编二进制香农码；（3）计算平均码长及编码效率； 解：（1） ()()()l o g0.2l o g 0.20.19l o g 0.190.18l o g 0.180.17l o g 0.170.15l o g 0.150.1l o g 0.10.01l0.46440.45520.44530.43460.41050.33220.06642.61i i H Xp a p a bitsign=-==-------=++++++=∑（2）(3)()0.20.190.180.170.1530.140.0173.14K =++++⨯+⨯+⨯=()()2log 2.6183.12%3.14K R mLH X H X RKη=====5.2对习题5.1的信源编二进制费诺码，计算其编码效率。

由题知：()()()log 0.2log 0.20.19log 0.190.18log 0.180.17log 0.170.15log 0.150.1log 0.10.01log 0.010.46440.45520.44530.43460.41050.33220.06642.61i i HX p a p a bitsign=-==-------=++++++=∑0.220.1930.1830.1720.1530.140.0142.74K =⨯+⨯+⨯+⨯+⨯+⨯+⨯=()()2log 2.6195.26%2.74K R mLH X H X RKη=====5.3对习题5.1的信源编二进制赫夫曼码，计算平均码长和编码效率。

（注：老师，图画的不好看，您就将就看吧，实在画不出了！）()()()0.20.1920.180.170.1530.10.0142.72K =+⨯+++⨯++⨯=()()()log 0.2log 0.20.19log 0.190.18log 0.180.17log 0.170.15log 0.150.1log 0.10.01log 0.010.46440.45520.44530.43460.41050.33220.06642.61i i H Xp a p a bitsign=-==-------=++++++=∑()()2.6195.96%2.72H X H X RKη====5.4设信源()1234567811111111248163264128128aa a a a a a a X P X ⎧⎫⎛⎫⎪⎪=⎨⎬ ⎪⎝⎭⎪⎪⎩⎭（1） 计算信源熵；（2） 编二进制香农码和二进制费诺码；（3） 计算二进制香农码和二进制费诺码的平均码长及编码效率； 解：（1）()()()log 1111111111111111loglogloglogloglogloglog2244881616323264641281281281281.984375i i HX P a P a biasign=-=--------=∑（在下一页）（2）香浓编码费诺编码香浓编码()()211111111123456772481632641281281.984375log 1.984375100%1.984375K K R mL H X HX RKη=⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯======费诺编码()()211111111123456772481632641281281.984375log 1.984375100%1.984375K K R mL H X HX RKη=⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯======5.9将幅度为3.25V 、频率为800 Hz 的正弦信号的输入采样频率为8kHz 采样保持器后，通过一个如题图5.1所示量化数为8的中升均匀量化器。

5-10 设有离散无记忆信源}03.0,07.0,10.0,18.0,25.0,37.0{)(=X P 。

（1）求该信源符号熵H(X)。

（2）用哈夫曼编码编成二元变长码，计算其编码效率。

（3）要求译码错误小于310-，采用定长二元码达到（2）中的哈夫曼编码效率，问需要多少个信源符号连在一起编？ 解：（1）信源符号熵为symbolbit x p x p X H i ii /23.203.0log 03.007.0log 07.010.0log 10.018.0log 18.025.0log 25.037.0log 37.0)(log )()(222222=------=-=∑ （2）1x 3x 2x 6x 5x 4x 0.370.250.180.100.070.030111110.100.200.380.621.0000011110110001001符号概率编码该哈夫曼码的平均码长为符号码元/3.2403.0407.0310.0218.0225.0237.0)(=⨯+⨯+⨯+⨯+⨯+⨯==∑iii K x p K 编码效率为9696.03.223.2)(===KX H η (3)信源序列的自信息方差为2222)(792.0)]([)]()[log ()(bit X H x p x p X i ii =-=∑σ7.00696.90)()(==+=εεη得，由X H X H53222102.6110)7.00(92.70)(⨯=⨯=≥-δεσX L 由切比雪夫不等式可得所以，至少需要1.62×105个信源符号一起编码才能满足要求。

5-12 已知一信源包含8个消息符号，其出现的概率}04.0,07.0,1.0,06.0,05.0,4.0,18.0,1.0{)(=X P ，则求：（1）该信源在每秒内发出1个符号，求该信源的熵及信息传输速率。

（2）对这8个符号作哈夫曼编码，写出相应码字，并求出编码效率。

第五章课后习题【5.1】某信源按43)0(=P ，41)1(=P 的概率产生统计独立的二元序列。

（1）试求0N ，使当0N N >时有01.005.0)()(≤≥−S H N I P i α 式中，)(S H 是信源的熵。

（2）试求当0N N =时典型序列集N G ε中含有的信源序列个数。

解：（1）该信源的信源熵为811.0)(log )()(=−=∑i i s p s p S H 比特/符号自信息的方差为4715.0811.04log 4134log 43)()]([)]([22222=−+=−=S H s I E s I D i i 根据等长码编码定理，我们知道δεα−≤≥−1)()(S H N I P i 根据给定条件可知，05.0=ε，99.0=δ。

而[]2)(εδN s I D i =因此[]5.19099.0*05.04715.0)(220==≥δεi s I D N 取1910=N 。

（2）ε典型序列中信源序列个数取值范围为：])([])([22)1(εεεδ+−<<−S H N N S H N G代入上述数值得451.164351.1452201.0<<×N G ε【5.2】有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A 、B 、C 、D 、E 和F 。

表5.2消息 )(i a P A B C D E F 1a 1/2 000 0 0 0 0 0 2a 1/4 001 01 10 10 10 100 3a 1/16 010 011 110 110 1100 101 4a 1/16 011 0111 1110 1110 1101 110 5a 1/16 100 01111 11110 1011 1110 111 6a1/1610101111111111011011111011（1） 求这些码中哪些是惟一可译码； （2） 求哪些码是非延长码（即时码）； （3） 求对所有惟一可译码求出其平均码长L 。