信息论

第八章习题：【8.1】求概率分布为（1/3,1/5,1/5,2/15,2/15）信源的二元霍夫曼码。讨论此码对于概率分布为（1/5，1/5，1/5，1/5，1/5）的信源也是最佳二元码。解：概率分布为（1/3,1/5,1/5,2/15,2/15）信源二元霍夫曼编码过程如下：同样，对于概率分布为（1/5，1/5，1/5，1/5，1/5）的信源，编码过程如下：可见，二者的码字完全相同。当信源给定时，二元霍夫曼码是最佳二元码。即概率分布为（1/5，1/5，1/5，1/5，1/5）的信源也是最佳二元码。【8.2】设二元霍夫曼码为（00,01,10,11）和（0,10,110,111），求出可以编的这样霍夫曼码的信源的所有概率分布。解：二元霍夫曼编码的过程必定是信源缩减的过程，编码为（00,01,10,11）的信源，其码树如下图所示。假设四个信源符号的概率分别是4321,,,pppp，假设4321pppp，则必定有如下条件成立。432431pppppp又14321pppp，即3143pp，因此要构造上述编码，必定要满足4324314331pppppppp而编码为（0,10,110,111）的码树如下图所示：如果按上述情况进行编码，必定要满足,,14312ppppp根据14321pppp，可得，311p。因此完成上述编码的概率分布为：14312131pppppp【8.3】设信源符号集9.01.0)(21sssPS（1）求H(S)和信源剩余度；（2）设码符号为X={0,1}，编出S的紧致码，并求S的紧致码的平均码长；（3）把信源的N次无记忆扩展信源NS编成紧致码，试求出N=2,3,4,时的平均码长）（NLN；(1)（4）计算上述4,3,21，N这四种码的编码效率和码冗余度；解：（1）信源9,.01.0,21，sssPS其符号比特469.0)(log)()(21iiisPsPSH剩余度%1.53531.02log)(1SH（2）码符号}1,0{X，对信源S编紧致码为：1,021ss其平均码长信源符号码符号1L（3）当2N时81.009.009.001.0)(2241232121112ssssssssPSi紧致码（即霍夫曼码）为33211111101001234iilW码长码字平均码长信源符号码符号645.0)(1)(41iiiNlPNNL3N时32222223876543213)9.0()9.0(1.0)9.0(1.0)9.0(1.09.0)1.0(9.0)1.0(9.0)1.0()1.0()(iPS对信源3S进行霍夫曼编码，其紧致码为5555333111111111101110111100110101100012345678iilW码长码字平均码长信源符号码符号533.0)(31)(81iiiNlPNL4N时4333316151413122222222222111098722333346543214)9.0()9.0(1.0)9.0(1.0)9.0(1.0)9.0(1.0)9.0()1.0()9.0()1.0()9.0()1.0()9.0()1.0()9.0()1.0()9.0()1.0(9.0)1.0(9.0)1.0(9.0)1.0(9.0)1.0()1.0()(iPS对信源4S进行霍夫曼编码，其紧致码为10109997711111110011111111000111111111111111110111111101111111011110117776433311111010111100111110001111101110110101100012345678910111213141516iiiilWlW码长码字码长码字平均码长信源符号码符号493.0)(41)(161iiiNlPNLN时，根据香农第一定理，其紧致码的平均码长信源符号码符号469.0log)(limrSHNLNN（4)编码效率)2()()(rLSHLSHr码剩余度)2()(1)(11rLSHLSHr所以%9.4049.0951.04%0.12120.0880.03%3.27273.0727.02%1.53531.0469.011111NNNN码剩余度编码效率【8.4】信源空间为05.005.005.005.01.01.02.04.0)(87654321sssssssssPS码符号为X={0,1,2}，试构造一种三元的紧致码。解：原信源有8个信源符号，为了有效利用短码，需对原信源进行扩展，添加1个概率为0的信源符号，使其满足9=2*3+3成立。编码过程如下：0110102221200200187654321ssssssss三元紧致码信源符号【8.5】某气象员报告气象状态，有四种可能的消息：晴、去、雨和雾。若每个消息是等概率的，那么发送每个消息最少所需的二元脉冲数是多少？又若四个消息出现的概率分别为21818141和，，，问在此情况下消息所需的二元脉冲数是多少？如何编码？解：因为是等概率分布，对这四个消息进行二元脉冲无失真编码时，必须满足lq24，所以l=2,因此发送每个消息最少需要的二元脉冲数为2。如果四个消息非等概率分布，采用紧致码编码，可使得所需要的二元脉冲数最少，编码过程如下：平均码长为：信源符号/二元码元码75.1)(iilsPL即在此情况下消息所需的二元脉冲数为1.75个。【8.6】若某一信源有N个符号，并且每个符号等概率出现，对这信源用最佳霍夫曼码进行二元编码，问当iN2和12iN（i是正整数）时，每个码字的长度等于多少？平均码长是多少？解：（1）当iN2时，对每个符号编码所得的码字为等长码，其码长为i，平均码长iL；（2）当12iN时，每次进行编码时，总会剩余一个，因此，我们可以先将两个信源符号进行缩减，使得缩减后的信源符号个数恰好为i2个，而这i2个信源符号进行编码时是等长的，其码长为i，其中包含原信源符号为12i个，同时，另外两个信源符号的码长为i+1，因此，原信源符号的平均码长为122122212)1(2)12(iiiiiiiiiiL【8.7】设信源MMMMppppssssS121121:并满足Miip11和Mppp21。试证明对于信源S一定存在这样的二元最佳码。其码字1MW和MW具有相同的长度，且1MW与MW只有最后一位码符号不同（分别为1和0）。解：信源MMMMppppssssS121121:Miip11并有Mppp21首先,对于一个最佳码来说.对信源符号MS所编的码字MW,它的码长必定不短于其他码字的码长,(i=1,2...,.M-1)。假如不这样,设某个iW,其码长Mill于是,可把码字MW与iW的位置对换,这样会使平均码长发生变化。这种位置变换所引起的码长变化的差等于))((iMMiMMiiiMMillpplplplplp因为iMMillpp所以0这就是说,位置的交换,平均码长不会增加，只会减少。所以这种置换一直进行下去,直到最后,使信源符号对应的码字MW其码长Ml不小于任一其他码字的码长。其次,根据上述证明,码字MW的码长是所有码字中最长的。若11,MMMMllll那么根据二元码的码长,可找到一种即时码可用树图法表示。根据码树的编码方法,必定从某一中间节点伸出二枝组成码字MW和1MW。因为MW的码长最长,所以必定在树梢端点上。若1MMll,即可将树枝缩短一节。而不影响唯一可译性,如图5.2所示。因为二元码树每一节点伸出的二枝权,只有一位码符号不同。所以得MW和1MW长度相同,而最后一位码符号不同。最后,假如MW中去掉最后一位码元后的码符号序列1MW中去掉最后一位码元后的码符号序列,因为编码的唯一可译性，一定有一个信源符号is,其概率为ip,而码字iW与iW是去掉最后一位码元后的码符号序列相同。由于iMll,而1Mipp。所以可将MW与1MW两码字互相置换，而不增加平均长度。由此证得，码字MW与1MW具有相同的长度，且仅最后一位不同。【8.8】设码C是均匀概率分布(P=1/n,...,1/n）信源的二元霍夫k曼码。并设码C中各码字的码长为il，又设kan2,而21a。（1）证明对于此等概率信源的所有即时码中，码C的总码长iilT最短；（2）证明码C中，所有i满足Lli或1Lli，其中ilLmax；（3）证明码C满足1ilir（4）设u是码长为L-1的码字个数，v是码长为L的码字个数，根据a,k确定u、v和L；（5）根据a,k确定码C的平均码长；证明：（1）根据二元霍夫曼编码的性质，它一定是最佳即时码，即在所有即时码中它的平均码长最短。设C’是其他码字，一定有ccLL'，而平均码长nTLnTLCC','，可得'TT,iilT为最短（2）当a=1时，C码为等长码，均为kli；当a=2时，C码也为等长码，均为1kli；而当1a2时，信源符号个数是位于k2至12k之间的某正整数，反应在码树上，应是一些长度为k的节点上生出分枝，作为长度为k+1的码字。若码C中有一码字j的码长1Llj，设12kLlj。将最长的两个码字合并为一个码字，缩短一个码字；将码字j的码长伸长1，形成两个码长为L-1的码字即)1()2(2326222LLLL码C中没有码长小于L-1的码字。同理，若码C中有二元码字k,j的码长Llljk，设1Lllj。LLL23222)1(1）（，码C中没有码长大于L的码字。由此可以证明码C中最长码长和最短码长只差一个码长，所有i满足Lli或1Lli，其中ilLmax（3）设码长为k的节点数为x，则码长为k+1的节点的分枝数一定为22）（xk，而码字的总个数为：kkkaxxx222)2(1因此有12)2(222)2(221kkkkkkililxxxxrii（4）根据分析可知L=k+1，且有解得11112)1(22222222kkkkkkkaavauuvavu（5）编码后的平均码长为akakaaakakaLkkkk222212)1)(1()22(2111【8.9】现有一幅已离散量化后的图像，图像的灰度量化分成8级，见下表。表中数字为相应像素上的灰度级。1111111111111111111111111111111111111111222222222222222223333333333444444444455555556666667777788888另有一无损无噪二元信道，单位时间（秒）内传输100个二元符号。（1）现将图像通过给定的信道传输，不考虑图像的任何统计特性，并采用二元等长码，问需要多长时间才能传完这幅图像？（2）若考虑图像的统计特性（不考虑图像的像素之间的依赖性），求此图像的信源熵H(S)，并对灰度级进行霍夫曼最佳二元编码，问平均每个像素需用多少二元码符号来表示？这时需多少时间才能传送完这幅图像？（3）从理论上简要说明这幅图像还可以压缩，而且平均每个像素所需的二元码符号数可以小于H(S)比特。解：（1）采用二元等长码，不考虑信源符号的统计特性，平均每个灰度需要3位二进制表示，在的图像上，共需300位二