信息论编码与纠错课后作业答案3

本文格式为Word版，下载可任意编辑——信息论编码与纠错课后作业答案3第三章作业参考答案：

3.2答：

（1）当nlogD?LH(X)时，可实现无失真编码；

（2）等长编码时，从总的趋势来说，增加L可提高编码效率，且当L??时，

??1。但不一定L的每次增加都一定会使编码效率提高。

3.7答：

码1：其二次扩展码是奇异码，如u1u2和u5u1对应的码字均为010；

码2：是唯一可译码，非奇异等长码是唯一可译码，且是即时码，平均码长为3；

749n??3.06码3：是延长码，是唯一可译码，但不是即时码，平均码长为?pini?i?116码4：是非延长码，故是唯一可译码，也是即时码；平均码长为

749n??pini??3.06

i?116721?2.625；码5：是树码，即非延长码，因此是即时码；平均码长为n??pini?

i?18725n??3.125码6：是非延长码，因此是即时码；平均码长为?pini?i?18综上所述，码2~6均为唯一可译码，码2、4、5、6是即时码。3.8解：

（1）由等长编码定理n?LH(X)log4??2位logDlog2x4?3??1??，将其（1/2）的幂次{1，2，3，3}依次取????2??（2）按概率进行编码，出现概率大的编短码，概率小的编长码

x2?x1X???取?????1?1?1?2?P????????2??2?x3?1????2?3出作为每个符号的码长，即可得到紧致码。

1111此时H(X)?H(,,,)?1.75bit/符号

2488平均码长n??pini?1.75

i?14编码效率??LH(X)?1

nlogD因此验证了上述编码方法得到的是紧致码。

3.14解：

（1）H(X)?H(0.9,0.1)?0.469bit/符号（2）信源序列平均长度

l??pili

i?08?0.1?1?0.9?0.1?2?0.92?0.1?3?0.93?0.1?4???0.97?0.1?8?0.98?8?2.596（3）平均码长

n?0.98?1?[1?0.98]?4?2.7086码元/符号

（4）首先码长组合满足克拉夫特不等式，即?2?n?8?2?4?2?1?1

i8i?0又该码为非延长码，故唯一可译。3.17解：

（1）D=2香农编码

i12345678pi0.20.16670.16670.10.10.10.08330.0833Qi00.20.36670.53340.63340.73340.83340.9167-logpi2.322.582.583.323.323.323.5863.59ni33344444代码组00000101010001010101111011110n?0.5334?3?0.4664?4?3.4666码元/符号

??LH(X)2.92??100%?84.23%

nlogD3.4666（2）D=2费诺编码

n?0.2?3?0.6334?3?0.1667?4?2.97码元/符号

??

LH(X)2.92??100%?98.3%

nlogD2.97i12345678Pi1/51/61/61/101/101/101/121/12第一次分解其次次分解0(8/15)0(1/5)1(1/3)1(7/15)0(1/5)1(4/15)第三次分解第四次分解代码组000(1/6)1(1/6)0(1/10)1(1/10)0(1/10)1（1/6）0（1/12）1（1/12）01001110010111011101111（3）D=3霍夫曼编码

序号概率编码过程码字码长21123456781/51/61/61/101/101/101/121/12210101/63/1021001/21.00212023111022122023222233

n?1.9666码元/符号

??LH(X)2.92??100%?93.68%

nlogD1.9666?log3（4）D=4霍夫曼编码

n?1.6332码元/符号

??LH(X)2.92??100%?89.4%

nlogD1.6332?log4序号概率编码过程码字码长3123456781/51/61/61/101/101/101/121/12101/62107/1532101.021032313033133011122233

3.18解：

（1）D=2霍夫曼编码

序号概率编码过程码字码长1234567890.160.140.130.120.100.090.080.070.06100.19100.15100.11100.271010.230110.31100.5801.000.4211110110001100100011011100010101003333334444100.05

n?0.74?3?0.26?4?3.26码元/符号

??LH(X)3.15??100%?96.6%

nlogD3.26?log2（1）D=3霍夫曼编码

序号概率编码过程码字码长1234567890.160.140.130.120.100.090.080.070.06210210210100.11011.0222212023100202301111102222222233100.05

n?0.89?2?0.11?3?2.11码元/符号

??LH(X)3.15??100%?94.1%

nlogD2.11?log33.22解：

133??1（1）H(X)???log?log??0.81bit/符号

444??4（2）q(0)?q(x0)?0.25，q(1)?q(x1)?0.75（3）二进制扩展信源的概率空间为

?xx?X2??00?1?2??P(X)???16x0x1316x1x0316x1x1?9??16?对其进行费诺编码i1234Pi9/163/163/161/16第一次分解其次次分解第三次分解0(9/16)1（7/16）0(3/16)1(4/16)0(3/16)1(1/16)代码组010110111n?416?3?316?2?916?1?1.6875码元/符号??LH(X)2nlogD??0.811.6875?100%?96%

(4)X的三次扩展信源的概率空间为

?X3?x0x0x0x0x0x1x0x1x0x0x1x1x1x0x0x1x0x1???P(X3)?????133939?646464646464对其进行二进制霍夫曼编码

序概码码号率编码过程字长111027/641.010129/64019/64110339/6410101349/64018/64100353/641111111563/6406/6411110573/641010/6411101581/6404/64111005n?2764?1?2764?3?1064?5?15864?2.469码元/符号

??LH(X)nlogD?3?0.812.469?100%?98.4%

x1x1x0x1x1x1?927?6464??

对其进行费诺编码i1234Pi9/163/163/161/16第一次分解其次次分解第三次分解0(9/16)1（7/16）0(3/16)1(4/16)0(3/16)1(1/16)代码组010110111n?416?3?316?2?916?1?1.6875码元/符号??LH(X)2nlogD??0.811.6875?100%?96%

(4)X的三次扩展信源的概率空间为

?X3?x0x0x0x0x0x1x0x1x0x0x1x1x1x0x0x1x0x1???P(X3)?????133939?646464646464对其进行二进制霍夫曼编码

序概码码号率编码过程字长111027/641.010129/64019/64110339/6410101349/64018