《信息论与编码理论—第三章节习题解答幻灯片》由会员分享，可在线阅读，更多相关《信息论与编码理论—第三章节习题解答幻灯片（59页珍藏版）》请在金锄头文库上搜索。
1、习题课,3.1 试证明长度不超过N的D元不等长码至多有D(DN1)/(D1)个码字。 3.1的解答 长度等于k的D元码字至多有Dk个，其中k=1N。 因此长度不超过N的D元码字至多有,2019/6/3,1,3.2 以上是一个离散无记忆信源。若对其输出的长为100的事件序列中含有两个和更少个al的序列提供不同的码字。 (a) 在等长编码下，求二元码的最短码长N。 (b) 求错误概率(误组率)。 3.2的解答 (a) 长为L=100的事件序列中含有两个和更少个al的序列，其个数为,2019/6/3,2,习题课,(b) 含有两个和更少个al的序列拥有不同的码字，它们的译码不会出现错误。因此错误概率(
2、误组率)不会超过“含有三个以上al的序列”出现的概率。而“含有三个以上al的序列”出现的概率等于,2019/6/3,3,习题课,3.2的注解 事实上，在对“含有两个或更少个al的长为100的序列”提供不同的码字之后,还有210-596=428个富余的码字。这些富余的码字如果提供给其中428 个“含有恰好三个al的长为100的序列”，作为它们各自的不同码字。则错误概率不会超过,2019/6/3,4,习题课,3.4 对于有4个字母的离散无记忆源有两个码A和B，参看下表。试问： (a) 各码是否满足异字头条件?是否为唯一可译码? (b) 当收到1时得到多少关于字母a1的信息? (c) 当收到1时得到
3、多少关于信源的平均信息?,2019/6/3,5,习题课,3.4的解答 (a) 码A是异字头码。码B不是异字头码。码A和码B都是唯一可译码。码A的译码规则是：1就是一个码字的末尾。码B的译码规则是：1就是一个码字的开头。,2019/6/3,6,习题课,(b) “当收到1时得到多少关于字母a1的信息”，这是求事件a1与事件“收到1”的（非平均）互信息量。以码A为例。 P(a1)=0.4。 P(收到1)=P(a1)P(收到1|a1)+P(a2)P(收到1|a2) +P(a3)P(收到1|a3)+P(a4)P(收到1|a4) =0.41+0.3(1/2)+0.2(1/3)+0.1(1/4)=0.642
4、。 P(a1，且收到1)=P(a1)P(收到1|a1)=0.41=0.4。 所以I(a1；收到1)=log0.4/(0.40.642)=0.64155。,2019/6/3,7,(c) “当收到1时得到多少关于信源的平均信息”，这是求信源随机变量U与事件“收到1”的（半平均）互信息量。以码A为例。,I(收到1；U)=,2019/6/3,8,3.6 令离散无记忆信源如上。 (a) 求对U（即U1）的最佳二元码、平均码长和编码效率。 (b) 求对U2 （即U1U2）的最佳二元码、平均码长和编码效率。 (c) 求对U3 （即U1U2U3 ）的最佳二元码、平均码长和编码效率。,2019/6/3,9,（U
5、1U2U3 ）,2019/6/3,10,（U1U2）的第一种最佳二元码,2019/6/3,11,（U1U2）的第二种最佳二元码,2019/6/3,12,（U1U2）的最佳二元码平均码长和编码效率：,2019/6/3,13,2019/6/3,14,2019/6/3,15,2019/6/3,16,2019/6/3,17,2019/6/3,18,2019/6/3,19,2019/6/3,20,2019/6/3,21,2019/6/3,22,2019/6/3,23,2019/6/3,24,2019/6/3,25,2019/6/3,26,2019/6/3,27,2019/6/3,28,2019/6/3,
6、29,2019/6/3,30,2019/6/3,31,2019/6/3,32,2019/6/3,33,2019/6/3,34,（U1U2U3）的码字,2019/6/3,35,（U1U2U3）的最佳二元码平均码长：,2019/6/3,36,（U1U2U3）的最佳二元码编码效率：,2019/6/3,37,3.9 设离散无记忆信源如上。试求其二元和三元Huffman码。 3.9的解答 二元Huffman码为：,2019/6/3,38,习题课,三元Huffman码为：,2019/6/3,39,习题课,3.10 设离散无记忆源 试构造两组三元异字头条件码，其平均码长相同，但具有不同的方差。哪一组更好些?
7、为什么? 3.10的解答 两组不同的三元异字头条件码如下：,2019/6/3,40,第一种三元异字头码（用Huffman编码法） 平均码长为2 ， 方差为0。,2019/6/3,41,第二种三元异字头码（用Huffman编码法） 平均码长为10.2+20.6+30.2=2， 方差为(1-2)20.2+(2-2)20.6+(3-2)20.2=0.4。,2019/6/3,42,习题课,我们认为，第一种三元异字头码比第二种三元异字头码更好。以下是我们的理由。 离散信源每隔一个定长的时间间隔就产生一个随机变量。这个随机变量共有8个可能的事件。 使用第一种三元异字头码，则每隔一个定长的时间间隔就产生一个
8、长度为2的码字。 使用第二种三元异字头码，则每隔一个定长的时间间隔产生一个长度可能为1，可能为2，也可能为3的码字。 综上所述，第一种三元异字头码使得编码器的时钟固定，而第二种三元异字头码使得编码器的时钟随机。因此第一种三元异字头码的编码器更简单。,2019/6/3,43,3.12 设离散无记忆信源如上。若信源输出序列为1011011110110111 （a）对其进行算术编码并计算编码效率。（希望编程计算） （b）对其进行LZ编码并计算编码效率。 3.12的解答 （a） F(0)=0， F(1)=1/4，P(0)=1/4，P(1)=3/4。 L=16，事件序列,2019/6/3,44,编码迭代
9、过程最终得到的 H=P(u1)P(u2)P(u16)=(1/4)4 (3/4)12=312/416 ； log2(1/H)=log2(416/312)=32-12log23=12.98057；因此n=13+1=14。 G=F(u1)+P(u1)F(u2)+P(u1)P(u2)F(u3)+P(u1)P(u2)P(u15)F(u16),=(1/4) +(3/4)0 +(3/4)(1/4)(1/4) +(3/4)(1/4)(3/4)(1/4) +(3/4)(1/4)(3/4)(3/4)0 +(3/4)(1/4)(3/4)(3/4)(1/4)(1/4) +(3/4)(1/4)(3/4)(3/4)(1/
10、4)(3/4)(1/4) +(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(1/4) +(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(1/4) +(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)0 +(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(1/4) +(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(3/4)(1/4) +(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)
11、(3/4)(3/4)(3/4)(1/4)(3/4)(3/4)0 +(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(3/4)(3/4)(1/4)(1/4) +(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(1/4) +(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(3/4)(3/4)(1/4)(3/4)(3/4)(1/4)(3/4)(3/4)(1/4),2019/6/3,45,习题课,=(0.01011001111001000
12、010100111001111)2 码字为01011001111001,2019/6/3,46,习题课,（b） “分段”：(1011011110110111) (1，0，11，01，111，011，0111)； “事件编号”依次为 00， 11； “段编号”依次为,2019/6/3,47,习题课,“按段进行编码”：,2019/6/3,48,习题课,译码时，比特串“0001000000110101011110011101”按照码字长度为3+1=4来分割码字： 0000，0001，0011，0101，0111，1001，1101,2019/6/3,49,习题课,编码效率怎样计算?该事件序列的码字总
13、长度为 N=每段的码字长度段数=47=28。 因此,2019/6/3,50,3.13 设DMS为如上的概率分布。 各ai相应编成码字0，10，110和111。试证明对足够长的信源输出序列，相应的码序列中0和1出现的概率相等。 3.13的证明 设有一个足够长的信源输出序列，因而相应的码序列也足够长。在码序列中随机地取一个符号X，以下只需要证明P(X=0)=1/2。记 Aj=“X是aj的码字中的符号”，j=14。 根据全概率公式，,2019/6/3,51,习题课,2019/6/3,52,习题课,P(X=0|A1)=1；P(X=0|A2)=1/2；P(X=0|A3)=1/3；P(X=0|A4)=0。
14、所以,2019/6/3,53,3.14 设有一DMS如上。采用下述串长编码法进行编码：,2019/6/3,54,习题课,(a) 求H(U) (b) 求对于每个中间数字相应的信源序列平均长度 (c) 求每个中间数字所对应的码字的平均长度 (d) 说明码的唯一可译性。 3.14的解答 (a),2019/6/3,55,(b) 中间数字及其相应的信源序列的长度具有以下的概率分布：,2019/6/3,56,习题课,2019/6/3,57,习题课,(c) 显然码字长度n2的概率分布为 P(n2=1)=0.43046721； P(n2=4)=0.56953279。,2019/6/3,58,习题课,(d) 码的唯一可译性的理由：异字头码。,2019/6/3,59,
