2011信息论基础课程总结(放大版本)

信息科学基础课程总结（一）学习内容：第一章随机变量的信息度量1学习信息论的发展历史，了解信息论的产生、发展与应用；信息的定义与特征；2信息的度量问题；3香农熵——随机变量的不确定性度量；4信息量的一些基本性质；5熟练进行有关熵的计算：香农熵、联合熵、微分熵等（不要忽视条件熵、互信息、相对熵等概念）；6 广义熵。

第二章随机过程的信息度量和渐近等分性1 什么是信源？信源的分类；2 什么是随机过程？什么是马尔可夫信源？3 随机过程的信息度量问题—熵率；4 了解冗余度和相对冗余度；5 了解熵的基本性质，互熵与互信息；6 理解信源编码定理。

7 了解什么是最大熵，记住常用的几种最大熵分布：有限区间上的最大熵、半开直线与全直线上的最大熵。

第三章数据压缩和信源编码1信源编码的基本问题，了解即时码的定义；2等长码概念及其码率；Kraft不等式；3变长码编码及平均码长的定义；4熟练进行哈夫曼码与算术码的编码及构造码树；5了解通用码概念，会编LZW码和YK码；6会计算通用码的压缩率（码率）。

第四章数据可靠传输和信道编码1 了解离散无记忆信道和信道容量；2 会用定义、极值法和Lagrange乘子法计算信道容量；3 了解信道编码的作用和常见类型；4 理解信道编码定理的内容。

信息科学基础习题课一、填空题（20分）：1．利用数字结构进行信息处理是当今社会信息社会的一大特色，因此有人称当今的信息社会又是一个数字化的社会，这就是把现实世界中的各种不同类型的信息与信号都设法用数字来表达，并在数字化的条件下进行处理。

2．信息具有可设计、传递、复制、存储、修改与扩展等特性，对这些特性的处理过程统称为信息处理。

信息科学为研究信息处理提供理论基础，其中包括它们的数学模型、基本的度量关系与性质、相关的优化算法等。

3．时间与空间实际上是信息处理中的最基本的资源，在信息处理中除了加快速度与节省空间之外，寻找它们的最优信息处理方案是信息科学理论中的重要内容与基本目标。

4．信息论一般是指在信息的加工、传递、存储等处理问题中的基础理论问题。

5．1948年香农发表了具有奠基性的论文《通信系统的数学理论》，拉开了信息科学研究的帷幕。

信息的度量问题包括：信息能否度量？如何度量？信息度量的内在含义是什么？信息度量的基本特征（其中包括信息度量与其他学科的相互关系等问题）与信息度量的各种应用问题等。

6．一个量的引进，它的出发点必须基本合理，对这个量的度量对象、意义和内容有一个较为明确而又合理的解释；一个量的引进是否有意义，最终还要看它能否解决问题，解决了什么样的问题，以及它在这些问题中的作用与特征；理解一个量的意义，既要从它原始定义的出发点来理解，又要从它最终解决问题的意义上来理解。

信息不可能通过一种量而确定所有的信息度量问题。

香农熵 是信息的一种最基本与重要的度量。

7．一个通信系统的数学模型由信源、信道、翻码与译码组成，它们可用概率论模型给以描述，并由信息量确定它们的特征。

8．由消息变信号，再由信号还原成消息的运算称为编码。

编码的数学本质是一种映射，其核心问题是码元的设计与选择。

9．信息的传递过程可归结为：首先由信源发出消息（原始消息），由编码将原始消息变为信号，并进入信道成为信道的输入信号（简称输入信号，或入口信号〕，输入信号经信道的编码 通过信道，经过信道的传送，到达另一端，经过信道译码形成输出信号或出口信号，再经过信源译码运算把输出信号变为消息，这种消息是原始消息的还原；所以又称还原消息，还原消息最终由接收者接收。

10．由于干扰的存在，信道的输出信号可能与输入信号不同；从而形成还原消息与原始消息的不同，这种现象称为通信误差，是通信系统中需要克服的。

通信误差的克服一般通过硬件与软件两个途径来解决。

软件的改进就是信道编码方式的改进。

11．为实现有效编码，在编码理论中同时从两方面来进行考虑 首先从信源角度考虑，在不丢失信源的原始信息条件下对信源的数据量尽可能精简压缩，这就是信源编码 问题。

另一方面则从信道角度考虑，主要目的是克服误差干扰，使数据实现无误差或误差很小的传递，这就是 信道编码 问题。

12．香农信息论的主要目的是讨论编码的可行性问题。

讨论在什么样的条件下信源在信道中的可通过，或有效编码的存在性问题。

信源编码定理研究的是 只要编码的码率大于信源的熵，则必存在信源编译码方案，使当 被编码的信源分组长度趋于无穷时，译码误差概率可以任意小，信道编码定理研究的是 如果编码速率R 小于信道容量，则对任意小的正数，存在码率为 R 的信道码， 只要分组长度充分大，就可以使误差概率任意小。

13．信源编码问题分有失真与无失真编码问题。

所谓无失真编码问题就是要求编码运算能够 百分之百 恢复原来的数据信息，经编码运算后不丢失任何信息；而有失真编码运算问题就是允许编码运算有一定的误差发生，在允许误差的条件下，寻找信源的最小 “信号体积” 。

14．无失真信源编码的主要类型分等（或定）长码与变长码两种。

15．使用定长码的主要优点是编码运算简单，它可以依据消息与信号的长度自动区分各自所对应的字符。

但它的缺点是 编码利用率低。

16．无论是等长码还是变长码，它们的编码原则都必须具有可还原性 。

17．所谓通用码就是针对以上问题，在不知道信源的 概率分布的情况下，对随时出现的数据序列直接进行编码。

常用的通用码有LZW 码与YK 码。

18．哈夫曼（Huffman ）码与算术码是两种重要的 变长码 。

19．):()|(),|(),,(),(),(Y X I X Y H Y X H Y X H Y H X H 与 的相互关系可用集合之间的相互关系来表示：20．无记忆离散信源序列的最小可达速率就是信源的 香农熵（或熵率）。

但这是在∞→n 极限意义下的结论。

实际应用时，应该在给定有限的n 值的意义下，建立尽可能好的编码方案。

二、判断题（10分）：（对的在括号内打√，错的在括号内打⨯）（1）C ={0，10，00，01}是即时码； （ ）{}0,10,110,1110,10110,1101C =是唯一可译码；（ ） （3）C ={1，01，001，0001}是即时码； （ ） （4）C ={0，100，101，110，111，011}是唯一可译码； （ ） （5）信源定长码的编码问题是求最大可达速率； （ ） （6）连续型随机变量的微分熵具有非负性； （ ） （7）全直线上的随机变量，其期望和方差固定，则它的最大熵分布为指数分布； （ ）（8）12345678910113,1,3,4r l l l l l l l l l l l ============的码满足Kraft 不等式； （ ）（9）信道编码和信源编码就是映射关系，都是一一对应的映射关系； （ ） （10）信源输出符号所携带的信息的有效程度即冗余度。

（ ）三、计算题：1． X 与Y 的联合分布给定如下(X H ),(Y X H计算H(X)，H(Y)，H(X,Y),H(X/Y)，I(X,Y)。

解：计算边缘密度根据熵的定义及),(),(),(Y X H Y H X H ,);(),(Y X I Y X H 之间的关系，可得)(5117.095ln 9594ln 94log )(21nat p p X H i i i =--=-=∑=同理，)(6931.0)(nat Y H =)(1996.1log ),(2121nat p p Y X H ij i i ij =-=∑∑==)(5056.0)(),()(nat Y H Y X H Y X H =-=)(0052.0)()();(nat Y X H X H Y X I =-=2．已给信源概率分布S为⎪⎪⎭⎫ ⎝⎛10.010.020.020.040.054321x x x x x 如取码字母表u={0，1}，试进行二元Huffman 编码，并计算平均码长和方差。

45.2==∑ii i l p L ………………（1分）5475.0)(61221=-=∑=i i i L l p σ.……（2分）3．设信源序列为aacdbbaaadc ，对其进行LZW 编码。

4．试构造以下序列的YK 数据压缩编码：n x =0001000101 0111110001 010*******。

5．设随机变量X 的概率密度为⎩⎨⎧≤≤其它010 2x bx ，求(1)常数b ；(2)微分熵h(x)。

6．信源的概率分布p=（0.25，0.25，0.20，0.15，0.15），在D=2时给出算术编码，并计算平均码长。

…………………(8分)L =3.5……… (2分)7．已知LZW 码的码字集合为{}),4(),,5(),,1(),,2(),,1).(,0(),,0(c d a b c a b ，画出码树图，并进行译码，写出信源消息。

8．根据教材110页1）（2）的信道，写出转移概率矩阵，计算信道容量。

9．已知M 信道的信道转移概率矩阵为：⎪⎪⎭⎫ ⎝⎛2.08.002.008.0 计算信道容量。

四、证明题1．证明);()|(),|(),,(),(),(Y X I X Y H Y X H Y X H Y H X H 与之间的链法则。

2．证明以下结论：如果n X 是无记忆信源，记x 是由X 确定的随机变量，nL 是nX的最优不等长编码的平均长度，那么不等式：)(x H ≤nL n≤)(x H +n1成立，其中)(x H 是X的熵。

3．证明：二进对称信道的信道容量为())1log()1(log 1εεεε-----=C 。

4．设Z Y X ,,是三个离散型随机变量，根据相关的定义证明下面关系式成立),()()(),,(Z Y X H Z Y H Z H Z Y X H ++=。

5．设离散型随机变量X 的分布为)(x p ，当1→r 时，r 阶熵的极限为香农熵，即[]()1,0),()(log 11lim)(lim 11≠>=∑-=∈→→r r X H x p r X H rXx r r r。