信息论与编码第四章课后答案

信息论与编码课后习题答案

第二章

2.3 同时掷出两个正常的骰子，也就是各面呈现的概率都为1/6，求：

(1) “3和5同时出现”这事件的自信息； (2) “两个1同时出现”这事件的自信息；

(3) 两个点数的各种组合（无序）对的熵和平均信息量； (4) 两个点数之和（即2, 3, … , 12构成的子集）的熵； (5) 两个点数中至少有一个是1的自信息量。 解：

(1)

11111p(xi)?????6666181I(xi)??logp(xi)??log?4.170 bit18(2)

111p(xi)???66361I(xi)??logp(xi)??log?5.170 bit36(3)

两个点数的排列如下： 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 51 52 53 54 61 62 63 64

共有21种组合：

15 25 35 45 55 65 16 26 36 46 56 66

其中11，22，33，44，55，66的概率是其他15个组合的概率是2??111?? 6636111? 66181111??H(X)???p(xi)logp(xi)???6?log?15?log??

实验4 Huffman编码对英文文本的压缩和解压缩

一、实验内容

根据信源压缩编码——Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。 二、实验环境

1. 计算机

2. Windows 2000 或以上 3. Microsoft Office 2000 或以上 4. VC++ 6.0 三、实验目的

1. 掌握Huffman编码的原理

2. 掌握VC开发环境的使用（尤其是程序调试技巧） 3. 掌握C语言编程（尤其是位运算和文件的操作） 4. 掌握数据结构的内容：链表、顺序表、堆栈、最优二叉树 5. 掌握结构化程序分析和开发的软件工程原理 四、实验要求

1. 提前预习实验，认真阅读实验原理。

2. 认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老

师的管理。

3. 认真填写实验报告。 五、实验原理

压缩/解压缩流程

压缩流程：

读取扫描文本文件——〉统计字符频率——〉生成码字——〉保存压缩文件 解压缩流程：

读取扫描压缩文件——〉提取字符频率——〉生成码树——〉保存文本文件 六、参考书

1.

实验4 Huffman编码对英文文本的压缩和解压缩

一、实验内容

根据信源压缩编码——Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。 二、实验环境

1. 计算机

2. Windows 2000 或以上 3. Microsoft Office 2000 或以上 4. VC++ 6.0 三、实验目的

1. 掌握Huffman编码的原理

2. 掌握VC开发环境的使用（尤其是程序调试技巧） 3. 掌握C语言编程（尤其是位运算和文件的操作） 4. 掌握数据结构的内容：链表、顺序表、堆栈、最优二叉树 5. 掌握结构化程序分析和开发的软件工程原理 四、实验要求

1. 提前预习实验，认真阅读实验原理。

2. 认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老

师的管理。

3. 认真填写实验报告。 五、实验原理

压缩/解压缩流程

压缩流程：

读取扫描文本文件——〉统计字符频率——〉生成码字——〉保存压缩文件 解压缩流程：

读取扫描压缩文件——〉提取字符频率——〉生成码树——〉保存文本文件 六、参考书

1.

第四章 信源编码

一、 信源编码的作用

(1)把信源发出的模拟信号转换成以二进制为代表的数字式信息序列，完成模拟信号数字化。

(2)为了使传输更有效，把与传输内容无关的冗余信息去掉，完成信源的数据压缩。

二、 模拟信号数字化法方法 1．模拟调制

正弦波调制，调幅(AM)、调频(FM)和调相(PM)，采用的载波是正弦波，已调信号在时间上是连续的，它们均属于模拟调制。

脉冲调制，如脉冲幅度调制(PAM)、脉冲相位调制(PPM)和脉冲宽度调制(PWM)等，虽然已调波在时间上被取样离散化了，但各自的调制参数是按照信源的规律连续地变化，所以仍然属于模拟调制的范畴。

2．模拟信号数字化法方法

模拟信号数字化的方法有很多种：脉冲编码调制（Pulse Code Modulation ，缩写为PCM）、增量调制（Delta Modulation，缩写为DM或ΔM）、差分脉冲编码调制（缩写为DPCM）等。

脉冲编码调制(PCM)。其过程为抽样、量化、编码等，使已调波不但在时间上是离散的，且在幅度变化上用数字来体现，这便是模拟信号数字化。

4.1 抽样定理

一、抽样的概念

1．抽样的概念：抽样又可称为取样或者采样。

抽样定理是任何模拟信号数字化的理论基础。实质上，

2-1、一阶马尔可夫链信源有3个符号

?u1,u2,u3?，转移概率为：p(u1u1)?1，

2p(u2u1)?12，p(u3u1)?0，p(u1u2)?13 ，p(u2u2)?0，p(u3u2)?23，p(u1u3)?13，p(u2u3)?23，p(u3u3)?0。画出状态图并求出各符号稳态概率。

解：由题可得状态概率矩阵为：

0??1/21/2??

02/3 [p(sj|si)]?1/3????1/32/30?? 状态转换图为：

令各状态的稳态分布概率为W1，W2，W3，则： W1=

111122W1+W2+W3 ， W2=W1+W3 , W3=W2 且：W1+W2+W3=1 233233?稳态分布概率为：

296 W1=，W2=，W3=

525252-2.由符号集｛０，１｝组成的二阶马尔可夫链，其转移概率为：

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画出状态图，并计算各符号稳态概率。 解：状态转移概率矩阵为：

?0.8 0.2 0 0??0 0 0.5 0.

2.1一个马尔可夫信源有3个符号?u1,u2,u3?，转移概率为：p?u1|u1??1/2，

p?u2|u1??1/2，p?u3|u1??0，p?u1|u2??1/3，p?u2|u2??0，p?u3|u2??2/3，

p?u1|u3??1/3，p?u2|u3??2/3，p?u3|u3??0，画出状态图并求出各符号稳态概率。解：状态图如下

状态转移矩阵为：

1/2u11/31/21/32/32/3u2u3

0??1/21/2??p??1/302/3?

?1/32/30???设状态u1，u2，u3稳定后的概率分别为W1，W2、W3

11?1W1?W2?W3?W110??2W1?33??2512???WP?W9?W1?W3?W2?由?得?2计算可得?W2? 325?W1?W2?W3?1?2?6?W2?W3?W3?3??25??W1?W2?W3?1?

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解：p(

2-1、一阶马尔可夫链信源有3个符号

?u1,u2,u3?，转移概率为：p(u1u1)?1，

2p(u2u1)?12，p(u3u1)?0，p(u1u2)?13 ，p(u2u2)?0，p(u3u2)?23，p(u1u3)?13，p(u2u3)?23，p(u3u3)?0。画出状态图并求出各符号稳态概率。

解：由题可得状态概率矩阵为：

0??1/21/2??

02/3 [p(sj|si)]?1/3????1/32/30?? 状态转换图为：

令各状态的稳态分布概率为W1，W2，W3，则： W1=

111122W1+W2+W3 ， W2=W1+W3 , W3=W2 且：W1+W2+W3=1 233233?稳态分布概率为：

296 W1=，W2=，W3=

525252-2.由符号集｛０，１｝组成的二阶马尔可夫链，其转移概率为：

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画出状态图，并计算各符号稳态概率。 解：状态转移概率矩阵为：

?0.8 0.2 0 0??0 0 0.5 0.

《信息论、编码与密码学》课后习题答案

第1章 信源编码

1.1

考虑一个信源概率为{0.30，0.25，0.20，0.15，0.10}的DMS。求信源熵H（X）。

解： 信源熵 H(X)???pklog2(pk)

k?15

H(X)=-[0.30*(-1.737)+0.25*(-2)+0.2*(-2.322)+0.15*(-2.737)+0.1*(-3.322)]

=[0.521+0.5+0.464+0.411+0.332] =2.228(bit)

故得其信源熵H(X)为2.228bit

1.2 证明一个离散信源在它的输出符号等概率的情况下其熵达到最大值。 解： 若二元离散信源的统计特性为

P+Q=1 H(X)=-[P*log(P)+(1-P)*log(1-P)] 对H(X)求导求极值，由dH(X)/d(P)=0可得

plog?01?pp?11?p

1p?2可知当概率P=Q=1/2时，有信源熵H(X)max

对于三元离散信源，当概率

?1(bit)

时，信源熵

P1?P2?P3?1/3H(X)max?1.585(bit)，

此结论可以推广到N元的离散信源。

1.3 证明不等式

《信息论、编码与密码学》课后习题答案

第1章 信源编码

1.1

考虑一个信源概率为{0.30，0.25，0.20，0.15，0.10}的DMS。求信源熵H（X）。

解： 信源熵 H(X)???pklog2(pk)

k?15

H(X)=-[0.30*(-1.737)+0.25*(-2)+0.2*(-2.322)+0.15*(-2.737)+0.1*(-3.322)]

=[0.521+0.5+0.464+0.411+0.332] =2.228(bit)

故得其信源熵H(X)为2.228bit

1.2 证明一个离散信源在它的输出符号等概率的情况下其熵达到最大值。 解： 若二元离散信源的统计特性为

P+Q=1 H(X)=-[P*log(P)+(1-P)*log(1-P)] 对H(X)求导求极值，由dH(X)/d(P)=0可得

plog?01?pp?11?p1p?2可知当概率P=Q=1/2时，有信源熵H(X)max

对于三元离散信源，当概率

?1(bit)

时，信源熵

P1?P2?P3?1/3H(X)ma?5bit)， x1.58( 此结论可以推广到N元的离散信源。

1.3 证明不等式l

2-1、一阶马尔可夫链信源有3个符号

?u1,u2,u3?，转移概率为：p(u1u1)?1，

2p(u2u1)?12，p(u3u1)?0，p(u1u2)?13 ，p(u2u2)?0，p(u3u2)?23，p(u1u3)?13，p(u2u3)?23，p(u3u3)?0。画出状态图并求出各符号稳态概率。

解：由题可得状态概率矩阵为：

0??1/21/2??

02/3 [p(sj|si)]?1/3????1/32/30?? 状态转换图为：

令各状态的稳态分布概率为W1，W2，W3，则： W1=

111122W1+W2+W3 ， W2=W1+W3 , W3=W2 且：W1+W2+W3=1 233233?稳态分布概率为：

296 W1=，W2=，W3=

525252-2.由符号集｛０，１｝组成的二阶马尔可夫链，其转移概率为：

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画出状态图，并计算各符号稳态概率。 解：状态转移概率矩阵为：

?0.8 0.2 0 0??0 0 0.5 0.