发布时间 : 星期三 文章信息论与纠错编码题库更新完毕开始阅读407f90a5c1c708a1284a4489
第三章 离散信源无失真编码
3.2
离散无记忆信源，熵为H[x]，对信源的L长序列进行等长编码，码字是长为n的D进制符号串，问：
（1）满足什么条件，可实现无失真编码。 （2）L增大，编码效率 也会增大吗？ 解：
（1）当nlogD?LH(X)时，可实现无失真编码；
（2）等长编码时，从总的趋势来说，增加L可提高编码效率，且当L??时，?但不一定L的每次增加都一定会使编码效率提高。
3.3
变长编码定理指明，对信源进行变长编码，总可以找到一种惟一可译码，使码长n满足
?1。
H(X)H(X)1H(X)1+,试问在n>+时，能否也找到惟一可译码？ ?n<
logDlogDLlogDL解：在n>
H(X)1+时，不能找到惟一可译码。
logDLH(X)1+时，能否也找到惟一可译码，则由变长编码定理当n满足
logDL证明：假设在n>
H(X)H(X)1H(X)+，总可以找到一种惟一可译码知：在n? ① ?n<
logDlogDLlogD时，总可以找到一种惟一可译码。
由①式有：
nH(X)logD ② ?LLH(x)H(X) 代入式②得：nL? LlogD对于离散无记忆信源，有H(x)=
即在
nL?
H(x)时，总可以找到一种惟一可译码；
logD
而由定理给定熵H（X）及有D个元素的码符号集，构成惟一可译码，其平均码长满足
H(X)H(X)+1 ?nL<
logDlogD两者矛盾，故假设不存在。 所以，在n>
H(X)1+时，不能找到惟一可译码。
logDL 3.7
对一信源提供6种不同的编码方案：码1~码6，如表3-10所示
表3-10 同一信源的6种不同编码 信源消息 消息概率 u1 u2 U3 u4 u5 u6 u7 1/4 1/4 1/8 1/8 1/8 1/16 1/16 码1 0 10 00 11 01 001 111 码2 001 010 011 100 101 110 111 码3 1 10 100 1000 10000 100000 1000000 码4 1 01 001 0001 00001 000001 0000001 码5 00 01 100 101 110 1110 1111 码6 000 001 011 100 101 1110 1111 （1） 这些码中哪些是惟一可译码？ （2） 这些码中哪些是即时码？
（3） 对所有唯一可译码求出其平均码长。 解：
码1： 其二次扩展码是奇异码，如u1u2和u5u1对应的码字均为010；
码2： 是惟一可译码，非奇异等长码是惟一可译码，且是即时码，平均码长为3； 码3： 是延长码，是惟一可译码，但不是即时码，平均码长为n=
=3.06 ?pinii?17码4： 是非延长码，故是惟一可译码，也是即时码；平均码长n=
=3.06 ?pinii?17码5： 是数码，即非延长码，因此是即时码；平均码长n=
=2.625 ?pinii?17码6：是非延长码，故是惟一可译码，也是即时码；平均码长n=
=3.125 ?pinii?17综上所述，码2~6均为惟一可译码，码2、4、5、6是即时码。 3.10
信源符号集X={0,1,2}，一信源含8个消息，编码为即时码，若要求码长只取1,3,5中的一个，应用克拉夫特不等式，分析按上述要求能否构成唯一可译码。
解：
根据克拉夫特不等式唯一可译码充要条件为码长取1，则
不等式左边=8*1/3>1 ，则唯一可译。 码长取3，则
不等式左边=8*(1/3)^3<1 , 则唯一可译。 码长为5，则
不等式左边=8*(1/3)^5<1 , 则唯一可译。
3.11
某个信源有N个消息，等概率分布，对其进行最佳二进制编码，问当N=为整数）时，每个码字的长度等于多少？平均码长等于多少？ 解：当N= 当N=
?D?nm?1
2m和N=
2m+1（m
2m，最佳二进制编码每个码字的长度均为m；平均码长n=m +1，令q(x1)?q(x2) ?q(x3) ?…?q(
2mx2m),最佳二进制编码前面?12m–1
个码字的长度为m，后2个码字的长度为m+1；平均码长n=
3.15
离散无记忆信源?m?2?m?2m2m
?1??x1x2x3? ?=??
?q(X)??0.50.30.2??X（1） 求X的最佳二元编码，平均码长及编码效率。 （2） 求（3） 求
XX(2)的最佳二元编码，平均码长及编码效率。 的最佳二元编码，平均码长及编码效率。
(3)解：（1）编码结果如下图所示：
10.5a1 0.5a2 0.31010编码01110
a3 0.2
平均码长n1=1?0.5+2?（0.3+0.2）=1.5（码元/符号） 信源熵H（X）=–
q(xm)logq(xm) ?m?13
= -0.5log0.5-0.3log0.3-0.2log0.2=0.5+0.521+0.464=1.49(比特/符号) 编码效率?=
1.49H(X)==0.99
n1logD1.5?log2?(2)?X?=?x1x1 x1x2 x2x1 x1x3 x3x1 x2x2 x2x3 x3x2 x3x3?
（2）???q((2))???0.250.150.150.100.100.090.060.060.04??X?编码结果如下图所示：
10.550.450.30.25a1 0.250.20.15a2 0.15a3 0.150.1a4 0.10a5 0.10a6 0.09a7 0.06a8 0.06a9 0.041010101010101010编码011101010010001111111010011000
平均码长n2=2?0.25+3?0.5+4?0.25=3（码元/符号） 信源熵H（
X(2)）=-
m?1?q(xm)logq(xm)
)9(2)(2)=0.5+0.821+0.664+0.313+0.487+0.186=2.31 (比特/符号) 编码效率?=
H(X(2)n2logD序号k 1 2 3 =
2.31=0.77
3?log2(3)（4） 编码如下图所示： X D=2霍夫曼编码 100 1101 1100 D=2编码码长 4 4 4 概率 0.125 0.075 0.075 x1x1x1 x1x1x2 x1x2x1