《信息理论与编码》
课程论文
题目: 信息论的基本理论探究
学生姓名:
学 号:
系 别:
专 业:
任课教师:
年 月 日
目 录
摘 要.............................................................. 2
关键词............................................................. 2
1 前言............................................................. 3
2 信息的度量....................................................... 4
2.1 概述........................................................ 4
2.2 离散信源及其信息度量........................................ 4
2.2.1 离散随机信源的自信息与信息熵.......................... 4
2.2.2 离散平稳信源.......................................... 5
2.2.3 马尔可夫信源.......................................... 6
3 离散信道......................................................... 6
3.1 概述........................................................ 6
3.2 平均互信息.................................................. 7
3.3 离散信道的信道容量.......................................... 7
4 连续信道......................................................... 7
5 无失真信源编码................................................... 8
5.1 信源编码到无失真编码的概述.................................. 8
5.2 定长编码.................................................... 9
5.3 变长编码.................................................... 9
5.3.1 概述.................................................. 9
5.3.2 香农编码............................................. 10
5.3.3 费诺编码............................................. 10
5.3.4 霍夫曼编码........................................... 11
6 本次课程论文总结................................................ 11
参考文献.......................................................... 12
信息论的基本理论探究
摘 要
信息是从人类出现以来就存在于这个世界上,人类社会的生存和发展都离不开信息的获取、传递、处理、再生、控制和处理。而信息论正是一门把信息作为研究对象,以揭示信息的本质特性和规律为基础,应用概率论、随即过程和数理统计等方法来研究信息的存储、传输、处理、控制、和利用等一般规律的学科。主要研究如何提高信息系统的可靠性、有效性、保密性和认证性,以使信息系统最优化。在信息论的指导下,信息技术得到飞速发展,这使得信息论渗透到自然科学和社会科学的所有领域,并且应用与众多领域:编码学、密码学与密码分析、数据压缩、数据传输、检测理论、估计理论等。信息论的主要基本理论包括:信息的定义和度量;各类离散信源和连续信源的信源熵;有记忆,无记忆离散和连续信道的信道容量,平均互信息;无失真信源编码相关理论。
关键词
信息度量;离散和连续信源;信道容量;平均互信息;信源编码
1 前言
被称为“信息论之父”的美国科学家香农于1948年10月发表于《贝尔系统技术学报》上的论文《A Mathematical Theory of Communication》(通信的数学理论)作为现代信息论研究的开端。这一文章部分基于哈里·奈奎斯特和拉尔夫·哈特利先前的成果。他为信息论奠定了理论基础。后来其他的科学家做出了更深入的探究,使信息论到现在形成了比较完整的理论体系。
信息论将信息的传递作为一种统计现象来考虑,给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信息传输定理、信源-信道隔离定理相互联系。
信息不同于情报、知识、消息、信号等概念。信息论所包含的含义比其他几种理论概念更加广泛,更具有概括性。情报的定义是对某个特定的对象所见、所闻、所理解而产生的知识,情报的含义要比“信息”窄得多。知识是人们根据某种目的,从自然界收集得来的数据中,整理、概括、提取得到的价值的、人们所需的信息。消息是用文字、符号、数据、语言、音符、图片、图像等能够被人们感觉器官所感知的形式,把客观物质运动和主管思维活动的状态表达出来的就成为“消息”。所以信息不等同于消息,而信号携带消息,是消息的运载工具,所以信息也不等同于信号。信息是事物运动状态或存在方式的不确定性的描述,这就是香浓信息的定义。
下面从信息论的一些基本理论研究。
2 信息的度量
2.1 概述
信息这一概念是比较抽象的,它不像通常的长度,重量等概念,有一个比较直观的印象,信息必须要有一个比较容易用来分析的度量的数学工具。这样才方便人们能够更好的认识和理解它。香农对信息的度量给出了严格的数学定义。
2.2 离散信源及其信息度量
2.2.1 离散随机信源的自信息与信息熵
在通信系统的各种信源中,离散随机信源是最基本的一种信源,信源输出是单个的符号的消息,并且消息之间是两两互不相容的。我们知道,事件发生的不确定性与事件发生的概率有关:事件的发生概率越小,不确定性就越大,事件发生的概率越大,不确定性就越小,对于发生概率为1的必然事件就不存在不确定性。设一离散信源的概率空间为:
...
...
即,如果知道已发生,则该事件所含有的信息量称自信息,表达式为:
上面的自信息是指某一信源发出某一消息所含的信息量,但所发消息不同,它们所含信息量也就不同,所以自信息不能作为整个信源的信息测度,我们定义平均自信息量,即对每个事件各自所携带的信息量做一个加权平均,也称信息熵,表示如下:
信息熵具有一些基本的性质,比如,对称性,确定性,非负性,扩展性,可加性等等。这里面有一个最大离散熵定理,表明:离散信源情况下,对于具有q个符号的离散信源,只有在q个信源符号等可能出现的情况下,信源熵才能达到最大值,这样也表明等概率分布信源的平均不确定性为最大。
2.2.2 离散平稳信源
离散平稳信源也是一种非常重要的信源。不同时刻信源输出符号的概 率分布完全相同,则称为一维离散平稳信源。二维离散平稳信源就是信源输出的随机序列…,X1,X2,…,Xi,…,满足其一维和二维概率分布与时间起点无关。这种各维联合概率分布均匀与时间起点无关的完全平稳信源称离散平稳信源。
二维离散平稳信源的联和熵为:,此值表示原来信源X输出任意一对可能的消息的共熵,即描述信源X输出长度为2的平均不确定性,或所含的信息量,因此可用作为二维离散平稳信源的信息熵的近似值。
2.2.3 马尔可夫信源
在非平稳离散信源中有一类特殊信源,这类信源输出符号序列中符号之间的依赖关系是有限的,它满足马尔可夫链的性质,因此可用马尔可夫链来处理。马尔可夫信源满足下面两个条件:
⑴ 某一时刻信源符号的输出只与此刻信源所出的状态有关,而与以前的状态及以前的输出符号都无关。
⑵ 信源某时刻所处的状态由当前的输出符号和前一时刻信源的状态唯一决定。
m阶有记忆的离散信源用马氏链来描述就成了m阶马尔可夫源,当m=1时就为一阶马尔可夫信源。一般马尔可夫信源的信息熵应该是其平均符号熵的极限值,即:。
3 离散信道
3.1 概述
信道的任务是以信号方式传输信息和存储信息的。我们知道信源输出的是携带着信息的消息。消息必须要转换成能在信道中传输或存储的信号,然后通过信道传送到收信者。并且认为噪声或干扰主要从信道中引入。信道根据用户的多少,可以分为两端信道,多端信道。 根据信道输入端和输出端的关联,可以分为无反馈信道,反馈信道。根据信道的参数与时间的关系信道可以分为固定参数信道,时变参数信道。根据输入和输出信号的统计特性可以分为离散信道,连续信道,半离散或半连续信道和波形信道。
3.2 平均互信息
先引入信道疑义度:;它表示在输出端收到输入变量Y的符号后,对于输入端的变量X尚存在平均不确定性(存在疑义)。我们已知代表接收到输出符号以前关于输入变量X的平均不确定性,由此可见,通过信道传输消除了一些不确定性,获得了一定的信息,X与Y之间的平均互信:。
3.3 离散信道的信道容量
信道矩阵中每一行和每一列分别由同一概率分布集中的元素不同排列组成的,这就是对称离散信道。计算对称离散信道的信道容量公式是: (比特/符号)。右边的第一项是输出符号的最大信息熵,第二项是信道矩阵分布行矢量的熵函数。
4 连续信道
在某一时刻,输出的信号既是连续又是随机的,我们称之为随机波形信源。用连续随机变量来描述输出消息的信源就是连续信源。连续信源的熵为:。
和离散信道一样 ,对于固定的连续信道和波形信道都有一个最大的信息传输率 ,称之为信道容量 。它是信道可靠传输的最大信息传输率 。对于不同的连续信道和波形信道,它们存在的噪声形式不同,信道带宽及对信号的各种限制不同 ,所以具有不同的信道容量 。 我们先来讨论单符号高斯加性信道的信道容量 ,单符号高斯加性信道是指信道的输入和输出都是取值连续的一维随机变量 ,而加入信
道的噪声是一维高斯加性噪声。它的信道容量表达式为:
其中, 是输入信号 X 的平均功率,是高斯噪声的平均功率。只有当信的输入信号是均值为零 ,平均功率为高斯分布的随机变量时 。信息传输率才达到这个最大值。
5 无失真信源编码
5.1 信源编码到无失真编码的概述
为了减少信源输出符号序列中的剩余度,提高符号的平均信息量,对信源输出的符号序列所施行的变换。具体说,就是针对信源输出符号序列的统计特性来寻找某种方法,把信源输出符号序列变换为最短的码字序列,使后者的各码元所载荷的平均信息量最大,同时又能保证无失真地恢复原来的符号序列。为了有效的传播信息,最理想状态即为无失真传输。在无失真信源编码中又分为定长编码、变长编码和最佳长编码。
5.2 定长编码
在定长编码中,K是定值,编码的目的即为找到最小的K值。要实现无失真传输的信源编码,不但要求信源符号的码字是一一对应的,而且还要求有码字组成的符号序列的逆变换也是唯一的。由定长编码定理可知,当编码器容许的信息率,也就是当每个信源符号必须输出的码长是K=K1/logm。由定理表明,只要码字所能携带的信息量大于信源序列输出的信息量,则可以使传输几乎无失真传输,但是条件是L足够大。这就为传输带来了很大的麻烦,并且实现起来很困难,并且编码效率也不高。而要达到编码效率接近1的理想编码器虽有存在性,在实际上是不可能的,因为L非常大,无法实现。由此产生了变长编码。
5.3 变长编码
5.3.1 概述
在变长编码中,码长K是变化的,可根据信源各个符号的统计特性,对概率大的符号用短码,而对概率晓的符号用长码。这样大量信源符号编程码后,平均每个信源符号所需的输出符号数就降低,从而提高编码效率。用变长编码来达到相当高的编码效率,一般所要求的符号长度L可以比定长编码小得多得多。很明显,定长编码需要的信源序列长,这使得码表很大,且总存在起码差错。而变长码要求编码效率达到96%时,需要L=2。因此用变长编码编码时,L不需要很大就可达到相当高的编码效率,而且可实现无失真编码。并且随着信源序列长度的增加,编码效率越来越接近于1,编码后的信息传输率R也越来越接近于无噪无损二元对称信道的信道容量C=1bit/二元码符号,达到信源与信道匹配,使信道得到充分利用。
5.3.2 香农编码
香农第一定理指出了平均码长与信源之间的关系,同时也指出了可以通过编码使平均码长达到极限值,这是一个很重要的极限定理。香农第一定理指出,每个码字的长度Ki满足下式:I(xi)
5.3.3 费诺编码
费诺编码属于概率编码,但不是最佳的编码方法。在编N进制
时首先将信源消息符号按其出现的概率依次由小到大排列开来,并将排列好的信源符号概率值分N大组,使N组的概率之和近似相同,并对各组赋予一个N进制码元“0”“1”……“N-1”。之后再针对每一大组内的信源符号做如上处理,即再分为概率和相同的N组,赋予N进制码元。如此重复,直至每组只剩下一个信源符号为止。此时每个信源符号所对应的码字即为费诺码。针对同一信源,费诺码要比香农码的平均码长小,传输速率大,编码效率高。
5.3.4 霍夫曼编码
编码方法:也是先将信源符号按其出现的概率大小依次排列,并取概率最小的字母分别配以0和1两个码元(先0后1或者先1后0,以后赋值固定),再将这两个概率相加作为一个新字母的概率,与未分配的二进制符号的字母重新排队。并不断重复这一过程,直到最后两个符号配以0和1为止。最后从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即为对应的码字。
霍夫曼编码方式得到的码并非唯一的。在对信源缩减时,两个概率最小的符号合并后的概率与其他信源符号的概率相同时,这两者在缩减中的排序将会导致不同码字,但不同的排序将会影响码字的长度,一般讲合并的概率放在上面,这样可获得较小的码方差。
霍夫曼码的平均码长最小,消息传输效率最大,编码效率最高。
6 本次课程论文总结
通过对信息论的学习,我们发现信息论其实是一门理论性很强的学科,它涉及到众多学科。对于整个信息论的理论体系的认识也有了一个清晰的思路:首先介绍到的是信息的定义及其本质,我收获最大的是香农提出的狭义信息论的条件(非绝对论观点,形式假说,不确定性)。再而学习到了各类信源的熵,信道及信道容量,主要研究的是离散信源和连续信源。最后是无失真信源编码,其中包含等长信源编码和变长信源编码;主要研究的变长信源编码。这就差不多构成信息论的整个基本理论结构。在此我也要感谢万老师的悉心教导,使我更好的掌握了信息论的理论基础,为以后在通信领域以及其他方面的研究都奠定了坚实的基础。信息论发展到今天虽然已经做到比较全面,但仍旧存在一些不足,需要我们做更多的探讨,所以我会更加努力的学习,培养敢于创新,敢于挑战,为以后的生活和工作做好准备!
参考文献
[1] 傅祖芸.信息论—基础理论与应用(第二版).北京:电子工业出版社,2007.5
[2] 傅祖芸.信息论基础.北京:电子工业出版社,1989
[3] R W汉明.朱雪龙译.编码和信息理论.北京:科学出版社,1984
[4] 王育民,梁传甲.信息与编码理论.西安:西安电子科技大学出版社,1986
[5] 周炯槃.信息理论基础.北京:人民邮电出版社,1983
[6] 钟义信.信息科学原理.北京:北京邮电大学出版社,1996