信息论与编码理论习题答案(4)

log11?nk?log?1 pkpk对不等号两边取概率平均可得

?pkklog11??pknk??pklog?1 pkpkkk即 H(U)?n?H(U)?1

?a1.....a2?3.8 扩展源DMC，U???0.6,0.4??

??(a)求对U的最佳二元码、平均码长和编码效率。 (b)求对U的最佳二元码、平均码长和编码效率。 (c)求对U的最佳二元码、平均码长和编码效率。 (d)求对U的最佳二元码、平均码长和编码效率。 解：(a) C1?0，C2=1，n=1

H(U)?0.97 bit H(U)?97% R(b) DMC信道

432??00011011a1a1a1a2a2a1a2a20.360.240.240.160.401010.6011

n2?2，n?1，?? (c)

H(U)?97% n0.4960.28801a1a1a10.504011010.2160.1920.160.204011100000110010111001101a1a1a2a1a2a1a2a1a1a1a2a20.1440.1440.1440.0960.0960.0960.064010110101a2a1a2a2a2a1a2a2a2

n3=2.944 n=0.981 ?=98.85% (d) 略

a2,....a3,......a4,....a5,...a6??a1,.....3.9 设离散无记忆信源 U???试求其二元和三元

0.3,..0.2,..0.15,..0.15,..0.1,..0.1??Huffman编码。

解：

0.60.40.3010.20101101a10.311 a20.2 000 a30.15001 100 a0.154a50.1101 a60.1

012110001022021a10.30.20.150.150.10.101aa0.201223aaa456

3.11 设信源有K个等概的字母,其中K=??2j,1???2。今用Huffman编码法进

行二元编码。

（a）是否存在有长度不为j或j+1的码字，为什么？ （b）利用?和j表示长为j+1的码字数目。 （c）码的平均长度是多少？

解：Huffman思想：将概率小的用长码，大的用短码，保证n↓，当等概时，趋

于等长码。

a) 对??1时，K=2j，则用长度为j码表示；当??2时，用K=2j+1，用长度为j+1码表示。平均码长最短，则当1???2时，则介于两者之间，即只存在j，j+1长的码字。

b) 设长为j的码字个数为Nj，长度为j+1的码字数目为Nj+1，根据二元

Huffman编码思想（必定占满整个码树），即

j?N?N?K???2j?1?j ?j?(j?1)?1??Nj?2?Nj?1?2从而Nj?(2??)?2j，Nj?1?(??1)?2j?1 c） L?

3.12 设二元信源的字母概率为p(0)? 1011 0111 1011 0111

(a) 对其进行算术编码并进行计算编码效率。 (b) 对其进行LZ编码并计算编码效率。 解：

12?3??1?(a) p(s)??????316

4?4??4?124112Nj?j?Nj?1?(j?1)=j?2? KK?13，p(1)?。若信源输出序列为 44????(i?)pu(iF)ui?1()?F(ui?1)?Fu?? 根据递推公式 ?可得如下表格

(i?)pui()??1?p(ui?1)?pu其中，F(1)=0， F(1)= 3， p(0)=1， p(1)=3 444ui ? 1 0 1 1 0 1 p(ui) 1 3 4313?? 4416339?? 164649327?? 64425633 5434 46F(ui) 0 1 41 4? ? ? ? 1 35 74? ? ? ? ? ? ? ? ? 1508125135 416?0.0101100111100100? 1 1 0 1 1 0 1 1 1 从而 C = 0101100111101 36 4837 4937 10438 11439 41239 413310 144311 154312 416134log4?logH(U)443?99.85% ???13R16 (b) 首先对信源序列进行分段：

1 0 11 01 111 011 0111

然后对其进行编码，编码字典如下所示

段号 短语 i j 编码 1 1 0 1 0001 2 0 0 0 0000 3 11 1 1 0011 4 01 2 1 0101