信息论与编码总复习.ppt

《信息论与编码总复习.ppt》由会员分享，可在线阅读，更多相关《信息论与编码总复习.ppt（78页珍藏版）》请在三一办公上搜索。

1、第1章绪论,重点掌握信息的特征信息、消息、信号的联系和区别通信系统的物理模型 一般了解信息论理论的形成和发展过程信息论的研究内容,信息的特征,信息的基本概念在于它的不确定性，任何已确定的事物都不含信息。接收者在收到信息之前，对它的内容是不知道的，所以信息是新知识、新内容信息是能使认识主体对某一事物的未知性或不确定性减少的有用知识信息可以产生，也可以消失，同时信息可以被携带、贮存及处理信息是可以量度的，信息量有多少的差别,消息、信号和信息,信号最具体，它是一物理量，可测量、可显示、可描述，同时它又是载荷信息的实体消息是具体的、非物理的，可描述为语言文字、符号、数据、图片，能够被感觉到，同时它是信

2、息的载荷体，是信息论中主要描述形式信息是抽象的、非物理的哲学层表达,信息的物理层表达,信息的数学层表达,通信系统模型简介,加密密钥,解密密钥,第2章信源及信源熵,重点掌握信源的分类和数学描述自信息量、互信息离散信源熵离散序列信源的熵熵的性质一般了解连续信源熵冗余度,信源分类,信源的数学描述,单符号无记忆信源用一维离散型随机变量X来描述这些信息的输出。数学模型符号序列无记忆信源很多实际信源输出的消息往往是由一系列符号组成，这种用每次发出1组含2个以上符号的符号序列来代表一个消息的信源叫做发出符号序列的信源。设信源输出的随机序列为X，序列中的变量,信源的数学描述,有记忆信源的联合概率表示比较复杂，

3、需要引入条件概率来反映信源发出符号序列内各个符号之间的记忆特征。,信源的数学描述,一阶马尔可夫信源,m阶马尔可夫信源,自信息量,随机事件的自信息量定义为其概率对数的负值，即,I(xi)含义:当事件xi发生以前，表示事件xi发生的不确定性当事件xi发生以后，表示事件xi所含有的信息量,自信息量的特性,I(xi)是非负值当p(xi)=1时，I(xi)=0当p(xi)=0时，I(xi)=I(xi)是先验概率p(xi)的单调递减函数，即 当p(x1)p(x2)时，I(x1)I(x2)两个独立事件的联合信息量等于它们分别的信息量之和。即：统计独立信源的信息量等于它们分别的信息量之和。,联合自信息量,两个

4、消息xi，yj同时出现的联合自信息量 当xi,yj相互独立时，有p(xi yj)=p(xi)p(yj)，那么就有 I(xi yj)=I(xi)+I(yj)。xi yj所包含的不确定度在数值上也等于它们的自信息量。,条件自信息量,在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi/yj)，则它的条件自信息量定义为条件概率对数的负值：在给定yj条件下，随机事件xi所包含的不确定度在数值上与条件自信息量相同，但两者含义不同。联合自信息量、条件自信息量和自信息量,信源熵,离散信源熵为信源中各个符号不确定度的数学期望信源熵的物理含义表示信源输出前信源的平均不确定性表示信源输出后每个符号所携带的

5、平均信息量,条件熵,在给定yj条件下，xi的条件自信息量为I(xi/yj)，X集合的条件熵在给定Y（即各个yj）条件下，X集合的条件熵在给定X（即各个xi）条件下，Y集合的条件熵条件熵是在联合符号集合XY上的条件自信息量的联合概率加权统计平均值。条件熵H(X/Y)表示已知Y后，X的不确定度。,联合熵,联合熵是联合符号集合 XY上的每个元素对xiyj的自信息量的概率加权统计平均值联合熵H(XY)表示X和Y同时发生的不确定度。联合熵、信源熵和条件熵之间的关系,互信息,定义：xi的后验概率与先验概率比值的对数事件xi是否发生具有不确定性，用I(xi)度量。接收到符号yj后，事件xi是否发生仍保留有一

6、定的不确定性，用I(xi/yj)度量。接收到某消息yj后获得的关于事件xi的信息量，用I(xi;yj)表示。,平均互信息,互信息量 I(xi;yj)在X集合上的统计平均值为 I(X;yj)在Y集合上的概率加权统计平均值,平均互信息（量）,平均互信息量的物理意义,H(X/Y)：信道疑义度，损失熵信源符号通过有噪信道传输后引起的信息量损失。信源X的熵等于接收到的信息量加损失掉的信息量。H(Y/X)：噪声熵，散布度它反映了信道中噪声源的不确定性。输出端信源Y的熵H(Y)等于接收到关于X的信息量I(X;Y)加上H(Y/X)，这完全是由信道中噪声引起的。,熵的性质,非负性H(X)H(x1,x2,xn)0

7、等号在p(xi)=1时成立对称性H(x1,x2,xn)H(x2,x1,xn)熵函数只与随机变量的总体结构有关确定性H(0,1)H(1,0,0,0)0只要信源符号集中有一个符号的出现概率为1，信源熵就等于零,熵的性质,香农辅助定理对于P(p1,p2,pn)和Q(q1,q2,qn)对任意概率分布pi，它对其他概率分布qi的自信息量取数学期望时，必不小于pi本身的熵最大熵定理离散无记忆信源输出M个不同的信息符号，当且仅当各个符号出现概率时（即等概率分布），熵最大,互信息量与熵,离散无记忆信源的序列熵,设信源输出的随机序列为X=(X1X2XlXL)序列中的变量Xlx1,x2,xn信源的序列熵可以表示为

8、信源序列中，平均每个符号的熵为离散无记忆信源平均每个符号的符号熵HL(X)等于单个符号信源的符号熵H(X),无记忆,无记忆、平稳,离散有记忆信源的序列熵,若信源输出一个L长序列，则信源的序列熵为平均每个符号的熵为信源无记忆时满足平稳时,离散平稳信源,结论1：H(XL/XL-1)是L的单调非增函数结论2：HL(X)H(XL/XL-1)结论3：HL(X)是L的单调非增函数结论4：当L时，H(X)称为极限熵,马尔可夫信源,若一个信源满足下面两个条件，则称为马尔可夫信源：某一时刻信源输出符号的概率只与当前所处的状态有关，而与以前的状态无关；信源的下一个状态由当前状态和下一刻的输出符号唯一确定。符号条件

9、概率信源在某一时刻出现符号xj的概率与信源此时所处的状态si有关，用条件概率表示为p(xj/si)。状态转移概率当信源符号xj出现后，信源所处的状态将发生变化，并转入一个新的状态。这种状态的转移可用状态转移概率p(sj/si)表示。,状态转移图（香农线图）,齐次马尔可夫链可以用其状态转移图（香农线图）表示每个圆圈代表一种状态 状态之间的有向线代表从某一状态向另一状态的转移有向线一侧的符号和数字分别代表发出的符号和条件概率,p(x1/s2)=0.8,p(s2/s2)=0.8,稳定的马尔可夫信源,极限概率Wj一个不可约的、非周期的、状态有限的马尔可夫链，其k步转移概率pij(k)在k时趋于一个和初

10、始状态无关的概率，即不论起始状态如何，这种马氏链都可以最后达到稳定，即所有变量Xk的概率分布均不变。可以用P这一矩阵充分描述稳定的马氏链。平稳分布Wj可用下列方程组求得,马尔可夫信源的熵,M阶马尔可夫信源的极限熵齐次、遍历的马尔可夫信源的熵,处于状态si时符号的平均不确定性,第3章信道与信道容量,重点掌握有干扰无记忆信道的数学描述信道容量的定义对称和准对称DMC信道的信道容量计算香农公式一般了解信道的各种分类无干扰离散信道的信道容量信源和信道的匹配,信道的分类,按信道的用户数量来划分单用户信道、多用户信道按输入/输出之间的关系来划分无反馈信道、反馈信道按信道参数与时间的关系来划分固定参数信道、

11、时变参数信道按信道中的噪声种类来划分随机差错信道、突发差错信道按输入/输出信号在幅度和时间上的取值划分离散信道、连续信道、半离散半连续信道、波形信道,信道模型,根据干扰和记忆性分类无干扰（无噪声）信道有干扰无记忆信道有干扰有记忆信道信道模型信道的输入Xi=a1,a2,an信道的输出Yj=b1,b2,bm信道转移概率矩阵p(Y/X),信道模型,二进制离散信道：BSC信道输入符号X取值0,1输出符号Y取值0,1离散无记忆信道：DMC信道输入符号集X=a1,a2,an输出符号集Y=b1,b2,bm,信道模型,离散输入、连续输出信道输入符号集：X=a1,a2,an输出未经量化，即Y=-,输出特性由离散

12、输入X、连续输出Y以及一组条件概率密度函数 p(y/X=ai)来决定。波形信道输入是模拟波形，输出也是模拟波形连续无记忆信道和连续有记忆信道y(t)x(t)n(t)n(t)代表加性噪声,信道容量的定义,信道传输率R I(X;Y)bit/符号信道中平均每个符号能传送的信息量信息传输速率Rt I(X;Y)/t bit/s信道中单位时间传送的信息量信道容量给定转移概率矩阵P后，平均互信息I(X;Y)是概率矢量Px的上凸函数。I(Px)的极大值就是信道容量。,离散单符号信道,离散单个符号信道,无干扰离散信道,有扰离散信道,对称DMC信道,准对称DMC信道,一般DMC信道,无噪无损信道,无噪有损信道,有

13、噪无损信道,无干扰离散信道,无噪无损信道C=max I(X;Y)=log n无噪有损信道C=max I(X;Y)=max H(Y)有噪无损信道C=max I(X;Y)=max H(X),DMC信道的容量,对称DMC信道的性质对称信道的条件熵H(Y/X)与信道输入符号的概率分布无关。如果信道输入符号等概率分布，则信道输出符号也等概率分布；反之，若信道输出符号等概率分布时，信道输入符号也是等概率分布。当信道输入符号等概率分布时，对称DMC信道达到其信道容量。,DMC信道的容量,准对称DMC信道的容量如果转移概率矩阵P的输入对称而输出不对称，则称该信道是准对称DMC信道。当信道输入符号等概率分布时，

14、准对称DMC信道达到其信道容量C。矩阵分解法：将转移概率矩阵划分成若干个互不相交的对称子矩阵。,DMC信道的容量,一般DMC信道的容量以输入符号概率矢量Px为自变量的函数I(Px)的极大值，即信道容量。为了使I(X;Y)最大化，即求取信道容量的值，输入概率集p(xi)必须满足的充分必要条件是：I(xi;Y)C，对于所有满足p(xi)0条件的iI(xi;Y)C，对于所有满足p(xi)0条件的i,每一个概率不为0的输入符号对输出提供相同的互信息,离散序列信道及其容量,X=(X1,X2,XL),Xl=a1,a2,an,Y=(Y1,Y2,YL),Yl=b1,b2,bm,独立、无记忆、平稳离散序列信道的

15、信道容量为：,无记忆离散序列信道的转移概率为：,连续信道,连续单符号加性信道信道的输入和输出都是取值连续的一维随机变量，加入信道的噪声是均值为零、方差为2的加性高斯噪声。多维无记忆加性连续信道可等价成L个独立的并联高斯加性信道注水法：噪声小的子信道分配到的输入功率大，传输的比特数多。受加性高斯白噪声干扰的带限波形信道输入x(t)、输出y(t)和噪声n(t)：模拟波形,香农公式,香农公式W：频带宽度，简称带宽SNR(信噪比)：表示信号功率与噪声功率的比值加性白噪声的功率谱密度为N0/2Pav：信号的平均功率香农限每传输1比特信息所需的能量。当归一化的信噪比小于香农限（-1.6dB）时，归一化信道

16、容量为零，即信道完全丧失通信能力。,香农公式的讨论,带宽W一定时，信道容量C 随信噪比SNR的增加而单调增加，因此增大信号功率、减小信道噪声可以增加信道容量。信道容量C一定时，带宽W增大，信噪比SNR可降低，即二者可以互换。如果输入信号功率PS固定，信道容量C 随带宽W的增加而增加。但到一定阶段后，增加变得缓慢。,信源与信道的匹配,符号匹配信源输出的符号必须是信道能够传送的符号，这是实现信息传输的必要条件。信息匹配对于某一信道，只有当输入符号的概率分布满足一定条件时，才能达到其信道容量。信道冗余度信道绝对冗余度CI(X;Y)信道相对冗余度,第4章信息率失真函数,重点掌握失真函数、平均失真保真度

17、准则信息率失真函数的定义域信息率失真函数与信道容量的比较一般了解信息率失真函数的性质连续信源的平均失真,失真函数,单符号失真函数定义为：将所有的d(xi,yj)排列起来，用矩阵表示为,d 称为失真矩阵,失真函数,如果假定离散信源输出符号序列X=(X1X2Xl XL),XlA=a1,an，其中L长符号序列xi=(xi1xi2xiL)，经信源编码后输出符号序列Y=(Y1Y2YlYL)，YlB=b1,bm，其中L长符号序列yj=(yj1yj2yjL)，序列失真函数定义为,式中，d(xil,yjl)表示信源输出符号序列xi的第l个符号和编码输出符号序列yj的第l个符号之间的失真函数,信源序列的失真度等

18、于序列中对应单个符号的失真度之和,平均失真,将失真函数的数学期望或统计平均值称为平均失真。失真函数d(xi,yj)描述某个信源符号通过传输后失真的大小。对于不同的信源符号和不同的接收符号，其值是不同的。平均失真：平均失真对信源和信道进行的统计平均。描述某一信源在某一试验信道传输下的失真大小，是从总体上描述整个系统的失真情况。,平均失真,L维信源符号序列的平均失真度当信源与信道无记忆时，信源符号平均失真度（平均每个符号的平均失真度）,表示信源符号序列的第l 个符号的平均失真,保真度准则,保真度准则平均失真度不大于允许的失真D允许信道D允许的试验信道，即满足保真度准则的试验信道。满足保真度准则的所

19、有试验信道，即转移概率分布p(yj/xi)，构成了一个信道集合,信息率失真函数,信息率失真函数R(D)限定失真为D的条件下，信源输出的最小信息率。R(D)的定义域率失真函数的定义域问题就是在信源和失真函数已知的情况下，讨论允许平均失真度D的最小和最大取值问题，即Dmin,DmaxDmin的计算Dmax的计算,信息率失真函数的性质,R(D)是非负的实数，0R(D)H(X)定义域为0DminDDmax 当DDmax时，R(D)0 R(D)是关于D的下凸函数R(D)在定义域内是失真度D的U型下凸函数。R(D)在定义域内是关于D的连续函数。R(D)的单调递减性容许的失真度越大，所要求的信息率越小。,率

20、失真函数和信道容量的比较,平均互信息 I(X;Y)信源的概率分布 p(xi)的上凸函数。信道传递概率 p(yj/xi)的下凸函数。信道容量信息率失真函数,信道固定,输入概率分布固定,率失真函数和信道容量的比较,第5章信源编码,重点掌握分组码的属性唯一可译码的判断方法信源编码定理香农编码、费诺编码、哈夫曼编码一般了解编码的术语游程编码、算术编码,分组码属性,码,非分组码 分组码,奇异码 非奇异码,非唯一可译码 唯一可译码,非即时码 即时码（非延长码）,码树,中间节点不安排码字，只在终端节点安排码字每个终端节点对应的码字由从根节点出发到终端节点走过的路径上所对应的符号组成当第i阶的节点作为终端节点

21、，且分配码字，则码字的码长为i按树图法构成的码一定满足即时码的定义树码的各个分支都延伸到最后一级端点，则称为满树，否则为非满树 满树码是定长码，非满树码是变长码,克劳夫特不等式,唯一可译码存在的充分和必要条件为：各码字的长度Ki 应满足下式。m是进制数，n是信源符号数注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据。,唯一可译码的判断法,将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。集合F的构成方法首先观察码C中最短的码字是否是其它码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字

22、的前缀（或者某些码字是这些尾随后缀的前缀），再将这些尾随后缀产生的新的尾随后缀列出。依此下去，直到没有一个尾随后缀是码字的前缀为止。按照上述步骤将次短码字、等等所有码字可能产生的尾随后缀全部列出。最终得到码C的所有可能的尾随后缀的集合F。,唯一可译码判断方法和步骤,首先，观察是否是奇异码。若是，一定不是唯一可译码。其次，计算码长是否满足Kraft不等式。若不满足，一定不是唯一可译码。按照树图的构造法则，若能将码画成码树则是即时码，也就是唯一可译码。按唯一可译码判断法进行判断。,只有唯一可译码判断法能确切判断是否是唯一可译码,无失真信源编码,设信源符号序列的长度为L变换成由KL个符号组成的码序列

23、（码字）变换要求能够无失真或无差错地从Y 恢复X，也就是能正确地进行反变换或译码传送Y 时所需要的信息率最小,定长编码定理,定长编码定理：由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2XlXL，可用KL个符号Y1,Y2,Yk,YKL（每个符号有m种可能值）进行定长编码。对任意0，0，只要则当L足够大时，必可使译码差错小于；反之，当时，译码差错一定是有限值，而当L足够大时，译码几乎必定出错。,编码效率,差错概率当信源序列长度L满足时，就能达到差错率要求。编码效率最佳编码效率为,变长编码定理,单个符号变长编码定理若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制

24、码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式,变长编码定理,离散平稳无记忆序列变长编码定理对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率 满足不等式其中，为任意小正数。,香农编码步骤,将信源消息符号按其概率从大到小排列确定满足下列不等式的整数码长Ki令P1=0，计算第i个消息的累加概率将累加概率Pi变换成二进制数，取小数点后Ki位为该消息的码字,费诺编码方法,费诺编码属于概率匹配编码，不是最佳的编码方法。编码过程如下：将信源消息符号按其出现的概率依次排列p(x1)p(x2)p(xn)按编码进制数将概率分组，使每组概率尽可能接

25、近或相等，并为每一组分配一位码元。如编二进制码就分成两组，编m进制码就分成m组。将每一分组再按同样原则划分，重复步骤2，直至概率不再可分为止。信源符号所对应的码字即为费诺码。,哈夫曼编码方法,哈夫曼编码的步骤将信源消息符号按其出现的概率大小依次排列 p(x1)p(x2)p(xn)取两个概率最小的符号分别配以0和1，并将这两个概率相加作为一个新符号的概率，与未分配码元的符号重新排队。对重排后的两个概率最小符号重复步骤2的过程。继续上述过程，直到最后两个符号配以0和1为止。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。,三种编码的比较,香农码、费诺码、哈夫曼码都考虑了信源

26、的统计特性，经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现对信源的压缩。香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高。费诺码和哈夫曼码的编码方法都不惟一。费诺码比较适合于对分组概率相等或接近的信源编码。哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。,限失真信源编码定理,设离散无记忆信源X的信息率失真函数为R(D)当信息率 RR(D)时，只要信源序列长度 L 足够长，一定存在一种编码方法，其译码失真小于或等于 D，为任意小的正数。反之，若RR(D)，则无论采用什么样的编码方法，其译码失真必大于

27、D。如果是二元信源，则对于任意小的0，每一个信源符号的平均码长满足如下公式：,第6章信道编码,重点掌握差错控制相关的基本概念差错控制系统分类检、纠错能力有扰离散信道编码定理一般了解纠错码分类纠错码的基本思路,与差错控制有关的基本概念,汉明重量（码重）：码字中非0码元的个数，用W表示。对于二进制来说，指码字中码元1的数目。汉明距离（码距）：两个等长码字之间对应码元不相同的数目，用D表示。码的最小距离dmin：在某一码集C中，任意两个码字之间汉明距离的最小值称为该码的最小距离，即,最小码距是衡量该码纠错能力的重要依据,与差错控制有关的基本概念,错误图样在二元无记忆N次扩展信道中，差错的形式也可以用

28、二元序列来描述，称为错误图样。设发送码字为C=(c1c2cn)，接收码字为R=(r1r2rn)，两者的差别为分组码：每个码字中增加的r 个校验元只由本组的k个信息元产生，与其他信息组的信息元无关。记为(n,k)卷积码：增加的r个校验元既与本组信息元有关，还与前面L组信息元有关。记为(n,k,L),差错控制系统分类,前向纠错方式（FEC）自动请求重发方式（ARQ）混合纠错（HEC）,译码设备不复杂，对突发错误特别有效,实时性好，适用于单工通信,检错、纠错能力强，译码设备复杂，应用广泛,检错与纠错能力,检错与纠错能力纠错码的检、纠错能力是指能够检测、纠正差错的数目。检错能力纠错能力检、纠错能力将检

29、错和纠错统一考虑，情况会有所变化。要增加检错能力，必须抑制纠错能力。,e dmin1,ed+ec dmin-1,t=INT(dmin-1)/2,有扰离散信道编码定理,若有一离散无记忆平稳信道，其容量为C，输入符号序列长度为N。只要待传送的信息率RC，总可以找到一种编码方法，当N足够长时，使译码错误概率Pe，为任意正数。反之，当RC时，任何编码的Pe0。当N时，Pe1。与信源编码定理类似，香农第二定理只是一个存在性定理，它指出信道容量是一个临界值，只要信息传输率不超过这个临界值，信道就可以几乎无失真地把信息传送过去。,差错控制,差错控制：从公式和概念两条途径来论述差错控制与信道编码的基本原理。途径一：信道编码定理的公式增大C、减小R、增加N途径二：从概念上分析纠错编码的基本原理利用冗余度噪声均化,