信息论与编码复习课

1、“信息论与编码”复习1消息、信号、信息的含义、定义及区别。信息是指各个事物运动的状态及状态变化的方式。消息是指包含信息的语言，文字和图像等。信号是消息的物理体现。消息是信息的数学载体、信号是信息的物理载体信号：具体的、物理的消息：具体的、非物理的信息：非具体的、非物理的同一信息，可以采用不同形式的物理量来载荷，也可以采用不同的数学描述方式。同样，同一类型信号或消息也可以代表不同内容的信息。2信息论的起源、历史与发展。n 1924年，Nyquist提出信息传输理论；n 1928年，Hartly提出信息量关系；n 1932年，Morse发明电报编码；n 1946年，柯切尼柯夫提出信号检测理论；n

2、1948年，Shannon提出信息论，“通信中的数学理论”现代信息论的开创性的权威论文，为信息论的创立作出了独特的贡献。3通信系统的物理模型（主要框图），各单元（方框）的主要功能及要解决的主要问题。信源的核心问题是它包含的信息到底有多少，怎样将信息定量地表示出来，即如何确定信息量。信宿需要研究的问题是能收到或提取多少信息。信道的问题主要是它能够传送多少信息，即信道容量的多少。4通信的目的？要解决的最基本问题？通信有效性的概念。提高通信有效性的最根本途径？通信可靠性的概念。提高通信可靠性的最根本途径？通信安全性的概念，提高通信安全性的最根本途径？通信系统的性能指标主要是有效性，可靠性，安全性和经

3、济性。通信系统优化就是使这些指标达到最佳。从提高通信系统的有效性意义上说，信源编码器的主要指标是它的编码效率，即理论上所需的码率与实际达到的码率之比。提高通信有效性的最根本途径是信源编码。减少冗余。提高可靠性：信道编码。增加冗余。提高安全性：加密编码。7随机事件的不确定度和它的自信息量之间的关系及区别？单符号离散信源的数学模型，自信息量、条件自信息量、联合自信息量的含义？信源符号不确定度：具有某种概率的信源符号在发出之前，存在不确定度，不确定度表征该符号的特性。符号的不确定度在数量上等于它的自信息量，两者的单位相同，但含义不同：不确定度是信源符号固有的，不管符号是否发出；自信息量是信源符号发出

4、后给予收信者的；为了消除该符号的不确定度，接受者需要获得信息量。自信息量条件自信息量：联合自信息量：8信息量的性质？含义？分别从输入端、输出端和系统总体来理解互信息量的含义。自信息量指的是该符号出现后，提供给收信者的信息量。9. 各种熵（信源熵，条件熵，联合熵（共熵），等）的含义及其关系。信源熵：条件熵：疑义度： 噪声熵：联合熵：11. 平均互信息量的定义及物理意义？疑义度及噪声熵？12. 平均互信息量的性质及理解？17. 信源的种类（详细分类）？各举出几个例子。按时间和幅度分类： 离散信源 单符号离散信源文字，数字，数据等 离散序列信源连续信源 连续幅度信源话音，图像，图形等 随机波形信源按

5、符号之间的关系： 无记忆信源 发出单个符号的无记忆信源 发出符号序列的无记忆信源有记忆信源 发出符号序列的有记忆信源 发出符号序列的马尔可夫信源20. 信源的冗余度的定义和含义？为什么有些信源有冗余度？冗余度的计算。冗余度，表示给定信源在实际发出消息时所包含的多余信息。它来自两个方面，一是信源符号间的相关性；二是信源符号分布的不均匀性.29. 信道的数学模型和分类？30. 信息传输速率R的定义？信道转移概率、信道矩阵和信道容量C的定义？几种离散无噪信道的C？31. 强对称，对称，准对称信道的含义及其C？式中，m为信道输出符号集中符号的数目。强对称信道：或：32. 离散信道容量的一般计算方法及其

6、步骤？36. 什么是最佳编码？说出Shannon、 Fano和Huffman编码的基本方法和主要特点。37. 理解Huffman编码是最佳编码？40.简要说明下面几种译码准则：（1）最优译码准则；（2）最大似然译码准则BSC信道的最大似然译码可以简化为信道的最大似然译码可以简化为最最小汉明距离译码小汉明距离译码。41.信源与信道达到匹配的含义以及如何实现？信道剩余度的概念及计算？42.失真函数、平均失真度的定义及其含义？失真函数定义：推广-L长序列：平均失真度：43.信息率失真函数R(D)的定义、性质及其含义？R(D)与C的比较？对于给定信源，在平均失真不超过失真限度D的条件下，信息率容许压缩

7、的最小值为R（D）。如果选取对压缩更为有利的编码方案，则压缩的效果可能更好。但是一旦超过最小互信息这个极限值，就是R(D)的数值，那么失真就要超过失真限度。如果需要压缩的信息率更大，则可容忍的平均失真就要大。信息率失真函数R（D）性质：44.Shannon第三定理及其含义？50.汉明距离和汉明重量的定义？错误图样的定义？随机错误和突发错误的定义？52.线性分组码的定义、构造、性质？ 三、判断（每题1分）（50道）1、 必然事件和不可能事件的自信息量都是0 。错2、 自信息量是的单调递减函数。对3、 单符号离散信源的自信息和信源熵都具有非负性。对4、 单符号离散信源的自信息和信源熵都是一个确定值

8、。错5、 单符号离散信源的联合自信息量和条件自信息量都是非负的和单调递减的。对6、 自信息量、条件自信息量和联合自信息量之间有如下关系： 对7、 自信息量、条件自信息量和互信息量之间有如下关系： 对8、 当随即变量X和Y相互独立时，条件熵等于信源熵。对9、 当随即变量X和Y相互独立时，I（X；Y）=H（X） 。错10、信源熵具有严格的下凸性。错11、平均互信息量I（X；Y）对于信源概率分布p（xi）和条件概率分布p（yj/xi）都具有凸函数性。 对12、m阶马尔可夫信源和消息长度为m的有记忆信源，其所含符号的依赖关系相同。 错13、利用状态极限概率和状态一步转移概率来求m阶马尔可夫信源的极限熵

9、。 对14、N维统计独立均匀分布连续信源的熵是N维区域体积的对数。 对15、一维高斯分布的连续信源，其信源熵只与其均值和方差有关。 错16、连续信源和离散信源的熵都具有非负性。 错17、连续信源和离散信源都具有可加性。 对18、连续信源和离散信源的平均互信息都具有非负性。 对19、定长编码的效率一般小于不定长编码的效率。 对20、若对一离散信源（熵为H（X）进行二进制无失真编码，设定长码子长度为K，变长码子平均长度为，一般>K。 错21、信道容量C是I（X；Y）关于p（xi）的条件极大值。 对22、离散无噪信道的信道容量等于log2n，其中n是信源X的消息个数。 错23、对于准对称信道，

10、当时，可达到信道容量C。错24、多用户信道的信道容量不能用一个数来代表。 对25、多用户信道的信道容量不能用一个数来代表，但信道的信息率可以用一个数来表示。错26、高斯加性信道的信道容量只与信道的信噪有关。 对27、信道无失真传递信息的条件是信息率小于信道容量。对28、最大信息传输速率，即：选择某一信源的概率分布（p（xi），使信道所能传送的信息率的最大值。 错29、对于具有归并性能的无燥信道，当信源等概率分布时（p（xi）=1/n），达到信道容量。 错30、求解率失真函数的问题，即：在给定失真度的情况下，求信息率的极小值。对31、信源的消息通过信道传输后的误差或失真越大，信宿收到消息后对信源

11、存在的不确定性就越小，获得的信息量就越小。 错32、当p（xi）、p（yj/xi）和d（xi，yj）给定后，平均失真度是一个随即变量。 错33、率失真函数对允许的平均失真度具有上凸性。对34、率失真函数没有最大值。 错35、率失真函数的最小值是0 。对36、率失真函数的值与信源的输入概率无关。错37、信源编码是提高通信有效性为目的的编码。 对38、信源编码通常是通过压缩信源的冗余度来实现的。 对39、离散信源或数字信号的信源编码的理论基础是限失真信源编码定理。 错40、一般情况下，哈夫曼编码的效率大于香农编码和费诺编码。 对41、在编m（m>2）进制的哈夫曼码时，要考虑是否需要增加概率为

12、0的码字，以使平均码长最短。 对42、游程序列的熵（“0”游程序列的熵与“1”游程序列的熵的和）大于等于原二元序列的熵。 错43、在游程编码过程中，“0”游程和“1”游程应分别编码，因此，它们的码字不能重复。 错44、L-D编码适合于冗余位较多和较少的情况，否则，不但不能压缩码率，反而使其扩张。 对45、狭义的信道编码既是指：信道的检、纠错编码。 对46、对于BSC信道，信道编码应当是一对一的编码，因此，消息m的长度等于码字c的长度。 错47、等重码和奇（偶）校验码都可以检出全部的奇数位错。 对48、汉明码是一种线性分组码。对49、循环码也是一种线性分组码。 对50、卷积码是一种特殊的线性分组

13、码。 错四、简答（每题4分）（20道）1、 信息的主要特征有哪些？（4）2、 信息的重要性质有哪些？（4）3、 简述几种信息分类的准则和方法。（5）4、 信息论研究的内容主要有哪些？（8）5、 简述自信息的性质。（13）6、 简述信源熵的基本性质。（23）7、 简述信源熵、条件熵、联合熵和交互熵之间的关系。（48）8、 信道的分类方法有哪些？（93-94）9、 简述一般离散信道容量的计算步骤。（107）10、简述多用户信道的分类。（115-116）11、简述信道编码定理。（128）12、简述率失真函数的性质。（140-145）13、简述求解一般离散信源率失真函数的步骤。（146-149）14、

14、试比较信道容量与信息率失真函数。（164）15、简述编码的分累及各种编码的目的。（168）16、简述费诺编码的编码步骤。（170）17、简述二元哈夫曼编码的编码步骤。（173）18、简述广义的信道编码的分类及各类编码的作用。（188）19、简述线性分组码的性质。（196）20、简述循环码的系统码构造过程。（221） 信息论基础A复习资料作者 郝仁第一章 概论l 在认识论层次研究信息时，把只考虑到形式因素的部分称为语法信息，把只考虑到含义因素的部分称为语义信息；把只考虑到效用因素的部分称为语用信息。目前，信息论中主要研究语法信息l 归纳起来，香农信息论的研究内容包括：1) 信息熵、信道容量和信息

15、率失真函数2) 无失真信源编码定理、信道编码定理和保真度准则下的信源编码定理3) 信源编码、信道编码理论与方法l 一般认为，一般信息论的研究内容除香农信息论的研究内容外，还包括维纳的微弱信号检测理论：包括噪声理论、信号滤波与预测、统计检测与估计理论、调制理论等。信息科学以信息为研究对象，信息科学以信息运动规律为研究内容，信息运动包括获取、传递、存储、处理和施用等环节。第二章 离散信源及离散熵l 单符号离散信源的数学模型：自信息量：，是无量纲的，一般根据对数的底来定义单位：当对数底为2时，自信息量的单位为比特(bit,binary unit)；对数底为e时，其单位为奈特(nat,nature u

16、nit)；对数底为10时，其单位为哈特(Hart, Hartley) 自信息量性质：I(xi)是随机量；I(xi)是非负值；I(xi)是P(xi)的单调递减函数。l 单符号离散信源的离散熵：，单位是比特/符号(bit/symbol)。离散熵的性质和定理：H(X)的非负性；H(X)的上凸性；最大离散熵定理：l 如果除概率分布相同外，直到N维的各维联合概率分布也都与时间起点无关，即：则称该多符号离散信源为N维离散平稳信源。l N维离散平稳信源的数学模型：l 二维离散平稳信源的离散熵：H(X2/X1 )称为条件熵，是条件信息量在联合概率上的数学期望，H(X1X2)称为联合熵，离散熵H(X1)、 H(

17、X2)称为无条件熵，H2(X1X2)称为平均符号熵且：，l 对于，当N时，平均符号熵取极限值，称之为极限熵，用H表示：l 如果离散平稳信源发出的符号序列中各符号相互独立，则称该信源为离散平稳无记忆信源。N维离散平稳无记忆信源(一维离散平稳信源的N次扩展信源)的数学模型：，其离散熵：信源的平均符号熵：l 如果离散平稳信源发出的符号只与前面已经发出的m(<N)个符号相关，则称该信源为m阶马尔科夫信源。可将m阶马尔科夫信源发出的符号序列看成长度为m+1的一段段符号序列，m阶马尔科夫信源的数学模型：为强调m阶马尔科夫信源的长度特征，一般将其极限熵H记为Hm+1，即：马尔科夫链的各态历经定理：第三

18、章 离散信源无失真编码l 码字的每一个比特携带信息的效率即编码效率：，平均码长一般采用不等长编码，使平均码长接近离散熵，从而在无失真前提下提高编码效率；编码的基本原则是大概率符号元编成短码，小概率符号元编成长码如果所采用的不等长编码使接收端能从码序列中唯一地分割出对应与每一个符号元的码字，则称该不等长编码为单义可译码。单义可译码中，如果能在对应与每一个符号元的码字结束时立即译出的称为即时码，如果要等到对应与下一个符号元的码字才能译出的称为延时码。异前置码：任何一个码字都不是其他码字的前缀m元长度为ki , i=1,2, ,n的异前置码存在的充分必要条件是：，（克拉夫特(Kraft)不等式）l

19、无失真编码定理：（香农第一定理）如果L维离散平稳信源的平均符号熵为HL(X1X2XL)，对信源符号进行m元不等长组编码，一定存在一种无失真编码方法，当L足够大时，使得每个信源符号所对应码字的平均比特数：无失真编码定理从理论上阐明了编码效率：l L时，则极限熵H是一个界限，通常也称为香农界对于L维离散平稳无记忆信源，由于其平均符号熵HL(X1X2XL) =H(X)，故对信源符号进行m元不等长组编码，一定存在一种无失真编码方法，当L足够大时，使得每个信源符号所对应码字的平均比特数：，此时香农界为H(X)。对离散平稳信源进行无失真编码，每个信源符号所对应码字的平均比特数平稳无记忆信源最多， m阶马尔

20、科夫信源次之，一般平稳信源最少。l 二进制香农码的编码步骤如下：1) 将符号元xi按概率进行降序排列2) 令p(x0)=0，计算第j-1个码字的累加概率：3) 确定第i个码字的码长ki，满足下列不等式：4) 将pa(xj)用二进制表示，取小数点后ki位作为符号元xi的码字。l 哈夫曼(Huffman)编码1) 将符号元按概率进行降序排列2) 为概率最小的符号元分配一个码元1，概率次小的符号元分配一个码元03) 将概率最小的两个符号元合并成一个新的符号元，用两者概率之和作为该新符号元的概率；4) 重复以上三个步骤，直到最后合并出一个以1为概率的符号元哈弗曼码有两种排列方式，分前置和后置。采用不同

21、排列方法编出的哈夫曼码，其码字和码长可能完全不相同，但平均码长一定是相等的，因此编码效率不会因排列方法而改变。但放在前面可以使短码得到充分利用第四章 离散信道及信道容量l 符号离散信道的数学模型可表示为：l 互信息量在有噪信道的情况下，将信源发出xi 而信宿接收到yj所包含的信息量用I(yj;xi )来表示并将其称为xi对yj的互信息量，则互信息量的定义为：I(yj/xi )称为条件信息量，表示信道给出的“信息”。互信息量的性质：I(yj;xi )是随机量，I(yj;xi )可为正值也可为负值，I(yj;xi )具有对称性l 单符号离散信道的平均互信息量：，条件熵H(Y/X)是信道所给出的平均

22、信息量，通常称为噪声熵，条件熵H(X/Y)也是信道所给出的平均“信息”量，通常称为损失熵，也称为信道疑义度l 平均互信息量的性质和定理：1) I(Y;X)的对称性2) I(Y;X)的非负性3) I(Y;X)的极值性： 4) I(Y;X)的凸函数性当信道固定时，I(Y;X)是信源概率分布P(X)的上凸函数；当信源固定时，I(Y;X)是信道转移概率分布P(Y/X)的下凸函数5) 数据处理定理： 一个信息传递并进行数据处理的问题可看成是一个由串联信道进行信息传递的问题l 单符号离散信道的信道容量由于平均互信息量反映的是每传输一个符号在信道中流通的平均信息量，从这个意义上，可以将其理解为信道的信息传输

23、率(不是信息传输速率！)，即。定义最大的信息传输率为信道容量，即：。定义最大信息传输速率为：l 信道容量的计算步骤 l 均匀信道和对称信道的信道容量，则称该信道为均匀信道均匀信道的信息传输率可达最大，其信道容量为：l 对称信道和对称信道的信道容量既是行可排列的，又是列可排列的，则称该矩阵所表示的信道为对称信道则称该信道为对称信道如果每一行都是同一集合中诸元素的不同排列，则称该矩阵为行可排列的；如果每一列都是同一集合中诸元素的不同排列，则称该矩阵为列可排列的均匀信道的信息传输率可达最大，其信道容量为：l 离散无记忆信道及其信道容量对应于多符号离散信源和多符号离散信宿的信道为多符号离散信道，可表示

24、为：当信源和信宿均为平稳无记忆时，信道矩阵中的条件概率：该信道矩阵表示的多符号离散信道称为离散无记忆信道(DMC, Discrete Memoryless Channel)。可称其为L次扩展信道如果记一维离散无记忆信道的信道容量为C，则其L次扩展信道的信道容量为：第五章 离散信道编码l 信道编码定理译码规则的设计依据的是最小错误概率准则。为了降低错误概率，可以考虑重复发送，如重复三次，即将x1编码为a1=x1x1x1，x2编码为a2=x2x2x2，称为3重复码香农第二定理：对于离散无记忆信道，如其信道容量为C，只要信息传输率R<C，一定存在一种编码，当L足够大时，使得译码错误概率Pe&l

25、t; ，其中为任意给定的小正数。该定理从理论上证明了译码错误概率任意小的理想纠错编码的存在性信道编码定理也指出，信道容量C是一个界限，如果信息传输率超过这个界限一定会出错l 汉明距离与线性分组码线性分组码通常用于前向纠错，可表示为(n,k)，其中n为码字长度，k为信息位长度，从而校验位长度为n-k在m(=2k)个码字构成的码中，两个长度为n的码字之间的汉明距离(码距)是指两个码字对应位置上不同码元的个数；对于二元码，码距可表示为：长度为n的码字的汉明重量(码重)是指码字中非零码元的个数；对于二元码，码重可表示为：对于二元码，两个长度为n的码字之间的码距可用码重表示：线性分组码(n,k)能检e个

26、错误并能纠t个错误的充要条件是：最简单的能检1个错误并能纠1个错误的线性分组码(n,k)的将错误序列E的随机结果ei称为错误图案，当eik=1时，表示第i个码字的第k位在传输中出现错误。最简单的能检1个错误并能纠1个错误的线性分组码(n,k)的错误图案为0001，0010，0100，1000l (7,4)汉明码设码字为：，其中为信息位，长度为k=4，为校验位，长度为n-k=3(7,4)汉明码的编码由生成矩阵产生：(7,4)汉明码的最小距离：由线性分组码(n,k)能检e个错误并能纠t个错误的充要条件，(7,4)汉明码只能检出并纠正1个错误l第七章 信息率失真理论l 离散信源的信息率失真函数总能找

27、到一种信道转移概率分布，使信息传输率最小定义非负函数d(xi,yj) i=1,2, ,n; j=1,2, ,m为失真度，称全部n×m个失真度组成的矩阵为失真矩阵：常用的失真矩阵：，当=1时，称为汉明失真矩阵。称为平方误差失真度。平均失真度：保真度准则：如果给定的允许失真为D，则称为保真度准则。定义保真度准则下的最小信息传输率为信息率失真函数：信息率失真函数的性质和定义域：R(D)具有非负性，R(D)是D的下凸函数，R(D)是D单调递减连续函数信息率失真函数的定义域：，特别地，当D =Dmin=0，即不允许任何失真时R(D)=H(X)l 信息率失真函数的参量表达式信道转移概率分布的n个

28、约束条件是，。平均失真度的约束条件是：。信息率失真函数的计算步骤为： 其中，且S < 0及l 等概率信源的信息率失真函数当p=0.5，即二元等概率信源时的信息率失真函数：n元等概率信源，其信息率失真函数：l 连续信源的信息率失真函数定义随机变量X、Y之间的失真函数为非负函数d(x,y)，则平均失真度：记实验信道的集合：。定义信息率失真函数：，其中l 高斯信源的信息率失真函数平均失真度Y=y条件下的条件熵：信道疑义度：在满足保真度准则的条件下保真度准则下的信源编码定理（香农第三定理）：序列长度为L的离散平稳无记忆信源，信息率失真函数为R(D)，对于任意允许失真D和任意小的数>0，只要

29、信息传输率R>R(D)，总可以找到一种编码，使得当L足够长时，译码后的平均失真度，练习21题 1从大量统计资料知道，男性中红绿色盲的发病率为7，女性发病率为0.5，如果你问一位男同志：“你是否是红绿色盲？”他的回答可能是“是”，可能是“否”，问这二个答案中各含多少信息量？平均每个回答中含有多少信息量？如果你问一位女同志，则答案中含有的平均自信息量是多少？2如果你在不知道今天是星期几的情况下问你的朋友“明天是星期几？”则答案中含有多少信息量？如果你在已知今天是星期四的情况下提出同样的问题，则答案中你能获得多少信息量（假设已知星期一至星期日的排序） 3地区的女孩中有25是大学生，在女大学生中

30、有75是身高1.6米以上的，而女孩中身高1.6米以上的占半数一半。假如我们得知“身高1.6米以上的某女孩是大学生”的消息，问获得多少信息量？ 4信源求这信源的熵，并解释为什么，不满足信源熵的极值性。 5设二元对称信道的传递矩阵为(1) 若P(0) = 3/4, P(1) = 1/4，求H(X), H(X/Y), H(Y/X)和I(X;Y)；(2) 求该信道的信道容量及其达到信道容量时的输入概率分布； 6设有一批电阻，按阻值分70%是2K，30%是5 K；按瓦分64%是0.125W，其余是0.25W。现已知2 K阻值的电阻中80%是0.125W，问通过测量阻值可以得到的关于瓦数的平均信息量是多少？ 7黑白气象传真图的消息只有黑色和白色两种，即信源X黑，白，设黑色出现的概率为P（黑）0.3，白色的出现概率为P（白）0.7。（1） 假设图上黑白消息出现前后没有关联，求熵H（X）。（2） 假设消息前后有关联，其依赖关系为P（白|白）0.9，P（黑|白）0.1，P（白|黑）0.2，P（黑|黑）0.8，求此一阶马尔可夫信源的熵H2。（3）分别求出上述两种信源的剩余度，并比较H（X）和H2的大小，并说明其物理意义。 8求图中信道的信道容量及其最