第四章信源编码 习题解答1、一个信源由1） 哪些是非奇异码？哪些是唯一可译码？哪些是即时码？ 2） 分别计算每个唯一可译码的平均码长和编码效率。
解：1）A 、B 、C 、D 、E 、F 是非奇异码。
A 、B 、C 、F 是唯一可译码（E 不满足克拉夫特不等式）。
A 、C 、F 是即时码（B 是续长码）。
3） 编码A ：平均码长：3A L = 码元/消息 信源熵：111111()lb lb 4lb 222441616H X =---⨯=比特/消息 编码效率：max ()/2/366.7%lb21A H H X L H η====码码编码B 和C ：平均码长：11111123456 2.1252416161616B C L L ==+⨯+⨯+⨯+⨯+⨯= 码元/消息 编码效率：max ()/2/2.12594.1%lb21B C H H X L H ηη=====码码编码F ：平均码长：111234 2.52416F L ⎛⎫=⨯+⨯+⨯= ⎪⎝⎭ 码元/消息 编码效率：max ()/2/2.580%lb21F H H X L H η====码码2、离散无记忆信源X 的概率空间为：1234567()0.200.190.180.170.150.100.01X x x x x x x x p X ⎧⎫⎡⎤=⎨⎬⎢⎥⎩⎭⎣⎦ 1）对其进行费诺编码，并计算其编码效率；2）对其进行哈夫曼编码，并将其编码效率与费诺编码相比较。
解：1）费诺编码：平均码长：()()()0.20.1720.190.180.1530.10.014 2.74L =+⨯+++⨯++⨯=码元/符号 信源熵：()0.20lb0.200.19lb0.190.18lb0.180.17lb0.170.15lb0.150.1lb0.10.01lb0.01 2.60/874H X =-------= 比特符号编码后平均码元熵：() 2.608740.95212.74H X H L===码比特/码元编码效率：max 0.952195.21%lb2H H η===码码2）哈夫曼编码： 码长 码字 信源X p (X ) 2 10 x 1 2 11 x 2 3 000 x 3 3 001 x 4 3 010 x 5 4 0110 x 6 40111x 7平均码长：()()()0.20.1920.180.170.1530.10.014 2.72L =+⨯+++⨯++⨯=码元/符号 编码后平均码元熵：() 2.608740.95912.72H X H L===码比特/码元编码效率：max 0.959195.91%lb2H H η===码码与费诺编码相比，哈夫曼编码的编码效率要高于费诺编码。
一般情况下哈夫曼编码效率较高，但费诺编码如果每次划分概率很接近，则效率也很高。
3、离散无记忆信源X 的概率空间为：12345678()0.220.200.180.10.150.020.050.08X x x x x x x x x p X ⎧⎫⎡⎤=⎨⎬⎢⎥⎩⎭⎣⎦ 1）对其进行费诺编码；2）对其进行哈夫曼编码。
解：1信源X p (X ) 编码过程 码字 码长 x 1 0.22 00 00 2 x 2 0.20 1 01 2 x 3 0.18 1 00 100 3 x 5 0.15 1 101 3 x 4 0.1 1 0 110 3 x 8 0.08 10 1110 4 x 7 0.05 10 11110 5 x 60.0211111152）哈夫曼编码：4、离散无记忆信源S 描述为：123456()0.370.250.10.180.030.07S s s s s s s p S ⎧⎫⎡⎤=⎨⎬⎢⎥⎩⎭⎣⎦ 1）计算信源熵及其冗余度；2）对其进行费诺编码；3）对其进行哈夫曼编码；4*）对其进行香农-费诺-埃利阿斯编码； 5*）对其进行香农编码；6）计算哈夫曼码的平均码长、编码效率和码冗余度；7）把哈夫曼编码器的输出看成一个新信源X ，计算其概率分布p (x 1) 和 p (x 2)； 8）H [p (x 1), p (x 2)] 是否等于H 码（即平均码元熵）？为什么？ 解：1）信源熵：()0.37lb0.370.25lb0.250.18lb0.180.1lb0.10.07lb0.070.03lb0.03 2.229H S =------= 比特/消息冗余度：max ()2.231113.788%()lb6H S E H S =-=-=2）费诺编码：信源S p (S ) 编码过程 码字 码长 s 1 0.37 00 00 2 s 2 0.25 1 01 2 s 4 0.18 1 0 10 2 s 3 0.1 10 110 3 s 6 0.07 10 1110 4 s 50.031111143）哈夫曼编码：4） 香农-费诺-埃利阿斯编码：信源S p (S ) F (s ) ()F s()F s 的二进制数 码长 码字s 1 0.37 0.37 0.185 0.00101.. 3 001 s 2 0.25 0.62 0.495 0.01111.. 3 011 s 40.180.800.710.101101..410115）香农编码：6）分析哈夫曼码，其平均码长：61()2(0.370.250.18)30.14(0.07+0.03=2.3i i i L p s l ===⨯+++⨯+⨯∑） 码元/消息平均码元熵：() 2.2290.968962.3H S H L===码 比特/码元 编码效率：max 0.97096.896%lb2H H η===码码码冗余度：max 0.9689611 3.104%lb2H E H η==-=-=码码码1-7）把哈夫曼编码器的输出看成一个新信源X ，计算其概率分布p (x 1) 和 p (x 2)：11211()(0)0.370.250.10.03+0.07=0.60422342p x p ==+⨯+⨯+⨯⨯21131()(1)0.250.10.180.030.070.39582342p x p ==⨯+⨯++⨯+⨯=8）计算12[(),()](0.6042,0.3958)0.6042lb0.60420.3958lb0.39580.9685 /H p x p x H ==--=比特码元 相比平均码元熵：12() 2.2290.96896[(),()]2.3H S H H p x p x L===≈码 比特/码元 可见，两者很相近，但理论上不相同。
因为平均码元熵计算的是算术平均值，而12[(),()]H p x p x 作的是统计平均。
5. 设有6个消息，其出现概率分别为A B C D E F 1/16 1/16 2/16 3/16 4/16 5/16将它们分别进行费诺编码和霍夫曼编码，并比较编码效率。
是否在任何情况下费诺编码比霍夫曼编码效率都低？解：信源：112345()161616161616A B C D E F X p X ⎧⎫⎡⎤⎪⎪=⎨⎬⎢⎥⎣⎦⎪⎪⎩⎭费诺编码：信源X p (X ) 编码过程 码字 码长 F 5/16 00 00 2 E 4/16 1 01 2 D 3/16 1 0 10 2 C 2/16 10 110 3 B 1/16 10 1110 4 A1/16111114平均码长：543211234 2.375161616161616L ⎛⎫⎛⎫=++⨯+⨯++⨯=⎪ ⎪⎝⎭⎝⎭码元/符号信源熵：111111331155()lb lb lb lb lb lb 2.35216161616881616441616H X =------=比特/符号 编码后平均码元熵：() 2.3520.992.375H X H L===码比特/码元 二元信源最大码元熵为1比特/码元，故编码效率：max 0.9999%1H H η===码码哈夫曼编码：由于平均码长与费诺编码一样，故编码效率也为99%。
一般情况下哈夫曼编码效率较高，但费诺编码如果每次划分概率很接近，则效率也很高。
6. 有一冗余位序列，N =15，码字为001000000010000，试将其编成L-D 码，并将L-D 码译回原序列。
解：001000000010000 N=15 编码：[]()2112212111111312152,3,1145247105 lb105 6.77 lb 151 4n n Q n n T C C C C C ----====+=+=+====+=⎡⎤⎣⎦已知：计算： 24477Q T ==将转变成位二进制数，转变成位二进制数，于是得L-D 码： 0010 0101111译码：221011215,2,4745475510111N Q T C C n ====≤<==+=修正：21101123147452223213T T C C C n =-=-==≤<==+=故译码恢复出原序列：001000000010000作业：1、2、4。