第五章 信源编码

1 第二章习题：

补充题：掷色子，（1）若各面出现概率相同

（2）若各面出现概率与点数成正比

试求该信源的数学模型

解： （1）根据61()1iipa，且16()()papa，得

161()()6papa，所以信源概率空间为

123456111111666666P

（2）根据61()1iipa，且126(),()2,()6pakpakpak，得121k。

123456123456212121212121P

2-2 由符号集0,1组成的二阶马尔可夫链，其转移概率为P(0/00)=0.8，P(0/11)=0.2，P(1/00)=0.2，

P(1/11)=0.8，P(0/01)=0.5，P(0/10)=0.5，P(1/01)=0.5，P(1/10)=0.5。画出状态图，并计算各状态的稳态概率。

解：由二阶马氏链的符号转移概率可得二阶马氏链的状态转移概率为：

P(00/00)=0.8 P(10/11)=0.2 P(01/00)=0.2

P(11/11)=0.8 P(10/01)=0.5 P(00/10)=0.5

P(11/01)=0.5 P(01/10)=0.5

二进制二阶马氏链的状态集S={,1S432,,SSS}={00，01，10，11}

0.80.20.50.50.50.50.20.8P

状态转移图

各状态稳定概率计算：41411ijijijjWPWW即

143214443432421414434333232131342432322212124143132121111WWWWPWPWPWPWWPWPWPWPWWPWPWPWPWwPWPWPWPWW 00010.20.810110.50.20.80.50.50.5S1S2S3S4 2 得：14541WW 14232WW

5.1某离散无记忆信源的概率空间为

采用香农码和费诺码对该信源进行二进制变长编码，写出编码输出码字，并且求出平均码长和编码效率。

解：计算相应的自信息量

1)()(11albpaI比特 2)()(22albpaI比特

3)()(313albpaI比特 4)()(44albpaI比特

5)()(55albpaI比特 6)()(66albpaI比特

7)()(77albpaI比特 7)()(77albpaI比特

根据香农码编码方法确定码长

1)()(iiiaIlaI

可以得到对应码长如表所示

符号 概率 累计概率 自信息量 码长 码字

a1 1/2 0 1 1 0

a2 1/4 1/2 2 2 10

a3 1/8 3/4 3 3 110

a4 1/16 7/8 4 4 1110

a5 1/32 15/16 5 5 11110

a6 1/64 31/32 6 6 111110

a7 1/128 63/64 7 7 1111110

a8 1/128 127/128 7 7 1111111

平均码长

984375.164/6317128/17128/1664/1532/1416/138/124/112/1L1由于每个符号的码长等于自信息量，所以编码效率为1。

费罗马编码过程

符号 码字 码长

a1 1/2 0 0 1

a2 1/4 1 0 10 2

a3 1/8 1 0 110 3

a4 1/16 1 0 110 4

a5 1/32 1 0 1110 5

a6 1/64 1 0 11110 6

a7 1/128 1 0 111110 7

a8 1/128 1 111111 7

5.2某离散无记忆信源的概率空间为

使用费罗码对该信源的扩展信源进行二进制变长编码，

(1) 扩展信源长度，写出编码码字，计算平均码长和编码效率。

. .

1 / 13 5-1 有一信源，它有六种可能的输出，其概率分布如下表所示，表中给出了对应的六种编码12345CCCCC、、、、和6C。

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

（2） 求哪些是非延长码（即时码）；

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

消息 概率

1C 2C 3C 4C 5C 6C

1a 1/2 000 0 0 0 1 01

2a 1/4 001 01 10 10 000 001

3a 1/16 010 011 110 1101 001 100

4a 1/16 011 0111 1110 1100 010 101

5a 1/16 100 01111 11110 1001 110 110

6a 1/16 101 011111 111110 1111 110 111

解：（1）1,2,3,6是唯一可译码；

(2)1,3,6是即时码。

5-2证明若存在一个码长为12,,,qlll的唯一可译码，则一定存在具有相同码长的即时码。

证明：由定理可知若存在一个码长为LqLL,,2,1的唯一可译码，则必定满足kraft不等式qilir11。由定理44可知若码长满足kraft不等式，则一定存在这样码长的即时码。所以若存在码长LqLL,,2,1的唯一可译码，则一定存在具有相同码长P（y=0）的即时码。

5-3设信源126126()sssSpppPs，611iip。将此信源编码成为r元唯一可译变长码（即码符号集12{,,,}rXxxx），其对应的码长为（126,,,lll）=（1，1，2，3，2，3），求r值的最小下限。

解：要将此信源编码成为 r元唯一可译变长码，其码字对应的码长

（l1 ,l2 ,l3, l4,l5, l6）=(1,1,2,3,2,3) 必须满足克拉夫特不等式，即

第五章课后习题

【5.1】某信源按

43

)0(=P，

41

)1(=P的概率产生统计独立的二元序列。

（1）试求

0N，使当

0NN>时有

01.005.0)()(

≤





≥−SH

NI

Piα

式中，)(SH是信源的熵。

（2）试求当

0NN=时典型序列集

NG

ε中含有的信源序列个数。

解：

（1）该信源的信源熵为

811.0)(log)()(=−=∑

iispspSH比特/符号

自信息的方差为

4715.0811.04log

41

34

log

43)()]([)]([

22222

=−+=−=SHsIEsID

ii

根据等长码编码定理，我们知道

δεα

−≤





≥−1)()(

SH

NI

Pi

根据给定条件可知，05.0=ε，99.0=δ

。而

[]

2)(

εδ

NsID

i

=

因此

[]

5.190

99.0*05.04715.0)(

220==≥

δεisID

N

取191

0=N。 （2）ε典型序列中信源序列个数取值范围为：

])([])([

22)1(ε

εε

δ+−

<<−SHN

NSHN

G

代入上述数值得

451.164351.145

2201.0<<×

NG

ε

【5.2】有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了

对应的码A、B、C、D、E和F。

表5.2

消息 )(

iaP

A B C D E F

1a

1/2 000 0 0 0 0 0

2a

1/4 001 01 10 10 10 100

3a

1/16 010 011 110 110 1100 101

4a

1/16

011 0111 1110 1110 1101 110

5a

1/16

100 01111 11110 1011 1110 111

6a

1/16

101 011111 111110 1101 1111 011

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

（2） 求哪些码是非延长码（即时码）；

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

解：

（1）上述码字中，A为等长码，且为非奇异码，因此码A为惟一可译码；