第5章_无失真信源编码 题与答案

A,B,C,D,E 和 F。

题表 5.1 消息 p(ai) 1/2 1/4 1/16 1/16 1/16 1/16 A 000 001 010 011 100 101 B 0 01 011 0111 01111 C 0 10 110 1110 11110 D 0 10 110 1110 1011 1101 E 0 10 1100 1101 1100 1111 F 0 100 101 110 111 011 a1 a2 a3 a4 a5 a6 011111 111110

(1) 求这些码中哪些是唯一可译码； (2) 求哪些是非延长码（即时码）； (3) 对所有唯一可译码求出其平均码长L。

解：

(1) 唯一可译码：A，B，C

A 是等长码，码长3，每个码字各不相同，因此是唯一可译码。 B 是非即时码，前缀码，是唯一可译码。 C 是即时码，是唯一可译码。

D 是变长码，码长{1, 2, 3, 4, 4, 4}，不是唯一可译码，因为不满足Kraft不等式。

rili111131.06251 22221234E 是变长码，码长{1, 2, 4, 4, 4, 4}，满足Kraft不等式，但是有相同的码字，W3W51100，不是唯一可译码。

rili111411 222124F 是变长码，码长{1, 3, 3, 3, 3, 3}，不满足Kraft不等式，不是唯一可译码。

rili1151.1251 2213

(2) 非延长码：A，C (3)

LA3LBLCpilii 1111111234561.312524161616165.7 设离散信源的概率空间为

s2s3s4s5s6Ss1P0.250.250.200.150.100.05

对其采用香农编码，并求出平均码长和编码效率。

解：

xi x1 x2 x3 x4 x5 x6 x7

p(xi) 0.2 0.19 0.18 0.17 0.15 0.1 0.01 pa(xi) 0 0.2 0.39 0.57 0.74 0.89 0.99 ki 3 3 3 3 3 4 7 码字 000 001 011 100 101 1110 1111110 Lpili0.2520.2520.230.1530.140.0552.7iH(S)pilogpi0.25log0.25...0.05log0.052.423 bit

i

H(S)2.42389.7%L2.75.8 设无记忆二元信源，其概率p10.005, p20.995。信源输出N100的二元序列。在长为N100的信源序列中只对含有3个或小于3个“1”的各信源序列构成一一对应的一组等长码。

(1) 求码字所需要的长度；

(2) 考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率pE是多少？

解： (1)

0码字中有0个“1”，码字的个数：C1001 1码字中有1个“1”，码字的个数：C100100 2码字中有2个“1”，码字的个数：C1004950

码字中有3个“1”，码字的个数：C100161700

0123qC100C100C100C100110049501617001667513rliqlilogrqlog16675117.35li18

(2)

码字中有0个“1”，错误概率：pa10.995100

码字中有1个“1”，错误概率：pa20.9950.005

99码字中有2个“1”，错误概率：pa30.9950.005

982码字中有3个“1”，错误概率：pa40.9950.005

9730123pGNpa1C100pa2C100pa3C100pa4C100100 0.99510.995990.0051000.99598 0.005249500.995970.0053161700 0.9983pE1pGN10.99830.0017

5.9 设有离散无记忆信源

s2s3s4s5s6s7s8Ss1P0.220.200.180.150.100.080.050.02 码符号集X{0, 1, 2}，现对该信源S进行三元哈夫曼编码，试求信源熵H(S)，码平均长度L和编码效率。

解：

满树叶子节点的个数：rkr132k3, 5, 7, 9, ...，q8，不能构成满树。

si wi li s1 1 1 s2 22 2

s7s90.07s100.25s12s1s4s11s30.53s2s5s8s6s3 21 2 s4 20 2

s5 02 2 s6 01 2 s7 000 3 s8 001 3

Lpili0.2210.220.1820.1520.120.0820.0530.0231.85

iH(S)pilogpi0.22log0.22...0.02log0.022.75 bitiH(S)2.7593.9%Llogr1.85log3

5.10 设有离散无记忆信源，其概率空间为

s2s3s4s5s6Ss1P0.320.220.180.160.080.04 进行费诺编码，并求其信源熵H(S)，码平均长度L和编码效率。

解：

xi x1 x2 x3 x4 x5 x6

p(xi) 0.32 0.22 0.18 0.16 0.08 0.04 1 0 Encode 0 1 0 1 0 1 0 1 wi 00 01 10 110 1110 1111 li 2 2 2 3 4 4 Lpili0.3220.2220.1820.1630.0840.0442.4iH(S)pilogpi0.32log0.32...0.04log0.042.352 biti



H(S)2.35298%L2.45.17 设有离散无记忆信源

s2s3s4s5s6s7Ss1P0.200.190.180.170.150.100.01 (1) 求该信源符号熵H(S)；

(2) 用霍夫曼编码编成二元变长码，计算其编码效率；

(3) 用霍夫曼编码编成三元变长码，计算其编码效率；

(3) 当译码错误小于103的定长二元码要达到(2)中霍夫曼码的效率时，估计要多少个信源符号一起编才能办到。

解： (1)

H(S)pilogpi0.2log0.2...0.01log0.012.609 bit

i(2)

si wi li

s8s6s1 10 2 s2 11 2

s120.61s13s110.39s90.260.11s5s7s3 010 3 s4 011 3

s100.35s1s2s3s4s5 001 3 s6 0000 4 s7 0001 4

Lpili0.220.1920.1830.1730.1530.140.0142.72iH(S)2.60995.9%L2.72

(3)

满树叶子节点的个数：rkr132k3, 5, 7, 9, ...，q7，能构成满树。

si wi li s1 1 1 s2 20 2

s80.26s10s1s7s6s5s3 21 2 s4 22 2

s5 00 2 s6 01 2 s7 02 2

s90.54s4s3s2

Lpili0.210.1920.1820.1720.1520.120.0121.8iH(S)2.60991.4%Llogr1.8log3

5.19 若某一信源有N个符号，并且每个符号均已等概率出现，对此信源用最佳霍夫曼二元编码，问当N2i和N2i1（i为正整数）时，每个码字的长度等于多少？平均码长是多少？

解：

(1) when N2i11pii22logpililogpi11lilogi2Lpiliiiii(2) when N2i1pi12i111pi2i2i1logpililogpi11lilog2ii1i1Lpilii12i2i1i