下载文档原格式
《信息论基础》教学大纲课程编码：1512105602课程名称：信息论基础学时/学分：36/2先修课程：《概率论与数理统计》、《随机过程》、《信息科学导论》适用专业：信息与计算科学开课教研室：信息与计算科学教研室一、课程性质与任务1．课程性质：本课程是信息与计算科学专业的一门专业选修课，是拟从事通信及相关行业工作的学生所必修，为本科三年级学生所选修。
2．课程任务：通过本课程的学习，学生应熟练掌握离散（连续）条件下的熵、条件熵、相对熵、互信息的概念，熟练掌握有（无）失真条件下的信源（信道）编码定理和一些常用编码并能熟练的应用它们，为今后的学习与科研打下坚实的基础。
二、课程教学基本要求掌握信息的基本理论，理解离散信源、连续信源的有关理论，熟练掌握信息、信息熵、条件熵、联合熵、互信息等的计算，了解通信系统的整个过程，熟练掌握基本的信源编码方法和信道编码方法，会判定信源码、信道码的优劣。
本课程主要以课堂讲授为主，在教学方法和手段上采用现代教育技术。
成绩考核形式：期终成绩（考查）（70%）＋平时成绩（平时测验、作业、课堂提问、 课堂讨论等）（30％）。
成绩评定采用百分制，60分为及格。
三、课程教学内容第一章 随机变量的信息度量1.教学基本要求理解和掌握的定义和计算式，理解有关熵的一些基本性质，了解广义熵及相互间的关系。
2.要求学生掌握的基本概念、理论通过本章学习，使学生能准确理解并掌握信息、熵、联合熵、条件熵等有关信息量的定义及计算式，理解熵的基本性质，了解广义熵的多种形式并了解它们之间的关系。
3.教学重点和难点教学重点是要让学生掌握熵的概念和性质，熟练计算熵、联合熵、条件熵、相对熵和互信息，并会用熵求解一些实际问题。
4.教学内容第一节 自信息第二节 熵、联合熵、条件熵第三节 相对熵和互信息第四节 信息量的一些基本性质第五节 广义熵第二章 随机过程的信息度量和渐进等分性1.教学基本要求理解和掌握信源、随机过程的基本概念，掌握无记忆信源、马氏信源、平稳性、遍历性，理解AEP性质，理解AEP性质在数据压缩中的应用，了解香农-麦克米兰-布瑞曼定理。
信息论发展现代信息论是从上世纪二十年代奈奎斯特和哈特莱的研究开始的,他们最早开始研究了通信系统传输信息的能力,并且试图度量系统的信道容量。
香农于1940年在普林斯顿高级研究所期间开始思考信息论与有效通信系统的问题。
经过8年的努力,1948年,来自贝尔研究所的ClaudeShannon（克劳德·香农）的《通信的数学理论》论文公诸于世,从此宣告了崭新的一门关于信息发面的学科──信息论的诞生。
1949年,香农又在该杂志上发表了另一著名论文《噪声下的通信》。
在这两篇论文中,香农阐明了通信的基本问题,给出了通信系统的模型,提出了信息量的数学表达式,并解决了信道容量、信源统计特性、信源编码、信道编码等一系列基本技术问题。
两篇论文成为了信息论的奠基性著作。
这两篇论文一起阐述了现代信息论的基础。
并且香农开始创造性的定义了“信息”。
信息论自从二十世纪四十年代中叶到二十一世纪初期,现已成为一门独立的理论科学,他给出一切传输、存储、处理信息系统的一般理论,并指出,实现有效、可靠地传输和存储信息的途径是走数字化的道路。
这是通信技术领域数字化革命的数学或理论基础。
1946年的计算机和1947年晶体管的诞生和相应技术的发展,是这一革命的物理或物质基础。
信息论是在长期的通信工程实践和理论研究的基础上发展起来的。
当物理学中的电磁理论以及后来的电子学理论一旦有某些进展,很快就会促进电信系统的创造发明或改进。
这是因为通信系统对人类社会的发展,其关系实在是太密切了。
日常生活、工农业生产、科学研究以及战争等等,一切都离不开消息传递和信息流动。
通信系统是人类社会的神经系统,即使在原始社会也存在着最简单的通信工具和通信系统,这方面的社会实践是悠久漫长的。
自从香农十九世纪四十年代末两篇论文发表后,前苏联和美国的科学家采取了不同的研究途径经一部发展了信息论。
柯尔莫哥洛夫、宾斯基和达布鲁新为首的一批著名数学家致力于信息论的公理化体系和更一般更抽象的数学模型,对信息论的基本定理给出了更为普遍的结果,为信息论发展成数学的一个分支作出了贡献。
2.2 重要定理2.2.1 链式法则从定理 2.1，我们得到：)|()(),(X Y H X H Y X H +=和)|()(),(Y X H Y H Y X H +=，并解释说它们是熵的链式法则在两个随机变量情况下的特例。
现在，我们来看它的一般形式，即针对一组随机变量的情况。
世界上有很多事情取决于多种因素，这时就可以看作多个随机变量共同决定了事情的不确定性。
定理2.3（熵的链式法则）设随机变量n X X X ,,,21 服从联合分布),,,(21n x x x p ，则∑=-=ni i i n X X X H X X X H 11121),,|(),,,( (2-36)证明 根据式(2-15)，可以把等式左边写成左边=)),,,,((),,,(12121n n n X X X X H X X X H -=)),,,(|(),,,(121121--+=n n n X X X X H X X X H)),,,(|(),,,(2211221---+=n n n X X X X H X X X H ),,|(11X X X H n n -+∑=-=ni i i X X XH 111),,|( =右边在证明过程中，我们没有使用联合概率分布),,,(21n x x x p ，如果使用之，同样可以证明这个定理。
可以从物理概念上对上述定理加以解释：多随机变量的联合熵是多个事件同时发生的不确定性，它应该等于事件1X 的不确定性与1X 已出现的情况下其它事件同时发生的不确定性之和，而后者是1X 已出现的前提下事件2X 的不确定性，与1X 、2X 已出现的情况下其它事件同时发生的不确定性之和，依此类推。
这个定理告诉我们一个重要的结论：多随机变量的联合熵等于条件熵之和。
；如果多个事件互相独立，问题就变得更简单了。
例如，我们班上有n 个同学，每人的学习成绩是[0，100]间的随机数，用随机变量i X 表示。
根据上述定理，全班成绩的不确定性为∑=-=ni i i n X X X H X X X H 11121),,|(),,,( ，是条件熵之和，但是由于大家的成绩相互独立，全班成绩的不确定性只由每人成绩不确定性之和决定，即为∑=n i i X H 1)(。
第1章绪论第2章熵和互信息§2.1 随机变量的熵和互信息2.1.1 事件的自信息和互信息2.1.2 条件事件的互信息与联合事件的互信息2.1.3 随机变量的平均自信息——熵2.1.4 熵的性质2.1.5 凸函数2.1.6 随机变量间的平均互信息2.1.7 概率分布的散度(相对熵)2.1.8 关于疑义度的Fano不等式2.1.9 马尔可夫链和数据处理定理2.1.10* Shannon信息度量与集合论之间的联系2.1.11*信息论与博奕之间的关系§2.2 连续随机变量的互信息和微分熵2.2.1 连续随机变量的互信息2.2.2 连续随机变量的熵——微分熵2.2.3 微分熵的极大化§2.3 平稳离散信源的熵2.3.1 平稳离散信源一般概念2.3.2 平稳信源的熵2.3.3 马尔可夫信源§2.4 平稳随机过程的信息量与熵习题第3章离散无记忆信源的无损编码§3.1 离散无记忆信源的等长编码3.1.1 等长编码3.1.2 Shannon信源编码定理叙述3.1.3 渐近等分性质（AEP）与Shannon定理的证明§3.2 离散无记忆源（DMS）的不等长编码3.2.1 不等长编码的唯一可译性和译码延时3.2.2 Kraft不等式3.2.3 不等长编码定理§3.3 几种不等长编码算法3.3.1 最佳不等长编码（Huffman编码）3.3.2 Shannon编码法3.3.3 Fano编码3.3.4 Shannon-Fano-Elias编码3.3.5 算术编码3.3.6*通用信源编码算法3.3.7*压缩编码与离散随机数发生§3.4 平稳信源和马尔可夫信源的编码定理3.4.1 平稳信源的编码3.4.2 马尔可夫信源的编码习题第4章信道、信道容量及信道编码定理§4.1 信道，信道模型和分类§4.2 离散无记忆信道（DMC）及其容量4.2.1 信道容量定义及例子4.2.2 离散无记忆信道（DMC）的容量定理4.2.3 对称离散无记忆信道容量的计算4.2.4 转移概率矩阵可逆信道的容量计算4.2.5*离散无记忆信道（DMC）容量的迭代计算§4.3 信道的组合4.3.1 积信道（平行组合信道）4.3.2 和信道4.3.3 级联信道§4.4 离散无记忆信道（DMC）的编码定理4.4.1 几个有关定义4.4.2 二进对称信道编码定理的证明4.4.3*一般离散无记忆信道编码定理的证明(典型列方法) 4.4.4*信道编码定理之逆4.4.5*具有理想反馈的离散无记忆信道的容量4.4.6*信源、信道编码分离定理和信源、信道联合编码§4.5 加性高斯噪声（A WGN）信道4.5.1 高斯信道的容量4.5.2*高斯信道编码定理4.5.3*高斯信道编码定理之逆4.5.4*带有独立高斯噪声的平行信道4.5.5*带有相关高斯噪声的平行信道4.5.6*MIMO高斯信道的容量§4.6 模拟信道的信道容量4.6.1 带限、加性白高斯噪声信道。
第四章抽象代数基础自古以来，许多数学家都在探讨数学的“本质”。
为使庞大的数学知识变得简而精，数学家们经常依据数学各领域间潜在的共性，提出统一数学各部分的新观点、新方法。
1872年，德国数学家克莱因提出了用“群”的观点来统一当时杂乱的各种几何学（欧氏几何、非欧几何包括黎曼几何和罗氏几何等）；1883年，美国数学家毕尔霍夫提出“格”的概念，以统一代数系统的各种理论和方法；十九世纪末二十世纪初出现了公理化运动，以公理系统作为数学统一的基础。
1938年法国布尔巴基学派不但继承了公理化运动的成果，而且提出数学公理结构的概念，以非常抽象的方式叙述全部数学，把数学的核心部分在结构这一概念下统一成一个整体。
他们认为整个数学学科的宏伟大厦可以99建立在丝毫不求助于直观的彻底公理化基础上。
他们从集合论出发，对全部数学分支给予完备的公理化，认为最普遍、最基本的数学结构有三类：代数结构、顺序结构、拓扑结构。
而群结构是最基本的代数结构之一。
我们所要介绍的抽象代数也叫近世代数，就是研究代数结构（或代数系统）的一门学科。
抽象代数有许多分支，除了线性代数外，还有群论、环论、域论、格论、布尔代数、李代数等等。
这些分支都先后在其他科学领域中找到了用场。
布尔代数后来在线路设计、自动化系统、电子计算机设计方面得到了广泛应用。
线性代数、群、环、域，特别是有限域的理论，看起来很抽象，然而在编码问题中却找到了具体的应用，起着重要的作用。
因此，要学习编码理论，必须首先学习抽100101 象代数的有关知识。
下面我们就把抽象代数的几个基本概念作一个很粗浅的介绍。
第一节 代数结构——群、环、域一. 集合1. 集合的基本概念集合：在一定范围内的讨论对象组成的整体。
元素：组成一个集合的各个个体，叫做这个集合的元素。
子集：设两个集合A 和B ，若A 中的每个元素又都是B 中的元素，则称A 为B 的子集，记为：真子集：若 ，且B 中至少有一个元素不属于A ，则称A 为B 的真子集，记为：AB B A ⊇⊆或,A B ⊇A B B A ⊃⊂或,102 空集：不含任何元素的集合，用Φ表示。
