信息论与编码理论第4章无失真信源编码习题解答1202.docx
《信息论与编码理论第4章无失真信源编码习题解答1202.docx》由会员分享，可在线阅读，更多相关《信息论与编码理论第4章无失真信源编码习题解答1202.docx（19页珍藏版）》请在冰点文库上搜索。
信息论与编码理论第4章无失真信源编码习题解答1202
第4章无失真信源编码
习题及其参考答案
4-1有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、
D、E和F
（1）求这些码中哪些是唯一可译码；
（2）求哪些码是及时码；
（3）对所有唯一可译码求出其平均码长「。
消息
概率
A
B
C
D
E
F
S1
1/2
000
0
0
0
0
0
S2
1/4
001
01
10
10
10
100
S3
1/16
010
011
110
110
1100
101
S4
1/16
011
0111
1110
1110
1101
110
S5
1/16
100
01111
11110
1011
1110
111
S6
1/16
101
011111
111110
1101
1111
011
~Y1~ssIII6
4-2设信源|Zp（s）=1。
对此次能源进行m元唯一
]p（x）」[p（s）P6）川P6L7
可译编码，其对应的码长为（li,l2,-6）=（1,1,2,323），求m值的最好下限。
（提示：
用kraft不等式）
010,011,100,101,110,111）。
求
（1）信源的符号熵；
（2）这种码的编码效率；
（3）相应的仙农码和费诺码。
11122
4-4求概率分布为（丄」」——信源的二元霍夫曼编码。
讨论此码对于概率分布为
3‘5‘5‘15’15
的信源也是最佳二元码。
55555
4-5有两个信源X和Y如下：
S5S6S7
0.150.100.01
X_S1S2S3S4
p（X）1（0.200.190.180.17
；Y1
S2
S3
S4
S5
S6
S7
S8
S91
]p（Y）一
〔0.49
0.14
0.14
0.07
0.07
0.04
0.02
0.02
0.01一
（1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X和Y进行编码，并计算其平均码长和编码效率；
（2）从X，Y两种不同信源来比较三种编码方法的优缺点。
4-6设二元霍夫曼码为（
00,01,10,11）和（0,10,110,111）,求出可以编得这样
霍夫曼码的信源的所有概率分布。
4-7设信源为［X〕
siS2S3s4s5S6S72
=
，求其三元霍夫曼编
]p（X）_
]0.40.20.10.10.050.050.050.0
5
码。
4-8若某一信源有N个符号，并且每个符号等概率出现，对这个信源进行二元霍夫曼编码，问当
N=2i和N=2，+1（i是正整数）时，每个码值的长度是多少？
平均码长是多少？
4-9现有一幅已离散量化后的图像，图像的灰度量化分成8级，如下表所示。
表中数字为相应像素
上的灰度级。
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
6
6
6
6
6
6
7
7
7
7
7
8
8
8
8
8
（1）不考虑图像的任何统计特性，对图像进行二元等长编码，这幅图像共需要多少个二元符号描述？
（2）若考虑图像的统计特性，求这幅图像的信源熵，并对每个灰度级进行二元霍夫曼编码，问平均每个像素需用多少二元符号表示。
4-10在MPEG中为了提高数据压缩比，采用了
方法。
A•运动补偿和运行估计
B.减少时域冗余和空间冗余
D.向前预测和向后预测
B.PCM编码和DPCM编码
D.哈夫曼编码和自适应二进制算术编码
C.帧内图像数据和帧间图像数据压缩
4-11JPEG中使用了熵编码方法。
A.统计编码和算术编码
C.预测编码和变换编码
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=0,试对1011进行算术编码。
4-16离散无记忆信源发出A,B,C三种符号，其概率分布为5/9,1/3,1/9，使用算术编码方法对序
列CABA进行编码，并对结果进行解码。
4-17给定一个零记忆信源，已知其信源符号集为A={a1,a2}={0,1},符号产生概率为P（a“=1/4,
P（a2）=3/4。
对二进制序列11111100,求其二进制算术编码码字。
4-18有四个符号a,b,c,d构成的简单序列S=abdac,各符号及其对应概率如表所示。
使用算术编码方法对S进行编码，并对结果进行解码。
符号
符号概率p
a
1/2
b
1/4
c
1/8
d
1/8
4-19简述游程编码的思想和方法。
4-20简述JEPG算法的主要计算步骤，并详细说明每个步骤。
4-21设二元信源的字母概率为P（0）=1/4,P
（1）=3/4。
若信源输出序列为10111
（a）对其进行算术编码并计算编码效率。
（b）对其进行LZ编码并计算编码效率。
4-22设有二元信源符号集，输入信源符号序列为印80印80808081印80印印8011（,求其序列的字典编码。
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。
试据此构建译码字典并译出发送序列。
习题参考答案
4-1:
（1）A、B、C、E编码是唯一可译码。
（2）A、C、E码是及时码。
（3）
唯一可译码的平均码长如下：
=3（1•丄丄丄丄丄
2416161616
111111
lBp（si）li123456=2.125码兀/信源符号
y2416161616
111111
lc=7p（s）h123456=2.125码元/信源符号
i42416161616
_6
l；八p（s）li
i4
111111一
12亠（）4=2码兀/信源符号
2416161616
4-3:
8
H（X）=-\p（xjlogp（xi）
i=1
111=-—log—-—
224
11log-log
48
11
-log
816
111
—-—log—163232
11
1
1
1
1
-log—-
log
-log
6464
128
128
128
128
彳63
=1bit/符
64
（1）平均码长:
所以编码效率：
=0.6615
_6
i「p（s）li
i4
11111111一
=3（---—一-一-——-——）=3码元/信源符号
信源符号Si符号概率p（Si）
248163264128128
信源符号Si
符号概率p（Si）
加概率
码长
码字
1
S1
一
0
1
0
2
1
1
S2
4
2
2
10
1
3
S3
—
——
3
110
8
4
1
7
S4
16
—
4
1110
8
1
15
S5
5
11110
32
16
1
31
S6
64
32
6
111110
1
63
S7
128
64
7
1
127
S8
128
128
7
（2）仙农编码:
费诺码:
码长
编码
码字
S1
1
2
0
0
1
S2
1
4
0
10
2
S3
1
8
0
110
3
S4
1
16
0
1110
4
S5
1
32
1
1
0
11110
5
S6
1
64
1
1
0
111110
6
S7
1
128
1
1
0
7
S8
1
128
1
7
4-5:
（1）霍夫曼编码:
对X的霍夫曼编码如下:
信源
符号
Si
符号概率
P（S）
编码过程
码长
码字
S1
0.2
0.2
0.26
r
0.35
0.39
0.61
■
0
10
2
S2
0.19
0.19
r
0.2
0.26
『0.35
0/
广0.39
1
11
2
S3
0.18
0.18
0.19
L
0.2
0.26
1
000
3
S4
0.17
0.17
0.18
:
0
0.19
1
001
3
S5
0.15
0.15
0
0.17
1
010
3
S6
0.10
0.11
1
0110
4
S7
0.01
1
0111
4
l=0.220.1920.1830.1730.1530.140.014=2.72码元/信源符号
7
H（X）=為pilog口=2.61码元/符号
i=1
二WK型79596
l2.72
Y的二元霍夫曼编码:
信源符号
Si
符号概率
P（Si）
编码过程
码字
码长
S1
0.49
0.49
0.49
0.49
0.49
0.49
0.49
f0.51
0
1
1
S2
0.14
0.14
0.14
0.14
0.14
\0.23
/
0.28
0.49
1
000
3
S3
0.14
0.14
0.14
0.14
0.14
0.14.
/0
0.23
1
001
3
S4
0.07
0.07
0.07
*
-0.09
2
0.14
0
0.14
1
0100
4
S5
0.07
0.07
0.07
10.07」
0.09
1
0101
4
S6
0.04
0.04
0.05
/
0
0.07
1
0111
4
S7
0.02
<0.03
0.04
1
01101
5
S8
0.02
/
0.02
1
011000
6
S9
0.01
1
011001
6
平均码长：
l=0.4910.14320.07420.0440.0250.0260.016=2.23码元/信源符
9
H（Y）='plog口=2.31码元/符号
i4
编码效率：
i.=里卫二23!
=0.9914
l2.33
⑵仙农编码：
对X的仙农编码:
信源符号S
符号概率p（S）
和概率
码长
码字
S1
0.2
0
3
000
S2
0.19
0.2
3
001
S3
018
0.39
3
011
S4
0.17
0.57
3
100
S5
0.15
0.74
3
101
S6
0.10
0.89
4
1110
S7
0.01
0.99
7
平均码长:
l=0.230.1930.1830.1730.1530.140.017=3.14
码元/信源符
对Y的仙农编码:
信源符号S
符号概率p（S）
和概率
码长
码字
S1
0.49
0
2
00
S2
0.14
0.49
3
011
S3
0.14
0.63
3
101
S4
0.07
0.77
4
1100
S5
0.07
0.84
4
1101
S6
0.04
0.91
5
11101
S7
0.02
0.95
6
111100
S8
0.02
0.97
6
111110
S9
0.01
0.99
7
平均编码长度:
1=0.4920.1420.07420.0450.02620.0260.017=2.89码元/信源符
H（Y）2.31
编码效率：
口=—==07993
l2.89
⑶费诺编码：
对X的费诺编码:
信源符号S
符号概率p（Si）
编码
码字
码长
S1
0.2
0
0
00
2
S2
0.19
1
0
010
3
S3
0.18
1
011
3
S4
0.17
1
0
10
2
S5
0.15
1
0
110
3
S6
0.10
1
0
1110
4
S7
0.01
1
1111
4
平均编码长度:
l=0.220.1930.1830.1720.1530.140.014=2.74
码元/信源符号
H（X）2.61
编码效率：
0.9526
l2.74
对Y进行费诺编码:
信源符号s
符号概率p（S）
编码
码字
码长
S1
0.49
0
0
1
S2
0.14
0
0
100
3
S3
0.14
1
101
3
S4
0.07
0
0
1100
4
S5
0.07
1
1
1101
4
S6
0.04
1
0
1110
4
S7
0.02
1
0
11110
5
S8
0.02
1
1
0
111110
6
S9
0.01
1
111111
6
平均码长:
1=0.4910.14230.07420.0440.0250.0260.016=2.33码元/信源符
编码效率：
二H（Y^=竺二0.9914
I2.33
（4）由三种编码的编码效率可知：
仙农编码的编码效率为最低，平均码长最长；霍夫曼编码的编码长度最短，编码效率最高，费诺码居中。
4-7:
由三元编码方式可知：
R=D—B=Rd-i（K—2）+2
由本题可知D=3,K=8,R=2，所以，首先合并最后两个信源概率，其中一种编码方式如下:
信源符号S
符号概率p（S）
编码
码字
码长
Si
0.4
0.4
1
0.4
0.4
0
0
1
S2
0.2
0.2
0.2
卩°4
1
2
1
S3
0.1
0.1
0.2
0.2
2
11
2
S4
0.1
0.1
0.1
彳
12
2
S5
0.05
40.1
/
0.1
2
101
3
S6
0.05
0.05
1
102
3
S7
0.05
0.05
2
1000
4
S8
0.05
1
1001
4
4-16:
符号
iu
P（J）
F（ui）
码长
—进制表示
C
C
1
9
8
9
4
0.1110
A
CA
5
81
8
9
5
0.11100
B
CAB
5
243
673
729
6
0.111011
A
CABA
5
673
9
0.111011000
2187
729
符号分布概率:
符号
概率
分布区间
5
-5、
A
9
氏丿
B
1
3
〔9,9丿
C
1
9
刖
19丿
译码:
F（U4）嘅"9292J'1
.第一字符是:
C
6738
7299=0.36280,5
18_9
9
.第二字符是:
A
0.3628-0「58}
5109丿
9
.第二字符是:
B
5
=0.36280,5
19丿
0.6530-
9
8_5
9一9
4-21:
.第二字符是:
A
所以译码结果是：
CABA
符号
概率
分布区间
0
0.25
〔0,0.25）
1
0.75
【0.25,1）
由题目可知信源符号为:
1011011110110111
p（S=1011011110110111）
12431214
-p
（1）12p（0）=（）12（）-0.0001237
44
算术码的码长丨--logp（s）=13
由序列S的分布函数F（S）由二元整树图来计算：
F（S）=1—p（11）—p（10111）-p（1011011111）-p（1011011110111）-p（1011011110110111）
323厶138〔23101331214
^-（-）2-（3）4（;）-
（二）8（;）2-（3）（匚）3-（3）（;）4
444444444
.010*********
所以算术编码为：
010000110011
平均码长及编码效率如下：
-13一
l0.8125码兀/符号
16
H（S）—p
（1）logp
（1）-p（0）logp（0）=0.8113bit/符号
H（S）=0.9985
l
由于信源符号集中共有2个兀素，因此只需要|log2=1位二进制数就可以表示其编码，该符号集
的编码表如下：
符号
0
1
编码
0
1
按照分段规则，分段为：
1011011110110111
短语数为7,可用n=log7=3位来表示段号；
每个信源符号编码长度为1，所以短语长度为：
3+1=4，具体编码过程如下:
啟1=1.段号
短语
编码
1
1
0001
2
0
0000
3
11
0011
4
01
0101
5
111
0111
6
011
1001
7
0111
1101
平均编码长度：
i二7（31=1.75码元/符号
16
1.75
编码效率为：
=二0.8113二0.4636
升级会员 