信息论第五章答案.doc

1、5.1 设信源 01.5.1708.92.0)( 76431 xxxXP(1) 求信源熵 H(X)；(2) 编二进制香农码；(3) 计算平均码长和编码效率。解：(1) symbolitxpXHi ii/609.2 )01.log.10g.15lg 17.0log.89l2.()()() 22 27 (2)xi p(xi) pa(xi) ki 码字x1 0.2 0 3 000x2 0.19 0.2 3 001x3 0.18 0.39 3 011x4 0.17 0.57 3 100x5 0.15 0.74 3 101x6 0.1 0.89 4 1110x7 0.01 0.99 7 1111110(

2、3) %1.834.6092)()(14.3 01.7.415.037.3)( KXHRpkii5.2 对信源 01.5.7.)( 764321 xxxP编二进制费诺码，计算编码效率。解：xi p(xi) 编码 码字 kix1 0.2 0 00 2x2 0.19 0 010 3x3 0.180 11 011 3x4 0.17 0 10 2x5 0.15 0 110 3x6 0.1 0 1110 4x7 0.011 11 1 1111 4%2.9574.60)()(74.2 01.4.15.037.18.3.2)( KXHRxpkii5.3 对信源 01.5.1708.92.0)( 76431

3、xxxXP编二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。解：二进制哈夫曼码：xi p(xi) 编码 码字 kis6 1 s5 0.61 0 s4 0.39 1 s3 0.35 0 s2 0.26 1 x1 0.2 0 10 2x2 0.19 1 11 2x3 0.18 0 000 3x4 0.17 1 001 3x5 0.15 0 010 3s1 0.11 1 x6 0.1 0 0110 4x7 0.01 1 0111 4%9.572.60)()(2. 01.4.15.037.8.3.)( KXHRpkii三进制哈夫曼码：xi p(xi) 编码 码字 kis3 1 s2 0.54 0

4、 s1 0.26 1 x1 0.2 2 2 1x2 0.19 0 00 2x3 0.18 1 01 2x4 0.17 2 02 2x5 0.15 0 10 2x6 0.1 1 11 2x7 0.01 2 12 2%4.913log8.1602log)()(8.1 )01.5.07.(.)(2 mLKXHRxpkii5.4 设信源 12864321842)( 7541 xxxXP(1) 求信源熵 H(X)；(2) 编二进制香农码和二进制费诺码；(3) 计算二进制香农码和二进制费诺码的平均码长和编码效率；(4) 编三进制费诺码；(5) 计算三进制费诺码的平均码长和编码效率；解：(1)symboli

5、txpXHi ii/984.1 128log128log64log132log16log18l4g2l)(l)()( 222281 =127/64 bit/symbol(2)二进制香农码：xi p(xi) pa(xi) ki 码字x1 0.5 0 1 0x2 0.25 0.5 2 10x3 0.125 0.75 3 110x4 0.0625 0.875 4 1110x5 0.03125 0.9375 5 11110x6 0.015625 0.96875 6 111110x7 0.0078125 0.984375 7 1111110x8 0.0078125 0.9921875 7 1111111

6、二进制费诺码：xi p(xi) 编码 码字 kix1 0.5 0 0 1x2 0.25 0 10 2x3 0.125 0 110 3x4 0.0625 0 1110 4x5 0.03125 0 11110 5x6 0.0156251 11 11 0 111110 6x7 0.0078125 0 1111110 7x8 0.0078125 1 1 1111111 7(3)香农编码效率： %10984.)()(6/127984. 1287645321462)( KXHRxpkii费诺编码效率： %10984.)()(984.1 712864153262)( KXHRxpkii(4)xi p(xi)

7、 编码 码字 kix1 0.5 0 0 1x2 0.25 1 1 1x3 0.125 0 20 2x4 0.0625 1 21 2x5 0.03125 0 220 3x6 0.015625 1 221 3x7 0.0078125 0 2220 4x8 0.0078125222 1 2221 4(5) %3.94log328.1log)()(328.1 2843616141)(2 mKXHRpkii5.5 设无记忆二进制信源 .09)(P先把信源序列编成数字 0，1，2，8，再替换成二进制变长码字，如下表所示。(1) 验证码字的可分离性；(2) 求对应于一个数字的信源序列的平均长度 1K；(3)

8、 求对应于一个码字的信源序列的平均长度 ；2(4) 计算 12K，并计算编码效率；(5) 若用 4 位信源符号合起来编成二进制哈夫曼码，求它的平均码长 ，并计算编码效率。K序列 数字 二元码字1 0 100001 1 1001001 3 10100001 3 101100001 4 1100000001 5 11010000001 6 111000000001 7 111100000000 8 0解：（1）满足 Kcraft 不等式： ；由码树图可见，没有一个码字是其它码字的1282491iKi前缀，码字均在树的终结点。所以码字可分离。（2）序列长度、序列概率及二元码长如下表所示：序列 序列长

9、度 Li 序列概率 pi 数字 二元码长 Li 二元码字1 1 0.1 0 4 100001 2 0.10.9 1 4 1001001 3 0.10.92 3 4 10100001 4 0.10.93 3 4 101100001 5 0.10.94 4 4 1100000001 6 0.10.95 5 4 11010000001 7 0.10.96 6 4 111000000001 8 0.10.97 7 4 111100000000 8 0.98 8 1 0信信/.693591iiLpK（3） 信/.bitii7082912（4） , 此值表示无记忆二元信源采用游程长度编码后每个二元信源需信

10、/.itK45612要的平均码长。 ，信/.)(log)()( bitxpXHii 469021i2%./)(69812KXH801234567 0111110000（5）4 位信源符号的联合概率、Huffman 编码及码长如下表：（码字可以不同，但码长一样）S4 P(Si) 码字 Wi 码长 Li S4 P(s) 码字 Wi 码长 Li0000 0.6561 0 1 1001 0.0081 1111010 70001 0.0729 110 3 1010 0.0081 1111011 70010 0.0729 100 3 1100 0.0081 1111110 70100 0.0729 101

11、 3 0111 0.0009 111111100 91000 0.0729 1110 4 1011 0.0009 111111101 90011 0.0081 111110 6 1101 0.0009 111111110 90101 0.0081 1111000 7 1110 0.0001 1111111110 100110 0.0081 1111001 7 1111 0.0001 1111111111 10%.)( /./,/.295 4926047014164KXHSymbitKSymbitLspii5.6 有二元平稳马氏链，已知 p(0/0) = 0.8，p(1/1) = 0.7，求它的

12、符号熵。用三个符号合成一个来编写二进制哈夫曼码，求新符号的平均码字长度和编码效率。解：平稳时马尔科夫状态的概率：解得：170801)()(.(.(SPSPp 52310/)(一阶马氏信源的熵： symbitSPSpHj ijijii /.logllog)|(l|)( 78602535214210270130185311321 .)|(,.)|( ,/),/ )|(|()( SpSpS1S2S3 P(S1S2S3) Li Wi S1S2S3 P(S1S2S3) Li Wi000 48/125 1 1 011 21/250 4 0011111 49/250 3 000 110 21/250 4 0

13、100001 12/125 3 011 010 9/250 5 01010100 12/125 4 0010 101 3/125 5 01011%./. )()()()(1490336257 1230921501425091581191 KHsymbitLspii11 0 10 1 01 1 00 1 11 0 00 0 11 1 10 0 06 / 2 5 09 / 2 5 02 1 / 2 5 02 1 / 2 5 02 4 / 2 5 02 4 / 2 5 04 9 / 2 5 09 6 / 2 5 01 5 / 2 5 03 6 / 2 5 04 5 / 2 5 06 0 / 2 5

14、09 4 / 2 5 01 5 4 / 2 5 000000011111105.7 对题 5.6 的信源进行游程编码。若“0”游程长度的截止值为 16， “1”游程长度的截止值为 8，求编码效率。解：一阶马氏信源的熵同上题， symbitH/.78601二元平稳一阶记忆序列“0”游程的长度概率： 100150 001532ii liiili plpl )(,.,)(/二元平稳一阶记忆序列“1”游程的长度概率： 117101732ii liiili plpl )(,.,)(/“1”游程长度的熵：信/.2),()( log)(log loglog)(ll)( l)(loglog)( loglog)

15、(l l)(log loglogl / / / / / / /bitpHp ppppp pplpp pplplplH iii i iii ii ii lll l lill ll l iiilii 691117111017 1217021 71271127112110271 71271711210102717 71271127101021071 71271102107 712711211121 11 1 同理， “0”游程长度的熵： 信/.),()( / bitppli 483101005分别对“0”和“1”游程序列进行 Huffman 编码，并分别计算出它们的编码效率。“0”游程序列的长度、对

16、应得概率、Huffman 编码的二元码长及码字序列 序列长度 Li 序列概率 pi 数字 二元码长 Li 二元码字0 1 P1/0 0 2 1100 2 P0/0 P 1/0 1 3 001000 3 P0/02 P 1/0 2 3 0110000 4 P0/03 P 1/0 3 3 1010000,0 5 P0/04 P 1/0 4 4 00010000,00 6 P0/05 P 1/0 5 4 01010000,000 7 P0/06 P 1/0 6 4 10010000,0000 8 P0/07 P 1/0 7 5 000000000,0000,0 9 P0/08 P 1/0 8 5 0

17、10010000,0000,00 10 P0/09 P 1/0 9 5 100010000,0000,000 11 P0/010 P 1/0 A 6 0000100000,0000,0000 12 P0/011 P 1/0 B 6 1000000000,0000,0000,0 13 P0/012 P 1/0 C 6 1000010000,0000,0000,00 14 P0/013 P 1/0 D 7 00001100000,0000,0000,000 15 P0/014 P 1/0 E 7 00001110000,0000,0000,0000 16 P0/015 F 5 01000数 字 符

18、 号信 源 符 号 /. )()( )()()(513 51765432176 511432 1030900200 511032010 102072020162 ppppp pppppLpii %./ 1948200 LlHi“1”游程序列的长度、对应得概率、Huffman 编码的二元码长及码字：序列 序列长度 Ki 序列概率 pi 数字 二元码长 Ki 二元码字1 1 P0/1 0 2 0111 2 P0/1 P 1/1 1 2 10111 3 P0/1 P 1/12 3 3 0011111 4 P0/1 P 1/13 3 3 1101111,1 5 P0/1 P 1/14 4 4 0001

19、1111,11 6 P0/1 P 1/15 5 4 11101111,111 7 P0/1 P 1/16 6 4 11111111,1111 8 P 1/17 7 4 0000数 字 符 号二 元 码 字 /. )()( /732 14321 71214021081 ppppKii %./7598621lHi %./ 110 9732564820 KLlHlll iiii 可见满足 ，这里的“0”游程编码效率高，因为游程长度长，而“1”游程编码效率受游1程的长度限制显得比“0”游程编码效率略低一些，因此整体的编码效率介于两者之间。5.8 选择帧长 N = 63(1) 对 00100000,00

20、000000,00000000,00000000,01000000,00000000,00000000,0000000 编 L-D 码；(2) 对 10000100,00101100,00000001,00100001,01001000,00000111,00000100,0000001 编 L-D 码再译码；(3) 对 0000000000000000000000000000000000000000000000000000000000000000 编 L-D 码；(4) 对 10100011010111000110001110100110000111101100101000110101011

21、010010 编 L-D 码；(5) 对上述结果进行讨论。解：（1）本帧内信息位数 Q=2；各信息位位置值 n1=3，n 2=34；帧长 N=63。53082134131 CCTQjjnQ 位和 T 位需要的二进制自然码位数分别是：1953195362263 log,)(logN所以，L-D 编码结果：000010,01000010010解码：已知 N=63，故前 6 位为 Q 的自然码表示，所以 Q=2；后 11 位为 T 的自然码表示，得T=530寻找某一值 K，使得：K=33,5, 221130KKQQ CCT即 ：再令， 821 K再次寻找某一值 L，使得： L=2, 1111 2LL

22、QQ即 ：所以解码出信息位的位置值是 n1=3，n 2=34(2) 对 10000100,00101100,00000001,00100001,01001000,00000111,00000100,00000010 编 L-D 码本帧内信息位数 Q=15；各信息位位置值n1=1，n 2=6，n 3=11，n 4=13，n 5=14，n 6=24，n 7=27，n 8=32，n 9=34，n 10=37，n 11=46，n 12=47，n 13=48，n 14=54，n 15=63；帧长 N=63。 9470956282093057412240397 51871586 3611 1563145134812471461037934 82726254332611 CCCTQjjQ 位和 T 位需要的二进制自然码位数分别是：38162156322log,log)(logCN所以，L-D 编码结果：001111，1010110,11111101,01111111,10110101,00011000,11111110解码：已知 N=63，故前 7 位为 Q 的自然码表示，所以 Q=15；后 47 位为 T 的自然码表示，得T= 95646769289470(a) 寻找某一值 K，使得：K=62, 15151 94709628 KKQ CCTC信(b)令，