第4章习题解答41022

1、4.1 某集源按P(0)=3/4,P(1)=1/4的概率产生统计独立的二元序列.(1) 试求N0，使当N>N0时有：P|I(ai)/NH(S)| 0.050.01其中H(S)是信源的熵。(2)试求当N= N0时典型序列集GN中含有的信源序列个数。解：(1) H(S)= -PiPi= -3/4(3/4)-1/4(1/4) =0.811 比特/符号根据契比雪夫不等式，对于任意0，当NN0时， PI(i)/N H(S)DI(Si)/N2现有=0.05,欲证原式，只要DI(Si)/N20.01根据信源，DI(Si)=P(Si)P(Si)2 H2(S) =3/4(3/4)2+1/4(1/4)2-(

2、0.811)2 =0.471N0= DI(Si)/0.012=0.471/0.01×(0.05)2=18840(2) 序列GN是所有N长的典型序列集合， （1-）2NH（S）-GN2NH（S）- 0.99×214342.5GN216226.54.2 设无记忆二元信源，其概率为P1=0.005, P0=0.995。信源输出N100的二元序列。在长为N100的信源序列中只对含有3个或小于3个“1”的各信源序列构成一一对应的一组等长码。（1）求码字所需的最小长度。（2）计算式（4.27a）中的。（3）考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率PE是多少？若从契比

3、雪夫不等式（4.22）考虑，PE应是多少？试加以比较。解：（1）无记忆二元信源N=100的扩展信源现只对含有3个或小于3个“1”的各信源序列构成一一对应的一组二元等长码。那么，在这个N长的信源序列中含有小于3个“1”和含有3个“1”的序列个数有对M个信源序列进行无失真的二元等长编码，必须=166750所以码字所需的最小长度18（2）对于这二元信源，其H(S)0.0454 比特/符号现根据所编码的N（100）长的信源序列来计算。在这N长的信源序列中全零序列其最大，则其最小；而其中含3个“1”的序列其最小则最大。所以，全零序列 log P()0.723根据典型序列的条件有所以 >-0.038

4、2>-得 >0.0382含3个“1”的序列其log23.63又可计算有 >0.1909>->0.1909由上分析 所以 >0.1909（3）按编码考虑，除了含有3个或小于3个“1”的信源序列给予了一一对应的编码外，其他信源序列没有给予编码，那么这些信源序列的出现会使编码带来错误。所以，本题等长码引起的错误概率就是其他序列的发生概率之和。得0.0017若按契比雪夫不等式考虑即 其中由上面计算而 所以 比较二种计算结果，可见 这是因为按照契比雪夫不等式所计算错误概率时，我们只是对典型序列进行编码，非典型不编码就引起错误。现典型序列个数为而我们实际是对所有含3个和

5、小于3个“1”的信源序列都进行编码，其个数M,所以 4.3有一信源它有六种可能的输出，其概率分布如下图所示，表中给出了对应的码A、B、C、D、E和F。（1）求这些码中哪些是唯一可以码。（2）求哪些是非延长码（即时码）（3）对所有唯一可译码求出其平均码长消息P（ai）ABCDEFa1a2a3a4a5a61/21/41/161/161/161/1600000101001110010100101101110111101111101011011101111011111001011011101011110101011001101111011110100101110111011解：（1）A码为等长码且是非

6、奇异码 所以是唯一可译码B码和C码由唯一可译码的判定方法知识唯一可译码D码由Craft不等式知不满足不等式所以不是唯一可译码E码由即时码的定义知E码是即时码所以是唯一可译码F码由craft不等式知道所以不是唯一可译码4.4证明定理4.6。若存在一个码长为l1 ,l2 .lq的惟一可译码，则一定存在具有相同码长的即时码。证明：由定理4可知若存在一个码长为的唯一可译码，则必定满足kraft不等式1。由定理4可知若码长满足kraft不等式，则一定存在这样码长的即时码。所以若存在码长的唯一可译码，则一定存在具有相同码长P（y=0）的即时码。4.5 设信源=，=1对此信源编码将r元唯一可译变长码（即码符

7、号集X=1，2， r），其对应的码长为（ ， ， ）=（1，1，2，3，2，3）求r值的最好下限。解：要将此信源编码成为 r元唯一可译变长码，其码字对应的码长 （l1 ,l2 ,l3, l4,l5, l6）=(1,1,2,3,2,3) 必须满足克拉夫特不等式，即所以要满足 ，其中 r是大于或等于1的正整数。可见，当r=1时，不能满足Kraft不等式。 当r=2, ,不能满足Kraft。 当r=3, ,满足Kraft。所以，求得r的最大值下限值等于3。4.6 试证明对于马尔可夫信源同样存在：其中是长为N的马氏链的平均码长,而是马尔可夫信源的熵。证明：由香农第一定理：又一般马尔可夫信源的

8、信息熵应该是其平均符号熵的极限值，即故可得离散马尔可夫信源为当N=1时，有 ；当时，有 马尔可夫信源 ， 即证。4.8求概率分布为信源的二元霍夫曼码。讨论此码对于概率分布为的信源也是最佳二元码。解：信源的概率分布为：二元霍夫曼码：00，10，11，010，011码长：2，2，2，3，3当信源给定时，二元霍夫曼码是最佳二元码。所以对于概率分布为的信源，其最佳二元码就是二元霍夫曼码。这二元霍夫曼码一定是三个信源符号的码长为2（码符号/信源符号），另二个信源符号的码长为3（码符号/信源符号），其平均码长最短。因此，上述对概率分布为信源所编的二元霍夫曼码也是概略分布为信源的最佳二元码。4.9设二元霍夫

9、曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这些霍夫曼码的信源的所有概率分布。解：由题意 假设信源所发出的是个符号的概率为由霍夫曼编码的特点知：根据霍夫曼编码的方法，每次概率最小的两个信源符号合并成一个符号，构成新的缩减信源，直至最后只剩两个符号。而且当缩减信源中的所有符号概率相等时，总是将合并的符号放在最上面。所以，对于二元霍夫曼码为（00，01，10，11）来说，每个信源都要缩减一次，所以要大于和，这时必有同理对于二元霍夫曼码为（0，10，110，111）有信源概率分布满足以上条件则其霍夫曼编码符合题意。4.10 设信源符号集=（1）求和信源剩余度。（2）设

10、码符号为X=0,1，编出S的紧致码，并求S的紧致码的平均码长。（3）把信源的N次无记忆扩展信源编成紧致码，试求N=2,3,4,时的平均码长。解：（1）信源其 0.469 比特/符号剩余度0.531=53.1(2) 码符号X=0,1,对信源S编紧致码为：，其平均码长=1 码符号/信源符号(3) 当N=2时=紧致码（即霍夫曼码）为码字 0 , 10 , 110 , 111码长 1 , 2 , 3 , 3平均码长=0.645 码符号/信源符号N=3时，=对信源进行霍夫曼编码，其紧致码为码字 0 , 100 , 101 , 110 , 11100 , 11101 , 11110 , 11111码长 1

11、 , 3 , 3 , 3 , 5 , 5 , 5 , 5平均码长 =0.533 码符号/信源符号N=4时，=对信源进行霍夫曼编码，其紧致码为码字0 , 100 , 101 , 110 , 1110 , 111110 , 1111000 , 1111001,码长 1 , 3 , 3 , 3 , 4 , 6 , 7 , 7 , 码字 1111010 , 1111011 , 1111110 , 111111101 , 111111110 , 111111111 , 1111111000 , 1111111001码长 7 , 7 , 7 , 9 , 9 , 9 , 10 , 10平均码长=0.493

12、码符号/信源符号N=时，根据香农第一定理，其紧致码的平均码长=0.469 码符号/信源符号(4) 编码效率 (r=2)码剩余度 1 (r=2)所以 N=1 编码效率0.469 码剩余度0.531=53.1% N=2 0.727 0.273=27.3% N=3 0.880 0.120=12% N=4 0.951 0.049=4.9% 从本题讨论可知，对于变长紧致码，当N不很大时，就可以达到高效的无失真信源编码。4.11信源空间为 =码符号为x=0,1,2,试构造一种三元紧致码.解:构造三元紧致码(三元霍夫曼码)要使短码得到充利用就必须让信源符号个数q满足q=(r-1)+r信源s的三元霍夫曼码如下

13、： 0.4s1 0.4 0.4 0.4 0.2 0.2s2 0.2 0.2 0.1 0.1s3 0.1 0.1s4 0.1 0.1s5 0.05 0.05s6 0.05 0.05s7 0.05s8 0.05s9 0得信源符号 s1 s2 s3 s4 s5 s6 s7 s8三元紧致码 1 00 02 20 21 22 010 0114.12某气象员报告气象状态，有四种可能的消息：晴、云、雨和雾。若每个消息是等概的，那么发送每个消息最少所需的二元脉冲数是多少？又若四个消息出现的概率分别是1/4，1/8，1/8和1/2，问在此情况下消息所需的二元脉冲数是多少？如何编码？解： 第一种情况：需要二元脉冲

14、数两个，可表示四种状态，满足我们的要求。第二种情况：我们采用霍夫曼可编为1/2编为 1；1/4编为01，1/8编为000和001，脉冲数显然。4.13 若某一信源有个符号，并且每个符号等概率出现，对这信源用最佳霍夫曼码进行二元编码，问当和时，每个码字的长度等于多少？平均码长是多少？解：当时用霍夫曼编码方法进行最佳编码，由于每个符号是等概率分布的，所以每个符号码长应相等，这样平均码长最短，而且信源符号个数正好等于，则满足：所以每个码字的码长。当个1时，因为每个符号等概率分布出现，所以每个符号的码长也应该基本相等，但现在信源符号个数不是正好等于，所以必须有两个信源符号的码长延长一位码长，这样平均码

15、长最短。所以时个码字的码长为，其余2个码字的码长为。平均码长。4.14 设信源S：s1, s2, , sM1, sM P(S)：p1, p2, , pM-1, pM并满足pi1和p1>p2> pM-1> pM。试证明对于信源S一定存在这样的二元最佳码。其码字WM-1和WM具有相同的长度，且WM-1与WM只有最后一位码符号不同（分别为1和0）。证明： 对于一个最佳码来说，对信源符号sM所编的码字WM，它的码长lM必定不短于其他码字的码长li(i1,2,M-1)，假如不这样，设某个Wi其码长li>lM，可把码字WM与Wi的位置对换，这样会使平均码长发生变化，这种位置变换所引

16、起的码长变化的差等于：pilM+pMli-pili-pMlM=(pi-pM)(lM-li)因为pipM，lM<li，所以0。这就是说，位置的交换，平均码长不会增加，只会减少，所以这种置换一直进行下去，直到最后，使信源符号对应的码字WM其码长lM不小于任一其他码字的码长。由上可知，码字WM的码长是所有码字中最长的。若lMlM-1，lM>lM-1，那么根据二元码的码长li可找到一种即时码，可用树图法表示，根据码树的编码方法，必定从某一中间节点伸出二枝组成码字WM和WM-1，因为WM的码长最长，所以必定在树梢端点上，若lM>lM-1，即可将树枝缩短一节，而不影响惟一可译性。因为二元

17、码树每一节点伸出的二枝杈，只有一位码符号不同，所以可得WM和WM-1长度相同，而最后一位码符号不同。假如WM中去掉最后一位码元后的码符号序列WM-1中去掉最后一位码元后的码符号序列，因为编码的惟一可译性，一定有一个信源符号si，其概率为pi，而码字Wi与WM去掉最后一位码元后的码符号序列相同，lM-1li，而pipM-1，所以可将Wi与WM-1两码字互相置换，而不增加平均长度。综上可得，码字WM和WM-1具有相同的长度，且只有最后一位码符号不同。4.15设码C是均匀概率分布P（1/n，1/n）信源的二元霍夫曼码。并设码C中各码字的码长为li ，又设na2k，而1a2。（1）证明对于此等概率信源

18、的所有即时码中，码C的总码长T最短。（2）证明码C满足1。（3）证明码C中，对所有i满足liL或liL1其中L=maxli。（4）设u是码长为L-1的码字个数，v是码长为L的码字个数，根据a，k确定u，v和L.证明：（1） 信源S共有n = a，个符号，并且为等概率分布。设码C为此信源的二元霍夫曼码，各码字的码长为。根据定理已知，信源给定时二元霍夫曼码一定是最佳即时码，即所有可能的即时码中它是平均码长最短的码。若设是任意其他即时码，根据霍夫曼码的最佳性则有 ) 也就是 设C的总码长，因为所以 设任意其他即时码的总码长，并设各码字的长度为，有 所以得 ， 得为最短（2） 设码C中。信源给定时，二

19、元霍夫曼码是最佳即时码，具有三个特性。故，时等概率分布的二元霍夫曼码一定是等长码，。 所以，当时，码C也是等长码，。 当时，码C也是等长码，令。当时，n介于和之间的某个正整数。而且，码C中最长码长和最短码长只差一个长读度。即，所有码字满足或。（3） 由上可知：当，时，则当，时，则当，时，一部分码长，另一部分码字。设码长为码字个数为，则码长为码字个数一定为。这时，克拉夫特不等式为（4） 由前证明已知。则 解得 ， 平均码长 4.16设离散无记忆信源S= S1，S2，Sq 其概率分布为p (s)，p (s)=1。而有此信源的概率分布估计q (s)，q (s)=1。相对熵为D(pq)=p (s) l

20、ogp (s)/ q (s)。证明D(pq)0，当且仅当p (s)= q (s) sS 等式成立。证明：S= S1，S2，Sq 其概率分布为p (s)，p (s)=1，且此信源熵D(pq)=p (s) logp (s)/ q (s)D(pq)=p (s) logp (s)/ q (s)= D(pq)=p (s) logq (s)/ p (s)logX 函数是型图形D(pq)= p (s) logq (s)/ p (s)logp (s) logq (s)/ p (s)=0D(pq)0并且当且仅当p (s)= q (s) 时 D(pq)=0。4.17 若有一信源每秒钟发出2.66个信源符号。将此信

21、源的输出符号送入某一个二元信道中进行传输（假设信道是无噪无损的），而信道每秒钟只传递2个二元符号。试问信源不通过编码能否直接与信道连接？若通过适当编码能否在此信道中进行无失真传输？若能连接，试说明如何编码并说明原因。解：信源其信源熵而其每秒钟发出2.66个信源符号，所以信源输出的信息速率为：送入一个二元无噪无损信道，此信道的最大信息传输率（信道容量）。而信道每秒钟只传输两个二元符号，所以信道的最大信息传输速率为：可见：。根据无噪信道编码定理（即无失真信源编码定理），因。所以总能对信源的输出进行适当的编码，使此信源能在此信道中进行无失真地传输。如果对信源不进行编码，直接将信源符号以“0”符号传送

22、，以“1”符号传送，这时因为信源输出为2.66（二元信源符号/秒），大于2（二元信道符号/秒），就会使信道输入端造成信源符号的堆积，信息不能按时发送出去。所以，不通过编码此信源不能直接与信道连接。若要连接，必须对信源的输出符号序列进行编码，也就是对此信源的N次扩展信源进行编码。但扩展次数越大，编码越复杂，设备的代价也越大，所以尽量使扩展的次数N少，而又能使信源在此信道中无失真传输。先考虑，并对二次扩展信源进行霍夫曼编码，得：二元霍夫曼码得：二次扩展编码后，送入信道的传输速率为：所以，必须考虑即对三次扩展信源进行霍夫曼编码，得：二元霍夫曼码得：三次扩展码后，送入信道额传输速率为：此时，就可以在信

23、道中进行无失真传输了。4.18 现有一幅已离散量化后的图像，图像的灰度量化分成8级，如下表所示。表中数字为相应像素上的灰度级。1111111111111111111111111111111111111111222222222222222223333333333444444444455555556666667777788888另有一无噪无损二元信道，单位时间（秒）内传输100个二元符号。（1）现将图像通过给定的信道传输，不考虑图像的任何统计特性，并采用二元等长码，问需多长时间才能传送完这幅图像？（2）若考虑图像的统计特性（不考虑图像的像素之间的依赖性），求这图像的信源熵H(S)，并对每个灰度级进

24、行霍夫曼最佳二元编码，问平均每个像素需用多少二元码符号来表示？这时需多少时间才能传送完这幅图像？（3）从理论上简要说明这幅图像还可以压缩，而且平均每个像素所需的二元码符号数可以小于H(S)比特。解：（1）因为q8，所以要满足2lq8，得出l3二元码符号/灰度级，即每个灰度级需采用三位二元码符号来传输。这幅图像空间离散后共有N100个像素，每个像素的灰度需用三个二元符号来编码，所以这幅图像采用二元等长码后共需300个二元符号来描述，所传输的信道是无噪无损信道，其每秒种传输100个二元符号，因此，需3秒钟才能传送完这幅图像。（2）若考虑图像的统计特性，把像素的灰度值作为信源S，可得： S 1 2

25、3 4 5 6 7 8 P(si) 40/100 17/100 10/100 10/100 7/100 6/100 5/100 5/100所以 H(S)P(si)P(si)2.572比特/灰度级。对此灰度级进行霍夫曼最佳二元编码：（如下）可得：LP(si)li2.63二元符号/灰度级。通过霍夫曼最佳二元编码后，每个像素平均需用2.63个二元符号，则此图像平均共需用263个二元符号来表示，因此，需2.63秒才能传送完这幅图像。（3）实际此图像的像素之间是有依赖的，这时，此图像灰度值信源S可以看成是一阶马尔可夫信源，还可以进一步看成是m阶马尔可夫信源，因此在考虑了这些依赖关系后，像素的灰度值信源S

26、的实际信息熵H<H(S)。根据香农第一定理，总可以找到一种编码，使每个灰度级的平均码长LH（极限熵），所以，这幅图像还可以进一步压缩，平均每个像素所需的二元码符号数L<H(S)。码长li 码字 灰度级 概率P(si) 0.60 1 1 1 0.40 0.40 0.40 0.40 0.40 0.40 0.23 0.373 001 2 0.17 0.17 0.20 0.20 0.13 0.23 0.10 0.17 0.174 0000 3 0.10 0.10 0.13 4 0001 4 0.10 0.10 0.10 4 0100 5 0.07 4 0101 6 0.06 4 0110

27、7 0.05 4 0111 8 0.054.19设某无记忆二元信源,概率p1=P(1)=0.1, p0=P(0)=0.9,采用下述游程编码方案:第一步,根据0的游程长度编成8个码字(同习题2.5),第二步,将8个码字变换成二元变长码,如下表所示：信源符号序列中间码二元码字1S0100001S11001001S210100001S3101100001S41100000001S511010000001S6111000000001S7111100000000S80(1) 试问最后的二元变长码是否是唯一可译码.(2) 试求中间码对应的信源序列的平均长度1. (3) 试求中间码对应的变长码二元码码字的平

28、均长度2.(4) 计算比值2/1,并解释它的意义,以及计算这种游程编码的编码效率.(5) 若用霍夫曼编码,对信源的四次扩展信源进行直接编码,求它的平均码长(对应于每一个信源符号),并计算编码效率,试将此方法与游程编码方法进行比较.(6) 将上述游程编码方法一般化,可把2S+1个信源序列(上例中s=3)变换成二元变长码,即2S个连零的信源序列编为码字0,而其他信源序列都编成s+1位的码字.若信源输出零的概率为p0,求2/1的一般表达式,并求p0=0.995时s的最佳值.解: (1) 根据唯一可译码的判断方法可知,最后的二元变长码是非延长码(即时码),所以它是唯一可译码.(2) 因为信源是二元无记

29、忆信源,所以有P(si)= P(si1) P(s2)P(sin)其中 si =( si1 si2sin) si1, si2,sin0,1已知p1=P(1)=0.1, p0=P(0)=0.9,可求得信源符号序列的概率P(si).根据编码,可排出下列表信源符号序列序列的概率P(si)信源符号序列长度l1i中间码二元码码长l2i10.11S04010.092S140010.0813S2400010.07294S34000010.065615S440000010.0590496S5400000010.05314417S64000000010.047829698S74000000000.43046721

30、8S84根据表可计算 1=5.6953 信源符号/中间码(3) 根据表计算 2=2.7086 二元码/中间码(4) 0.4756 二元码/信源符号此值为每个信源符号所需的二元码符号数,也就是无记忆二元信源采用游程编码后每个二元信源符号所需的平均码长.可计算无记忆二元信源的信息熵 H(S) =- 0.4690 比特/信源符号所以,这种游程编码的效率=0.98698.6 %(其中因为二元编码所以Hr(S)=H(S)(5)若对无记忆二元信源的次扩展信源直接进行霍夫曼编码,可得S4P(si)码字Wi码长liS4P(si)码字Wi码长li00000.65610110010.008111110107000

31、10.0729110310100.00811111011700100.0729100311000.00811111110701000.0729101301110.0009111111100910000.07291110410110.0009111111101900110.0081111110611010.0009111111110901010.00811111000711100.000911111111101001100.00811111001711110.00011111111111104=1.9702 二元码/4个信源符号得=0.4926 二元码/信源符号编码效率=0.95295.2 %此

32、编码效率低于游程编码方法.这是因为霍夫曼码只考虑N=4(固定值)时进行压缩,使概率大的对应于短码,概率小的对应于长码.但无记忆二元信源符号“0”出现的概率p0很大,所以在信源输出序列中符号“0”连续出现的概率较大,而连续出现符号“1”的概率极小.游程编码正是考虑了这些特性,使N较长(N=8)的连续出现的符号“0”序列压缩成一个二元码符号.所以,游程编码的编码效率较高.当然,当N很大时(N=8)霍夫曼编码效率会提高,但其编码方法没有游程编码方法来得简单.(6) 一般游程编码方法是将2s+1个信源序列中一个2s个连续为零的序列编成码字0,而其他信源序列编成码长为s+1的码字,所以根据表中类似计算可

33、得1=其中p0为信源中符号“0”出现的概率, p1为符号“1”出现的概率,有p0+ p1=1.展开上式,得 1 = p0+ 2p1 p0+3 p1+ =(1- p0)(1+2 p0+3+)+ =(1+2p0+3+)-( p0+2+3+) =(1+ p0+) =根据表中类似计算,得2=(s+1) =(s+1) (1- p0)(1+ p0+)+ =(s+1)(1-)+ =1+s(1-)得的一般表达式为 =当p0=0.995, p1=0.005时,求s的最佳值,也就是求s取某值时最短.可采用将对s求偏导来解,但所得为超越方程,所以我们采用数值求解方法.令 s=2 2s=4 =0.262s=3 2s=

34、8 =0.1422s=4 2s=16 =0.0849s=5 2s=32 =0.0587s=6 2s=64 =0.482s=7 2s=128 =0.0456s=8 2s=256 =0.0469 所以得最佳 当p0=0.995时二元信源的信息熵H(S) = H(0.995) 0.0454 比特/信源符号 可见,当s=7时, 已极接近H(S),编码效率达到99.5%4.20有一个含有8个消息的无记忆信源，其概率各自为0.2，0.15，0.15，0.1，0.1，0.1，0.1，0.1。试编成两种三元非延长码，使它们的平均码长相同，但具有不同的码长的方差。并计算其平均码长和方差，说明哪一种码更实用些。解

35、：对于三元编码，信源S的符号个数q必须满足q=（3-1）+3必须增加一信源符号，其概率为零。这样使q=9，=3时满足上式。列表编出两种三元霍夫曼码。码1： 0.5信源符号 码字W 码长l 概率P 0.3 0.3s1210.20.2 0.2s20020.150.15s30120.150.15s41020.100.20s51120.10s61220.10s702030.10s802130.10s90平均码长：1×0.2+2×0.15+2×0.15+2×0.1+2×0.1+2×0.1+3×0.1+3×0.1=2 三元码

36、/信源符号，方差=0.4码2： 0.5 0.3 0.3信源符号 码字W 码长l 概率P 0.2 0.2 0.2s10020.20.20.2s20120.150.150.15s30220.150.150.15s41020.10.1s51120.10.1s61220.10.1s72020.1s82120.1s92220平均码长=2 三元码/信源符号，方差=0码1和码2是平均码长相同的三元非延长码，但它们方差不同，码2的方差为零。所以，对于有限长的不同信源序列，用码2所编得的序列长度没有变化，并且相对来说码序列长度要短些。因此，码2更实用些4.21有两个信源X和Y如下：（1）分别用霍夫曼码编成二元变

37、长唯一可译码，并计算编码效率。（2）分别用香农编码法编成二元变长唯一可译码，并计算编码效率。（3）分别用费诺编码法编成二元变长唯一可译码，并计算编码效率。（4）从X,Y两种不同信源来比较着三种编码方法的优缺点。解：下面分别对信息源X和Y进行霍夫曼编码：信源X 码长Li码字Wi信源符号概率P（xi）0.610.390.390.350.350.260.260.26210X10.200.200.20211X20.190.190.193000X30.180.183001X40.170.173010X50.1540110X60.1040111X70.01其平均码长 二元符号/信源符号 编码效率： 信源Y

38、码长Li码字Wi信源符号概率P（yi）0.5111Y10.490.490.490.490.490.140.230.283001Y20.140.140.140.233010Y30.140.140.1440000Y40.070.0940001Y50.0740110Y60.04501110Y70.026011110Y80.026011111Y90.01其平均码长 二元符号/信源符号 编码效率： （2）对信息源X和Y分别进行香农编码信源X：信源符号概率P（xi）码长 码字Wi0.2030000.1930010.1830100.1730110.1531000.10410100.0171111111其平均

39、码长 二元符号/信源符号 编码效率： 信源Y：信源符号概率P（yi）码长 码字Wi0.492000.1430100.1430110.07410000.07410010.045110000.0261110010.0261110000.0171111111其平均码长 二元符号/信源符号 编码效率： （3) 对信息源X和Y分别进行费诺编码 信源X：信源符号概率P（xi）码字Wi码长 0.201001000101110020.1901030.1801130.171020.1511030.10111040.0111114其平均码长 二元符号/信源符号 编码效率： 信源Y：信源符号概率P（yi）码字Wi码

40、长 0.491000011101011100010.1410030.1410130.07110040.07110140.04111040.021111050.0211111060.011111116其平均码长 二元符号/信源符号编码效率： （4) 从信源XY 的三种不同编码方法可以看出，霍夫曼编码所得的平均码长最短，编码效率最高；香农编码所得的平均码长最长，编码效率最差，费诺居中。4.22 香农码: 信源符号集 A=1,2,q,其概率分布为pp2pq。以下面方法对信源符号进行编码。首先将概率分布按大小顺序排列pp2pq ，定义累积分布函数 Fi=pk , （k from 1to i-1），Fi

41、是所有小于I符号的概率和。于是，符号I的码字是取Fi的二进数的小数li位，若有尾数就进位到第li位，其lilog1/pi。 证明这样编码的码是即时码； 证明H(S)/L< H(S)+1 对于概率分布为(0.5，0.25，0.125，0.125）的信源进行编码，求其各码字； 由中得的码是否与此信源的霍夫曼码正好完全一致。试说明这种完全一致的一般原理。证明： 根据积累分布函数的定义，Fi的总区间为【0，1）。现编码方法是取Fi的二进数的小数li位，若有尾数就进位到li位，这li位作为符号I的码字Wi。其中li位由其概率pi确定，即取lilog1/pi。若符号累积函数为Fi=pk , （k from 1to i-1）=0.ziz2zlizli+1zli+2zli+n (zi取0或1)若zli+1 ，zli+2 ，zli+n ，全都取零（即没有尾数），其码字为Wiziz2zli 。其对应的数值为C=0. ziz2zli ,正好在累积函数Fi上，C