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

习题课3.1试证明长度不超过N的D元不等长码至多有D(DN－1)/(D－1)个码字。[3.1的解答]长度等于k的D元码字至多有Dk个，其中k=1~N。因此长度不超过N的D元码字至多有6/27/201913.2以上是一个离散无记忆信源。若对其输出的长为100的事件序列中含有两个和更少个al的序列提供不同的码字。(a)在等长编码下,求二元码的最短码长N。(b)求错误概率(误组率)。[3.2的解答](a)长为L=100的事件序列中含有两个和更少个al的序列,其个数为6/27/20192习题课(b)含有两个和更少个al的序列拥有不同的码字,它们的译码不会出现错误。因此错误概率(误组率)不会超过“含有三个以上al的序列”出现的概率。而“含有三个以上al的序列”出现的概率等于6/27/20193习题课[3.2的注解]事实上,在对“含有两个或更少个al的长为100的序列”提供不同的码字之后,还有210-596=428个富余的码字。这些富余的码字如果提供给其中428个“含有恰好三个al的长为100的序列”,作为它们各自的不同码字。则错误概率不会超过6/27/20194习题课3.4对于有4个字母的离散无记忆源有两个码A和B，参看下表。试问:各码是否满足异字头条件?是否为唯一可译码?当收到1时得到多少关于字母a1的信息?当收到1时得到多少关于信源的平均信息?字母概率码A码Ba10.411a20.30110a30.20011006/27/20195a0.100011000习题课6/27/20196[3.4的解答](a)码A是异字头码。码B不是异字头码。码A和码B都是唯一可译码。码A的译码规则是:1就是一个码字的末尾。码B的译码规则是:1就是一个码字的开头。习题课6/27/20197(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.4×1+0.3×(1/2)+0.2×(1/3)+0.1×(1/4)=0.642。P(a1,且收到1)=P(a1)×P(收到1|a1)=0.4×1=0.4。所以I(a1；收到1)=log{0.4/(0.4×0.642)}=0.64155。(c)“当收到1时得到多少关于信源的平均信息”,这是求信源随机变量U与事件“收到1”的（半平均）互信息量。以码A为例。I(收到1；U)=6/27/201983.6令离散无记忆信源如上。求对U（即U1）的最佳二元码、平均码长和编码效率。求对U2

（即U1U2）的最佳二元码、平均码长和编码效率。求对U3

（即U1U2U3

）的最佳二元码、平均码长和编码效率。6/27/20199（U1U2U3

）~6/27/201910a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a20.1250.0750.0750.0750.0500.0500.0500.0450.045a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30.0450.0300.0300.0300.0300.0300.0300.0270.020a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30.0200.0200.0180.0180.0180.0120.0120.0120.008（U1U2）的第一种最佳二元码6/27/201911（U1U2）的第二种最佳二元码6/27/201912（U1U2）的最佳二元码平均码长和编码效率:6/27/2019136/27/2019146/27/2019156/27/2019166/27/2019176/27/2019186/27/2019196/27/2019206/27/2019216/27/2019226/27/2019236/27/2019246/27/2019256/27/2019266/27/2019276/27/2019286/27/2019296/27/2019306/27/2019316/27/2019326/27/2019336/27/201934（U1U2U3）的码字6/27/201935a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a201000000001011011101000100110101011a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30010001110110001100111010110111111011111001100a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30011010011100011110111100111110010100001010100101100010111（U1U2U3）的最佳二元码平均码长:6/27/201936（U1U2U3）的最佳二元码编码效率:6/27/2019373.9设离散无记忆信源如上。试求其二元和三元Huffman码。[3.9的解答]二元Huffman码为:6/27/201938习题课三元Huffman码为:6/27/201939习题课3.10设离散无记忆源试构造两组三元异字头条件码，其平均码长相同，但具有不同的方差。哪一组更好些?为什么?[3.10的解答]两组不同的三元异字头条件码如下:6/27/201940第一种三元异字头码（用Huffman编码法）平均码长为2,方差为0。6/27/201941第二种三元异字头码（用Huffman编码法）平均码长为1×0.2+2×0.6+3×0.2=2,方差为(1-2)2×0.2+(2-2)2×0.6+(3-2)2×0.2=0.4。6/27/201942习题课6/27/201943我们认为,第一种三元异字头码比第二种三元异字头码更好。以下是我们的理由。离散信源每隔一个定长的时间间隔就产生一个随机变量。这个随机变量共有8个可能的事件。使用第一种三元异字头码,则每隔一个定长的时间间隔就产生一个长度为2的码字。使用第二种三元异字头码,则每隔一个定长的时间间隔产生一个长度可能为1,可能为2,也可能为3的码字。综上所述,第一种三元异字头码使得编码器的时钟固定,而第二种三元异字头码使得编码器的时钟随机。因此第一种三元异字头码的编码器更简单。3.12设离散无记忆信源如上。若信源输出序列为1011011110110111对其进行算术编码并计算编码效率。（希望编程计算）对其进行LZ编码并计算编码效率。[3.12的解答]（a）F(0)=0,F(1)=1/4,P(0)=1/4,P(1)=3/4。L=16,事件序u1u2u3u4u5u6u7u8u9u10u11u12u13u14u15u1610110111101101116/27/201944编码迭代过程最终得到的H=P(u1)P(u2)…P(u16)=(1/4)4

(3/4)12=312/416

；log2(1/H)=log2(416/312)=32-12×log23=12.98057；因此n=13+1=1G=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)×(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/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)×(3/4)×(1/4)×(3/4)×(3/4)×(3/4)×(3/4)×(1/4)×(3/4)×(3/4)×(1/4)×(1/4)6/27/201945习题课=(0.01011001111001000010100111001111)2码字为010110011110016/27/201946习题课6/27/201947（b）“分段”:(1011011110110111)→(1，0，11，01，111，011，0111)；“事件编号”依次为{0~0，1~1}；“段编号”依次为段1011011110110111段号001010011100101110111习题课6/27/201948“按段进行编码”:10110111101101110001000000110101011110011101习题课译码时，比特串“0001000000110101011110011101”按照码字长度为3+1=4来分割码字:0000，0001，0011，0101，0111，1001，1101码字0001000000110101011110011101段号001010011100101110111段值10110111101101116/27/201949习题课编码效率怎样计算?该事件序列的码字总长度为N=每段的码字长度×段数=4×7=28。因此6/27/2019503.13设DMS为如上的概率分布。各ai相应编成码字0,10,110和111。试证明对足够长的信源输出序列,相应的码序列中0和1出现的概率相等。[3.13的证明]设有一个足够长的信源输出序列,因而相应的码序列也足够长。在码序列中随机地取一个符号X,以下只需要证明P(X=0)=1/2。记Aj=“X是aj的码字中的符号”,j=1~4。根据全概率公式,6/27/201951习题课6/27/201952习题课P(X=0|A1)=1；P(X=0|A2)=1