信源編碼 習(xí)題解答

1、第四章信源編碼 習(xí)題解答1、一個信源由6個消息組成，其概率分布已知，對其進(jìn)行信源編碼得如下表所示6種編碼方法：信源Xp(X)ABCDEFGx11/200000011011x21/400101101000000101x31/160100111101101001100101x41/160110111111011000101010011x51/1610001111111101001110110101x61/16101011111111110111110111110011） 哪些是非奇異碼？哪些是唯一可譯碼？哪些是即時碼？2） 分別計算每個唯一可譯碼的平均碼長和編碼效率。解：1）A、B、C、D、E、F

2、是非奇異碼。A、B、C、F是唯一可譯碼（E不滿足克拉夫特不等式）。A、C、F是即時碼（B是續(xù)長碼）。3） 編碼A：平均碼長：信源熵：比特/消息編碼效率：編碼B和C：平均碼長：編碼效率：編碼F：平均碼長：編碼效率：2、離散無記憶信源X的概率空間為：1）對其進(jìn)行費諾編碼，并計算其編碼效率；2）對其進(jìn)行哈夫曼編碼，并將其編碼效率與費諾編碼相比較。解：1）費諾編碼：信源Xp(X)編碼過程 碼字碼長 x10.2000002x20.19100103x30.1810113x40.1710102x50.15101103x60.101011104x70.01111114平均碼長：碼元/符號信源熵：編碼后平均碼元

3、熵：比特/碼元編碼效率：2）哈夫曼編碼：碼長碼字信源X0100.11100.2610.35110.391000.6101.0p(X)210x10.20211x20.193000x30.183001x40.173010x50.1540110x60.1040111x70.01平均碼長：碼元/符號編碼后平均碼元熵：比特/碼元編碼效率：與費諾編碼相比，哈夫曼編碼的編碼效率要高于費諾編碼。一般情況下哈夫曼編碼效率較高，但費諾編碼如果每次劃分概率很接近，則效率也很高。3、離散無記憶信源X的概率空間為：1）對其進(jìn)行費諾編碼；2）對其進(jìn)行哈夫曼編碼。解：1）費諾編碼：信源Xp(X)編碼過程 碼字碼長 x10.

4、2200002x20.201012x30.181001003x50.1511013x40.1101103x80.081011104x70.0510111105x60.0211111152）哈夫曼編碼：4、離散無記憶信源S描述為：1）計算信源熵及其冗余度； 2）對其進(jìn)行費諾編碼；3）對其進(jìn)行哈夫曼編碼；4*）對其進(jìn)行香農(nóng)-費諾-埃利阿斯編碼；5*）對其進(jìn)行香農(nóng)編碼；6）計算哈夫曼碼的平均碼長、編碼效率和碼冗余度；7）把哈夫曼編碼器的輸出看成一個新信源X，計算其概率分布p(x1) 和 p(x2)；8）Hp(x1), p(x2) 是否等于H碼（即平均碼元熵）？為什么？解：1）信源熵：冗余度：2）費諾

5、編碼：信源Sp(S)編碼過程 碼字 碼長 s10.3700002s20.251012s40.1810 102s30.1101103s60.071011104s50.031111143）哈夫曼編碼：4） 香農(nóng)-費諾-埃利阿斯編碼：信源Sp(S)F(s)的二進(jìn)制數(shù) 碼長碼字s10.370.370.185 0.00101.3001s20.250.620.495 0.01111.3011s40.180.800.71 0.101101.41011s30.10.900.850.1101100.511011s60.070.970.9350.1110111.511101s50.031.000.9850.111

6、111000.711111105）香農(nóng)編碼：信源Sp(S)F(s)F(s) 的二進(jìn)制數(shù)碼長碼字 s10.3700.000.200s20.250.370.010.201s40.180.620.1001.3100s30.10.80.11001.41100s60.070.90.11100.41110s50.030.970.1111100.61111106）分析哈夫曼碼，其平均碼長：平均碼元熵：編碼效率：碼冗余度：7）把哈夫曼編碼器的輸出看成一個新信源X，計算其概率分布p(x1) 和 p(x2)：8）計算相比平均碼元熵：可見，兩者很相近，但理論上不相同。因為平均碼元熵計算的是算術(shù)平均值，而作的是統(tǒng)計平

7、均。5. 設(shè)有6個消息，其出現(xiàn)概率分別為 A B C D E F 1/16 1/16 2/16 3/16 4/16 5/16 將它們分別進(jìn)行費諾編碼和霍夫曼編碼，并比較編碼效率。是否在任何情況下費諾編碼比霍夫曼編碼效率都低？解：信源：費諾編碼：信源Xp(X)編碼過程 碼字 碼長 F5/1600002E4/161012D3/1610 102C2/16101103B1/161011104A1/16111114平均碼長：碼元/符號信源熵：比特/符號編碼后平均碼元熵：比特/碼元二元信源最大碼元熵為1比特/碼元，故編碼效率：哈夫曼編碼：由于平均碼長與費諾編碼一樣，故編碼效率也為99%。一般情況下哈夫曼編