信息论与编码课程设计

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

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

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

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

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

程设计(论文) 武汉工程大学课

目录

目录 .......................................................................................................... I 摘要 ........................................................................................................ III 前言 ........................................................................................................ IV 1 1.1 1.2 1.3 1.4 2 2.1 2.2 3 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 4 4.1 4.2

课题背景 ............................................................................................. 1 背景

成绩：

教师姓名：

1. 任务说明

2016-2017学年第1学期

《信息论》课程设计

学院名称： 班级学号： 学生姓名：

2016年12月

一、判定唯一可译码

输入：任意的一个码(即已知码字个数及每个具体的码字) 输出：判决结果（是/不是）

输入文件:in1.txt，含至少2组码，每组的结尾为”$”符 输出文件:out1.txt，对每组码的判断结果

说明：为了简化设计，可以假定码字为0，1串

2. 实现原理

判断方法：将码C中所有码字可能的尾随后缀组成一个集合F，当且仅当集合F中没有 包含任一码字，则可判断此码C为唯一可译变长码。

构成集合F：首先观察码C中最短的码字是否是其他码字的前缀。若是，将其所有可能 的尾随后缀排列出。就是将其他码字序列中截去与其最短码字相同的前缀 部分，将余下的序列为尾随后缀。而这些尾随后缀又可能是某些码字的前 缀，或者最短码字又仍是这些尾随后缀的前缀，再将由这些尾随后缀产生 的新的尾随后

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

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.

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

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单符号离散信道