信息论与编码理论—第三章习题解答

1、2022-3-201习题课习题课3.1 试证明长度不超过N的D元不等长码至多有D(DN1)/(D1)个码字。 3.1的解答长度等于k的D元码字至多有Dk个，其中k=1N。因此长度不超过N的D元码字至多有)1/()1(1DDDDNNkk2022-3-2023.2 以上是一个离散无记忆信源。若对其输出的长为100的事件序列中含有两个和更少个al的序列提供不同的码字。(a) 在等长编码下，求二元码的最短码长N。(b) 求错误概率(误组率)。3.2的解答(a) 长为L=100的事件序列中含有两个和更少个al的序列，其个数为996.0004.021aaU。，所以最短码长为而；10259625964951

2、001109210011000100NCCC2022-3-203习题课习题课(b) 含有两个和更少个al的序列拥有不同的码字，它们的译码不会出现错误。因此错误概率(误组率)不会超过“含有三个以上al的序列”出现的概率。而“含有三个以上al的序列”出现的概率等于204.0201001001003100100!4.01)996.0()004.0(1)996.0()004.0(kkkkkkkkkkekCC2022-3-204习题课习题课3.2的注解 事实上，在对“含有两个或更少个al的长为100的序列”提供不同的码字之后,还有210-596=428个富余的码字。这些富余的码字如果提供给其中428 个

3、“含有恰好三个al的长为100的序列”，作为它们各自的不同码字。则错误概率不会超过00002.0!4.01)996.0()004.0(428)996.0()004.0(204.09731003100100kkkkkkekC2022-3-205习题课习题课3.4 对于有4个字母的离散无记忆源有两个码A和B，参看下表。试问：(a) 各码是否满足异字头条件?是否为唯一可译码?(b) 当收到1时得到多少关于字母a1的信息?(c) 当收到1时得到多少关于信源的平均信息?字 母概 率码 A码 Ba1a2a3a4 0.40.30.20.1 1010010001 1101001000 2022-3-206习题

4、课习题课3.4的解答(a) 码A是异字头码。码B不是异字头码。码A和码B都是唯一可译码。码A的译码规则是：1就是一个码字的末尾。码B的译码规则是：1就是一个码字的开头。2022-3-207习题课习题课(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。P(a1，且收到1)=P(a1)P(收到1|a1)=0.

5、41=0.4。所以I(a1；收到1)=log0.4/(0.40.642)=0.64155。2022-3-208(c) “当收到1时得到多少关于信源的平均信息”，这是求信源随机变量U与事件“收到1”的（半平均）互信息量。以码A为例。I(收到1；U)=)1()()1,(log)1|()1()()1,(log)1|()1()()1,(log)1|()1()()1,(log)1|(444333222111收到且收到收到收到且收到收到收到且收到收到收到且收到收到PaPaPaPPaPaPaPPaPaPaPPaPaPaP2022-3-2093.6 令离散无记忆信源如上。(a) 求对U（即U1）的最佳二元码、

6、平均码长和编码效率。(b) 求对U2 （即U1U2）的最佳二元码、平均码长和编码效率。(c) 求对U3 （即U1U2U3 ）的最佳二元码、平均码长和编码效率。2 . 03 . 05 . 0321aaaU04. 006. 006. 009. 010. 010. 015. 015. 025. 033233222133112211121aaaaaaaaaaaaaaaaaaUU2022-3-2010（U1U2U3 ）a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a20.1250.0750.0750.0750.0500.0500.0500.045

7、0.045a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30.0450.0300.0300.0300.0300.0300.0300.0270.020a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30.0200.0200.0180.0180.0180.0120.0120.0120.0082022-3-2011（U1U2）的第一种最佳二元码）的第一种最佳二元码2022-3-2012（U1U2）的第二种最佳二元码）的第二种最佳二元码2022-3-2013（U1U2）的最佳二元码平均

8、码长和编码效）的最佳二元码平均码长和编码效率：率：3)04. 0206. 009. 0(4) 210. 0215. 0(325. 02)(2Un5 .12)(2Unn因此平均码长为48503. 12 . 01log2 . 03 . 01log3 . 05 . 01log5 . 0)(UHnnR2log编码速率为99002.05 .148503.1)()(2RUHU因此编码效率为2022-3-20142022-3-20152022-3-20162022-3-20172022-3-20182022-3-20192022-3-20202022-3-20212022-3-20222022-3-2023

9、2022-3-20242022-3-20252022-3-20262022-3-20272022-3-20282022-3-20292022-3-20302022-3-20312022-3-20322022-3-20332022-3-20342022-3-2035（U1U2U3）的码字）的码字a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a201000000001011011101000100110101011a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30010001110

10、110001100111010110111111011111001100a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a300110100111000111101111001111100101000010101001011000101112022-3-2036（U1U2U3）的最佳二元码平均码长：）的最佳二元码平均码长：487. 4)008. 03012. 0(7) 3018. 03020. 0(6)027. 06030. 0045. 0(5) 2045. 03050. 03075. 0(4125. 03)(3Un4956666.13)

11、(3Unn因此平均码长为2022-3-2037（U1U2U3）的最佳二元码编码效率：）的最佳二元码编码效率：48503. 12 . 01log2 . 03 . 01log3 . 05 . 01log5 . 0)(UHnnR2log编码速率为99289.04956666.148503.1)()(3RUHU因此编码效率为)(99289.099002.0)(32UU2022-3-20383.9 设离散无记忆信源如上。试求其二元和三元Huffman码。 3.9的解答 二元Huffman码为：1 . 01 . 015. 015. 02 . 03 . 0654321aaaaaaU2022-3-2039习题

12、课习题课三元Huffman码为：2022-3-2040习题课习题课3.10 设离散无记忆源试构造两组三元异字头条件码，其平均码长相同，但具有不同的方差。哪一组更好些?为什么?3.10的解答 两组不同的三元异字头条件码如下：1 . 01 . 01 . 01 . 01 . 015. 015. 02 . 087654321aaaaaaaaU2022-3-2041第一种三元异字头码（用第一种三元异字头码（用Huffman编码法）编码法）平均码长为2 ，方差为0。2022-3-2042第二种三元异字头码（用第二种三元异字头码（用Huffman编码法）编码法） 平均码长为10.2+20.6+30.2=2，

13、方差为(1-2)20.2+(2-2)20.6+(3-2)20.2=0.4。2022-3-2043习题课习题课我们认为，第一种三元异字头码比第二种三元异字头码更好。以下是我们的理由。离散信源每隔一个定长的时间间隔就产生一个随机变量。这个随机变量共有8个可能的事件。使用第一种三元异字头码，则每隔一个定长的时间间隔就产生一个长度为2的码字。使用第二种三元异字头码，则每隔一个定长的时间间隔产生一个长度可能为1，可能为2，也可能为3的码字。综上所述，第一种三元异字头码使得编码器的时钟固定，而第二种三元异字头码使得编码器的时钟随机。因此第一种三元异字头码的编码器更简单。2022-3-20443.12 设离

14、散无记忆信源如上。若信源输出序列为1011011110110111（a）对其进行算术编码并计算编码效率。（希望编程计算）（b）对其进行LZ编码并计算编码效率。3.12的解答 （a） F(0)=0， F(1)=1/4，P(0)=1/4，P(1)=3/4。 L=16，事件序列4/ 34/ 110Uu1u2u3u4u5u6u7u8u9u10u11u12u13u14u15u1610110111101101112022-3-2045编码迭代过程最终得到的H=P(u1)P(u2)P(u16)=(1/4)4 (3/4)12=312/416 ；log2(1/H)=log2(416/312)=32-12log2

15、3=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/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

16、)(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)(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

17、/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)2022-3-2046习题课习题课=(0.01011001111001000010100111001111)2码字为码字为0101100111100181129. 034log434log41)(UH99851. 013)(16)(UHnUHL序列的编码效率，为编码效率

18、指的是该事件2022-3-2047习题课习题课（b）“分段分段”：(1011011110110111)(1，0，11，01，111，011，0111)；“事件编号事件编号”依次为 00， 11；“段编号段编号”依次为段1011011110110111段号0010100111001011101112022-3-2048习题课习题课“按段进行编码按段进行编码”：101101111011011100010000001101010111100111012022-3-2049习题课习题课译码时，比特串“0001000000110101011110011101”按照码字长度为3+1=4来分割码字：0000

19、，0001，0011，0101，0111，1001，1101码字码字0001000000110101011110011101段号段号001010011100101110111段值段值10110111101101112022-3-2050习题课习题课编码效率怎样计算?该事件序列的码字总长度为N=每段的码字长度段数=47=28。因此46359. 028)(16)(UHNUHL序列的编码效率，为编码效率指的是该事件2022-3-20513.13 设DMS为如上的概率分布。各ai相应编成码字0，10，110和111。试证明对足够长的信源输出序列，相应的码序列中0和1出现的概率相等。 3.13的证明 设

20、有一个足够长的信源输出序列，因而相应的码序列也足够长。在码序列中随机地取一个符号X，以下只需要证明P(X=0)=1/2。记Aj=“X是aj的码字中的符号”，j=14。根据全概率公式，8/18/14/12/14321aaaaU41)|0()()0(jjjAXPAPXP2022-3-2052习题课习题课72381381241121121)(1AP72381381241121241)(2AP143381381241121381)(3AP143381381241121381)(4AP2022-3-2053习题课习题课P(X=0|A1)=1；P(X=0|A2)=1/2；P(X=0|A3)=1/3；P(X=0|A4)=0。所以210143311432172172)0(XP2022-3-20543.14 设有一DMS如上。采用下述串长编码法进行编码： 1 . 09 . 010U信源输出序列 0串长度（或中间数字）