信息论基础和信息论与编码

实验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、 3、

理解离散信道容量的内涵；

掌握求二元对称信道（BSC）互信息量和容量的设计方法； 掌握二元扩展信道的设计方法并会求其平均互信息量。

二、实验原理

若某信道输入的是N维序列x，其概率分布为q(x),输出是N维

序列y,则平均互信息量记为I(X;Y)，该信道的信道容量C定义为

C?maxI(X;Y)。

q(x)三、实验内容

1、给定BSC信道，信源概率空间为

X

P

=

０ １ 0.6 0.4

?0.990.01?信道矩阵 P??? 0.010.99??求该信道的I(X;Y)和容量，画出I(X;Y)和?、C和p的关系曲线。 2 、编写一M脚本文件t03.m，实现如下功能：

在任意输入一信道矩阵P后，能够判断是否离散对称信道，若是，求出信道容量C。 3、已知X=(0,1,2);Y=(0,1,2,3),信源概率空间和信道矩阵分别为

X

Px

=

０ １ ２ 0.3 0.5 0.2

P=

0.1 0.3 0 0.6 0.3 0.5 0.2 0 0.1 0.7 0.1 0.

实验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.

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(

实验二 离散信道及其容量

一、实验目的

1、 2、 3、

理解离散信道容量的内涵；

掌握求二元对称信道（BSC）互信息量和容量的设计方法； 掌握二元扩展信道的设计方法并会求其平均互信息量。

二、实验原理

若某信道输入的是N维序列x，其概率分布为q(x),输出是N维

序列y,则平均互信息量记为I(X;Y)，该信道的信道容量C定义为

C?maxI(X;Y)。

q(x)三、实验内容

1、给定BSC信道，信源概率空间为

X

P

=

０ １ 0.6 0.4

?0.990.01?信道矩阵 P??? 0.010.99??求该信道的I(X;Y)和容量，画出I(X;Y)和?、C和p的关系曲线。 2 、编写一M脚本文件t03.m，实现如下功能：

在任意输入一信道矩阵P后，能够判断是否离散对称信道，若是，求出信道容量C。 3、已知X=(0,1,2);Y=(0,1,2,3),信源概率空间和信道矩阵分别为

X

Px

=

０ １ ２ 0.3 0.5 0.2

P=

0.1 0.3 0 0.6 0.3 0.5 0.2 0 0.1 0.7 0.1 0.

香农信息论的基本理论探究

制作者：陈喆 指导老师：杜奕

【内容摘要】：信息是自从人类出现以来就存在于这个世界上了，天地万物，飞禽走兽，以及人类的生存方式都离不开信息的产生和传播。人类每时每刻都在不停的接受信息，传播信息，以及利用信息。从原来的西汉时期的造纸，到近代西方的印刷术，以及现在的计算机，信息技术在人类历史的进程当中随着生产力的进步而发展。而信息理论的提出却远远落后于信息的出现，它是在近代才被提出来而形成一套完整的理论体系。信息论的主要基本理论包括：信息的定义和度量；各类离散信源和连续信源的信息熵；有记忆、无记忆离散和连续信道的信道容量；无失真信源编码定理。

【关键词】：平均自信息 信道容量 信源编码 霍夫曼码

一．信息的度量 在各种通信系统的信源当中，离散随机信源是一类最基本的信源，信源输出是单个的符号的消息，并且消息之间是两两互不相容的。假设有个一维离散无记忆信源，它的概率分布函数决定了他所携带的信息。该信源空间中共有q个符号，每个符号发生的概率是Pi,那么发出某个符号所携带的信息量是-logPi ,由于概率是在0和1之间的，使得每一事件的信息量是非负的。如果该事件发生的概率是0，或者是1，则表明该事件一定不会发生或者

信息论基础与编码的期末试题

1、一副充分洗乱的扑克牌（52张），从中任意抽取1张，然后放回，若把这一过程看作离散无记忆信源，则其信源熵为__log2 52________________ 。

2、信息率失真理论是量化、数模转换、频带压缩和___数据压缩_____________ 的理论基础。

3、信源的消息通过信道传输后的误差越大，信宿收到消息后对信源存在的不确定性就越大，获得的信息量就越小。

= 9kHz 。

4、高斯加性噪声信道中，信道带宽3kHz，信噪比为7，则该信道的最大信息传输速率C

t

5、BSC信道即：无记忆二进制对称信道。

1、给定xi条件下随机事件yj所包含的不确定度和条件自信息量p(yj /xi).( D )

A．数量上不等，单位不同B．数量上不等，单位相同

C．数量上相等，单位不同D．数量上相等，单位相同

2、条件熵和无条件熵的关系是：( C )

A．H(Y/X)＜H(Y) B．H(Y/X)＞H(Y)

C．H(Y/X)≤H(Y) D．H(Y/X)≥H(Y)

3、根据树图法构成规则， ( D )

A．在树根上安排码字B．在树枝上安排码字

C．在中间节点上安排码字D．在终端节点上安排码字

4、下列说法正确的是：( C )

A．奇异码是唯

武汉大学 电子信息学院 信号处理实验室 杨文老师 《信息论与编码理论》课件

信息论与编码理论

杨文通信工程系

武汉大学 电子信息学院 信号处理实验室 杨文老师 《信息论与编码理论》课件

第三章信道容量第三章信道容量

内容提要内容提要信道对于信息率的容纳并不是无限制的信道对于信息率的容纳并不是无限制的，它不仅与物理信道本身的特性有关，还与，它不仅与物理信道本身的特性有关，还与信道输入信号的统计特性有关，它有一个极信道输入信号的统计特性有关，它有一个极限值，即信道容量，信道容量是有关信道的限值，即信道容量，信道容量是有关信道的一个很重要的物理量。这一章研究信道，研一个很重要的物理量。这一章研究信道，研究在信道中传输的每个符号所携带的信息量究在信道中传输的每个符号所携带的信息量，并定义信道容量。,并定义信道容量。2006-10-18 2

武汉大学 电子信息学院 信号处理实验室 杨文老师 《信息论与编码理论》课件

3信道容量第三章信道容量

信道的功能：以信号形式传输和存储信息。信道传输信息的速率：与物理信道本身的特性、载荷信息的信号形式和信源输出信号的统计特性有关。信道容量研究内容：在什么条件下，通过信道的信息量最大。

3.1信道的数学模型和分类 3.2单符号离散信道

信息论与编码考试试卷

2012——2013学年 第一学期

课程名称：信息论与编码

试卷形式：开卷□闭卷□

试题 得分 一 二 三 四 五 六 七 八 总分 常用对数：log23?1.585

一、 选择题（共10分，每小题2分）

x2x3x4??X??x1、有一离散无记忆信源X，其概率空间为????1，??P??0.50.250.1250.125?则其无记忆二次扩展信源的熵H(X2)=( )

A、1.75比特/符号； B、3.5比特/符号； C、9比特/符号； D、18比特/符号。

0000??P(y1/x1)P(y2/x1)?，00P(y/x)P(y/x)002、信道转移矩阵为?3242???000P(y5/x3)P(y6/x3)??0?其中P(yj/xi)两两不相等，则该信道为

A、一一对应的无噪信道 B、具有并归性能的无噪信道 C、对称信道

D、具有扩展性能的无噪信道

3、设信道容量为C，下列说法正确的是：（ ） A、互信息量一定不大于C

B、交互熵一定不小于C C、有效信息量一定不大于C D、条件熵一定不大于C

4、在串联系统中，有效信息量的值（ ） A、趋于变大

5-1 有一信源，它有六种可能的输出，其概率分布如下表所示，表中给出了对应的六种编码C1、C2、C3、C4、C5和C6。

（1） 求这些码中哪些是唯一可译码； （2） 求哪些是非延长码（即时码）；

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

消息 概率C1 000 001 010 011 100 101 C2 0 01 011 0111 01111 C3 0 10 110 1110 11110 C4 0 10 1101 1100 1001 C5 1 000 001 010 110 110 C6 01 001 100 101 110 111 a1 a2 a3 a4 a5 a6 1/2 1/4 1/16 1/16 1/16 1/16 011111 111110 1111 解：（1）1,2,3,6是唯一可译码； (2)1,3,6是即时码。

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

证明：由定理可知若存在一个码长为L1,L2,?,Lq的唯一可译码，则必定满足kraft不等式

?ri?1q?li?1。由定理4?4可知若码长满足kraft不等式，则一定存在这样码长的即时码。

所以若存在码长L1,L2,?