信息论与编码理论-第4章无失真信源编码-习题解答-20071202

信息论与编码理论

第4章 无失真信源编码

习题及其参考答案

4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F

（1）求这些码中哪些是唯一可译码；

（2）求哪些码是及时码；

（3）对所有唯一可译码求出其平均码长l。

消息

S1

S2

S3

S4

S5

S6

概率

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

011111

C

0

10

110

1110

11110

111110

D

0

10

110

1110

1011

1101

E

0

10

1100

1101

1110

1111

F

0

100

101

110

111

011

Xs14-2 设信源p(s)P(X)1s2p(s2)s6p(s6)p(s)1。对此次能源进行m元唯一ii16可译编码，其对应的码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值的最好下限。（提示：用kraft不等式）

sX14-3设信源为1p(X)2（1）信源的符号熵；

（2）这种码的编码效率；

s214s318s4116s5132s8，编成这样的码：（000，001，11164128128s6s7010，011，100，101，110，111）。求

（3）相应的仙农码和费诺码。

4-4求概率分布为(,,,11122,)信源的二元霍夫曼编码。讨论此码对于概率分布为355151511111(,,,,)的信源也是最佳二元码。

555554-5有两个信源X和Y如下：

1

信息论与编码理论

s2s3s4s5s6s7Xs1p(X)0.200.190.180.170.150.100.01

s2s3s4s5s6s7s8s9Ys1p(Y)0.490.140.140.070.070.040.020.020.01

（1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X和Y进行编码，并计算其平均码长和编码效率；

（2）从X，Y两种不同信源来比较三种编码方法的优缺点。

4-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这样

霍夫曼码的信源的所有概率分布。

4-7设信源为码。

4-8若某一信源有N个符号，并且每个符号等概率出现，对这个信源进行二元霍夫曼编码，问当N=2i和N=2i+1（i是正整数）时，每个码值的长度是多少？平均码长是多少？

4-9现有一幅已离散量化后的图像，图像的灰度量化分成8级，如下表所示。表中数字为相应像素上的灰度级。

1

1

1

1

2

2

3

4

5

7

（1）不考虑图像的任何统计特性，对图像进行二元等长编码，这幅图像共需要多少个二元符号描述？

（2）若考虑图像的统计特性，求这幅图像的信源熵，并对每个灰度级进行二元霍夫曼编码，问平均每个像素需用多少二元符号表示。

4-10在MPEG中为了提高数据压缩比，采用了____方法。

A．运动补偿与运行估计 B.减少时域冗余与空间冗余

C．帧内图像数据与帧间图像数据压缩 D.向前预测与向后预测

2

s5s6s7s8Xs1s2s3s40.40.20.10.10.050.050.050.05，求其三元霍夫曼编p(X)1

1

1

1

2

2

3

4

5

7

1

1

1

1

2

2

3

4

5

7

1

1

1

1

2

2

3

4

5

7

1

1

1

1

2

2

3

4

6

7

1

1

1

1

2

2

3

4

6

8

1

1

1

1

2

2

3

4

6

8

1

1

1

1

2

3

4

5

6

8

1

1

1

1

2

3

4

5

6

8

1

1

1

1

2

3

4

5

6

8

信息论与编码理论

4-11 JPEG中使用了____熵编码方法。

A.统计编码和算术编码 编码和DPCM编码

C.预测编码和变换编码 D.哈夫曼编码和自适应二进制算术编码

4-12 简述常用信息编码方法的两类。

4-13 简述等长编码和变长编码的特点，并举例说明。

4-14已知信源X＝[x1=0.25,x2=0.25,x3=0.2,x4=0.15,x5=0.10,x6=0.05]，试对其进行Huffman编码。

4-15已知信源X＝[x1＝1/4，x2＝3/4]，若x1＝1,x2＝０，试对1011进行算术编码。

4-16离散无记忆信源发出A，B，C三种符号，其概率分布为5/9，1/3，1/9，应用算术编码方法对序列CABA进行编码，并对结果进行解码。

4-17给定一个零记忆信源，已知其信源符号集为A=｛a1，a2｝＝｛0，1｝，符号产生概率为P(a1)＝1/4，P(a2)＝3/4。对二进制序列11111100，求其二进制算术编码码字。

4-18有四个符号a，b，c，d构成的简单序列S＝abdac，各符号及其对应概率如表所示。应用算术编码方法对S进行编码，并对结果进行解码。

符号

a

b

c

d

4-19简述游程编码的思想和方法。

4-20简述JEPG算法的主要计算步骤，并详细说明每个步骤。

4-21设二元信源的字母概率为P(0)=1/4,P(1)=3/4。若信源输出序列为1111

（a） 对其进行算术编码并计算编码效率。

（b） 对其进行LZ编码并计算编码效率。

4-22设有二元信源符号集，输入信源符号序列为a1a0a1a0a0a0a1a1a0a1a1a0符号概率pi

1/2

1/4

1/8

1/8

,求其序列的字典编码。

4-23一个离散记忆信源A={a,b,c},发出的字符串为bccacbcccccccccccaccca。试用LZ算法对序列编码，给出编码字典及发送码序列。

4-24 用LZ算法对信源A={a,b,c}编码，其发送码字序列为：2，3，3，1，3，4，5，10，11，6，10。试据此构建译码字典并译出发送序列。

习题参考答案

3

信息论与编码理论

4-1：

(1) A、B、C、E编码是唯一可译码。

(2) A、C、E码是及时码。

(3) 唯一可译码的平均码长如下：

111111lAp(si)li3()3 码元/信源符号

2416161616i1111111lBp(si)li1234562.125码元/信源符号

2416161616i1111111lCp(si)li1234562.125码元/信源符号

2416161616i1111111lEp(si)li12()42码元/信源符号

2416161616i14-3：

(1)

6666H(X)=-p(xi)logp(xi)i=1=-log-log-log-log-log22448816163232

111111 -log-log-log6464863=1bit/符64(2) 平均码长：

11111111lp(si)li3()3码元/信源符号

2488i1所以编码效率：(3) 仙农编码：

信源符号Si

S1

S2

S3

S4

4

6H(X)0.6615

l符号概率p(Si)

加概率

0

码长

1

2

3

4

码字

0

10

110

1110

1

21

41

81

161

23

47

8

信息论与编码理论

S5

S6

S7

S8

费诺码：

信源符号Si

S1

S2

S3

S4

S5

S6

S7

S8

4-5：

(1) 霍夫曼编码：

对X的霍夫曼编码如下：

信源符号符号概率1

321

641

1281

128符号概率p(Si)

15

1631

3263

64127

128编码

0

0

0

0

1

1

1

1

1

0

5

6

7

7

11110

111110

1111110

1111111

码字

0

10

0

1

1 1111111

110

1110

11110

111110

1111110

码长

1

2

3

4

5

6

7

7

1

21

41

81

161

321

641

1281

128

0

编码过程 码长

Si

S1

S2

S3

S4

S5

S6

S7

p(Si)

0.2

0.19

0.18

0.17

0.15

0.10

0.01

0

1

0.2

0.19

0.18

0.17

0.15

0.11

0

1

0.26

0.2

0.19

0.18

0.17

0

1

0.35

0.26

0.2

0.19

0

1

0.39

0.35

0.26

0

1

0.61

0.39

0

1

10

11

000

001

010

0110

0111

码字

2

2

3

3

3

4

4

l0.220.1920.1830.1730.1530.140.0142.72码元/信源符号

5

信息论与编码理论

7H(X)pilogpi2.61 码元/符号

i1

H(X)2.610.9596

2.72lY的二元霍夫曼编码：

信源符号符号概率编码过程 码字

p(Si)

0.49

0.14

0.14

0.07

0.07

0.04

0.02

0.02

0.01 1

0.49

0.14

0.14

0.07

0.07

0.04

0 0.02 1

0.49

0.14

0.14

0.07

0.07

0.49

0.14

0.14

0.09

0.49

0.14

0.14

0.49

0.23

0.49 0.51 0 1

000

001

0100

0101

0111

01101

011000

011001

码长

Si

S1

S2

S3

S4

S5

S6

S7

S8

S9

1

3

3

4

4

4

5

6

6

0.28 0 0.49 1

0.14 0 0.23 1

0.14 0 0.14 1

0.07 0 0.09 1

0.05 0 0.07 1

0.03 0 0.04 1

平均码长：

l0.4910.14320.07420.0440.0250.0260.0162.23码元/信源符

H(Y)pilogpi2.31码元/符号

i19编码效率：H(Y)2.310.9914

2.33l(2) 仙农编码：

对X的仙农编码：

信源符号Si

S1

S2

S3

S4

S5

S6

S7

6

符号概率p(Si)

0.2

0.19

018

0.17

0.15

0.10

0.01

和概率

0

0.2

0.39

0.57

0.74

0.89

0.99

码长

3

3

3

3

3

4

7

码字

000

001

011

100

101

1110

1111110

信息论与编码理论

平均码长：

l0.230.1930.1830.1730.1530.140.0173.14

码元/信源符

H(X)2.610.8312

3.14l对Y的仙农编码：

信源符号Si

S1

S2

S3

S4

S5

S6

S7

S8

S9

平均编码长度：

符号概率p(Si)

0.49

0.14

0.14

0.07

0.07

0.04

0.02

0.02

0.01

和概率

0

0.49

0.63

0.77

0.84

0.91

0.95

0.97

0.99

码长

2

3

3

4

4

5

6

6

7

码字

00

011

101

1100

1101

11101

111100

111110

1111110

l0.4920.1420.07420.0450.02620.0260.0172.89码元/信源符

编码效率：H(Y)2.310.7993

2.89l(3) 费诺编码：

对X的费诺编码：

信源符号Si

S1

S2

S3

S4

S5

S6

S7

平均编码长度：

符号概率p(Si)

0.2

0.19

0.18

0.17

0.15

0.10

0.01

1

0

编码

0

1

0

1

0

1

0

1

0

1

码字

00

010

011

10

110

1110

1111

码长

2

3

3

2

3

4

4

l0.220.1930.1830.1720.1530.140.0142.74

码元/信源符号

编码效率：H(X)2.610.9526

2.74l对Y进行费诺编码：

7

信息论与编码理论

信源符号Si

S1

S2

S3

S4

S5

S6

S7

S8

S9

平均码长：

符号概率p(Si)

0.49

0.14

0.14

0.07

0.07

0.04

0.02

0.02

0.01

1

1

0

0

编码

0

1

0

0

1

0

1

0

1

1

0

1

码字

0

100

101

1100

1101

1110

11110

111110

111111

码长

1

3

3

4

4

4

5

6

6

l0.4910.14230.07420.0440.0250.0260.0162.33码元/信源符号

编码效率：H(Y)2.310.9914

2.33l(4) 由三种编码的编码效率可知：

仙农编码的编码效率为最低，平均码长最长；霍夫曼编码的编码长度最短，编码效率最高，费诺码居中。

4-7： 由三元编码方式可知：R=D－B=RD-1(K－2)+2

由本题可知D=3，K=8，R=2，所以，首先合并最后两个信源概率，其中一种编码方式如下：

信源符号Si

S1

S2

S3

S4

S5

S6

S7

S8

4-16：

符号

C

A

B

A

8

符号概率p(Si)

0.4

0.2

0.1

0.1

0.05

0.05

0.05

0.05

0

1

0.4

0.2

0.1

0.1

0.1

0.05

0.05

0

1

2

编码

0.4

0.2

0.2

0.1

0.1

0

1

2

0.4

0.4

0.2

0

1

2

码字

0

2

11

12

101

102

1000

1001

码长

1

1

2

2

3

3

4

4

ui

C

CA

CAB

CABA

P(ui) F(ui) 码长

4

5

6

9

二进制表示

0.1110

0.11100

0.111011

0.111011000

1

95

815

2435

21878

98

9673

729673

729

信息论与编码理论

符号分布概率：

符号

A

概率 分布区间

5

91

31

950,9

B

58,

998,1

9C

译码：

67380.9292,17299第一字符是:C673872990.36280,58919第二字符是:AF(u4)0.36280580.6530,59919第二字符是:B50.653090.36280,585999

第二字符是:A所以译码结果是：CABA

4-21：

(1)

符号

0

1

由题目可知信源符号为：

1011 0111 1011 0111

概率

0.25

0.75

分布区间

0,0.25

0.25,1

p(s1011 0111 1011 0111)

31214p(1)p(0)()()0.9

信息论与编码理论

算术码的码长llogp(s)13

由序列S的分布函数F（S）由二元整树图来计算：

F(S)1p(11)p(10111)p(1011011111)p(1)p(1111)331313131

1()2()4()()8()2()10()3()12()44444444440.35114030.1所以算术编码为：0100 0011 0011

平均码长及编码效率如下：

l130.8125码元/符号

16H(S)p(1)logp(1)p(0)logp(0)0.8113 bit/符号

(2)

由于信源符号集中共有2个元素，因此只需要log21位二进制数就可以表示其编码，该符号集的编码表如下：

符号

编码

按照分段规则，分段为：1 0 11 01 111 011 0111

短语数为7，可用nlog73位来表示段号；

每个信源符号编码长度为1，所以短语长度为：3+1=4，具体编码过程如下：

段号

1

2

3

4

5

6

7

平均编码长度：l短语

1

0

11

01

111

011

0111

编码

0001

0000

0011

0101

0111

1001

1101

0

0

1

1

H(S)0.9985

l7(31)1.75码元/符号

16H(S)0.81130.4636 编码效率为：1.75l10