第4章离散信源的无错编码

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

信息论与编码理论

第4章 无失真信源编码

习题及其参考答案

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

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

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

?X??s1

4-2 设信源????p(s)P(X)???1s6?

p(s2)?p(s6)??

?

s2

?p(s)?1。对此次能源进行m元唯一

i

i?1

6

可译编码，其对应的码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值的最好下限。（提示：用kraft不等式）

?s ?X??1

4-3设信源为??1?

?p(X)???2?

（1）信源的符号熵； （2）这种码的编码效率；

s2

14s3s411816s5132s6s7s8?

，编成这样的码：（000，001，111???64128128?

010，011，100，101，110，111）。求

（3）相应的仙农码和费诺码。 4-4求概率分布为(,

11122

信)源的二元霍夫曼编码。讨论此码对于概率分布为3551515

11111

(,,,,)的信源也是最佳二元码。 55555

4-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?

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

分别使用长度为10和100的序列进行等长无失真编码，分别计算最短平均码长和编码效率。

解：信源的熵为

881.03.03.07.07.0)(HlblbX比特/符号

当N=10时，序列码长应当满足

81.81881.0102)(L1lbXNH比特/序列

考虑到序列码长应该为整数，取L1=9比特/符号，平均每个符号的码长为

9.0NLL11比特/符号

所以编码效率为

%9.97L)(H11X

当N=100时，序列码长为

1.881881.01002)(L1lbXNH比特/100符号

取L1=89比特/符号，平均每个符号的码长为

89.0NLL22比特/符号

编码效率为

%99L)(H22X

4.2设离散无记忆信源为

如果要求编码效率为，允许错误概率为，求编码序列的长度。

解：信源的熵为

722.02.02.08.08.0)(HlblbX比特/符号

自信息量方差为

64.0722.0-）2.0（2.0）8.0（8.0D222lblb 采用二进制码进行等长编码，序列长度应当满足

72221062.1)1)((DNXH

4.3设离散无记忆信源的概率空间为

要求编码效率为

(1) 如果采用序列等长编码，而允许译码错误概率为，求编码序列的长度。

(2) 如果采用序列变长编码，求编码序列的长度，并且与(1)比较，说明为什么会有这样的结果。

解1）信源的熵为

811.025.025.075.075.0)(HlblbX比特/符号

自信息量方差为

471.0811.0-）25.0（25.0）75.0（75.0D222lblb

采用二进制编码，序列长度为

62221029.1)1)((DNXH

2）对信源进行二次扩展，并采用下列编码方式构成唯一可译码

序列 序列概率

序列码字

序列码长

第二章部分习题

2.1 试问四进制、八进制脉冲所含信息量是二进制脉冲的多少倍?

答：2倍，3倍。

2.2 一副充分洗乱了的牌(含52张牌)，试问

(1) 任一特定排列所给出的信息量是多少？

(2) 若从中抽取13张牌，所给出的点数都不相同, 能得到多少信息量？解：(1) !52log2

(2) 任取13张，各点数不同的概率为1352!13C，信息量：9.4793(比特/符号)

2.3 居住某地区的女孩子有%25是大学生，在女大学生中有75%是身高160厘米上的，而女孩子中身高160厘米以上的占总数的一半。假如我们得知“身高160厘米以上的某女孩是大学生”的消息，问获得多少信息量？

答案：1.415比特/符号。提示：设事件A表示女大学生，事件C表示160CM以上的女孩，则问题就是求p(A|C)，

83214341)()|()()()()|(CpACpApCpACpCAp

2.4 设离散无忆信源123401233/81/41/41/8XaaaaPX，其发出的消息为(202120130213001203210110321010021032011223210)，求

(1) 此消息的自信息量是多少？

(2) 在此消息中平均每个符号携带的信息量是多少？

解：(1)87.81比特，

(2)1.951比特。

提示：先计算此消息出现的概率，再用自信息量除以此消息包含的符号总数(共45个)。

2.5 从大量统计资料知道，男性中红绿色盲的发病率为7% ，女性发病率为0.5%，如果你问一位男士：“你是否是色盲？”他的回答可能是“是”，可能是“否”，问这两个回答中各含有多少信息量?平均每个回答中含有多少信息量？如果问一位女士，则答案中含有的平均自信息量是多少？

(1) 男性回答是的信息量为2log0.073.8369比特，回答否的信息量是0.1047

比特，平均每个回答含的信息量(即熵)是0.36596比特。

《信 息 论》

讲 义

204教研室

2005年11月

1 主要内容：

第一章 绪论

第二章 离散信源及其信息测度

第三章 离散信道及其信道容量

第四章 无失真信源编码

第五章 有噪信道编码

2 第一章 绪论

信息论——人们在长期通信工程的实践中，由通信技术与概率论、随机过程和数理统计相结合而逐步发展起来的一门学科。

奠基人——香农

1948年发表了著名的论文——《通信的数学理论》，为信息论奠定了理论基础。

1.1 信息的概念

人类离不开信息，信息的接收、传递、处理和利用时时刻刻都在发生。

如：“结绳记事”、“烽火告警”，信息的重要性是不言而喻的。

什么是信息？——信息论中最基本、最重要的概念。

信息与“消息”、“情报”、“知识”、“情况”等的区别：

“情报”——人们对于某个特定对象所见、所闻、所理解而产生的知识。是一类特定的信息。

“知识”——人们根据某种目的，从自然界收集得来的数据中，整理、概括、提取得到的有价值的、人们所需的信息。是一种具有普遍和概括性质的高层次的信息。

“消息”——以文字、符号、数据、语言、音符、图片、图像等能够被人们感觉器官所感知的形式，表达客观物质运动和主观思维活动的状态。

消息包含信息，是信息的载体。二者既有区别又有联系。

“信号”——消息的运载工具。

香农从研究通信系统传输的实质出发，对信息作了科学的定义，并进行了定性和定量的描述。

收信者：

收到消息前，发送者发送的消息——1、描述的是何种事物运动状态的具体消息；2、描述的是这种消息还是那种消息；3、若存在干扰，所得消息是否正确与可靠。

存在“不知”、“不确定”或“疑问”

收到消息后，知道消息的具体内容，原先的“不知”、“不确定”或“疑问”消除或部分消除了。

消息传递过程——从不知到知的过程；从知之甚少到知之甚多的过程；从不确定到部分确定或全部确定的过程。

通信过程——消除不确定性的过程。

不确定性的消除，就获得了信息。