信息论与编码总复习

第1章绪论重点掌握信息的特征信息、消息、信号的联系和区别通信系统的物理模型

一般了解信息论理论的形成和发展过程信息论的研究内容

3/30/20251信息的特征信息的基本概念在于它的不确定性，任何已确定的事物都不含信息。接收者在收到信息之前，对它的内容是不知道的，所以信息是新知识、新内容信息是能使认识主体对某一事物的未知性或不确定性减少的有用知识信息可以产生，也可以消失，同时信息可以被携带、贮存及处理信息是可以量度的，信息量有多少的差别3/30/20252消息、信号和信息信号最具体，它是一物理量，可测量、可显示、可描述，同时它又是载荷信息的实体消息是具体的、非物理的，可描述为语言文字、符号、数据、图片，能够被感觉到，同时它是信息的载荷体，是信息论中主要描述形式信息是抽象的、非物理的

哲学层表达信息的物理层表达信息的数学层表达3/30/20253通信系统模型简介信道信源信源编码加密信道编码干扰源信宿信源解码解密信道解码加密密钥解密密钥3/30/20254第2章信源及信源熵重点掌握信源的分类和数学描述自信息量、互信息离散信源熵离散序列信源的熵熵的性质一般了解连续信源熵冗余度3/30/20255信源分类离散信源{离散无记忆信源离散有记忆信源{{发出单个符号的无记忆信源发出符号序列的无记忆信源发出符号序列的有记忆信源发出符号序列的马尔可夫信源3/30/20256信源的数学描述单符号无记忆信源用一维离散型随机变量X来描述这些信息的输出。数学模型符号序列无记忆信源很多实际信源输出的消息往往是由一系列符号组成，这种用每次发出1组含2个以上符号的符号序列来代表一个消息的信源叫做发出符号序列的信源。设信源输出的随机序列为X， 序列中的变量3/30/20257信源的数学描述有记忆信源的联合概率表示比较复杂，需要引入条件概率来反映信源发出符号序列内各个符号之间的记忆特征。3/30/20258信源的数学描述一阶马尔可夫信源m阶马尔可夫信源3/30/20259自信息量随机事件的自信息量定义为其概率对数的负值，即I(xi)

含义:当事件xi发生以前，表示事件xi发生的不确定性当事件xi发生以后，表示事件xi所含有的信息量3/30/202510自信息量的特性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)两个独立事件的联合信息量等于它们分别的信息量之和。即：统计独立信源的信息量等于它们分别的信息量之和。3/30/202511联合自信息量两个消息xi，yj同时出现的联合自信息量当xi,yj相互独立时，有p(xiyj)=p(xi)p(yj)，则就有I(xiyj)=I(xi)+I(yj)。xiyj所包含的不确定度在数值上也等于它们的自信息量。3/30/202512条件自信息量在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi/yj)，则它的条件自信息量定义为条件概率对数的负值：在给定yj条件下，随机事件xi所包含的不确定度在数值上与条件自信息量相同，但两者含义不同。联合自信息量、条件自信息量和自信息量3/30/202513信源熵离散信源熵为信源中各个符号不确定度的数学期望信源熵的物理含义表示信源输出前信源的平均不确定性表示信源输出后每个符号所携带的平均信息量3/30/202514条件熵在给定yj条件下，xi的条件自信息量为I(xi/yj)，X集合的条件熵在给定Y（即各个yj）条件下，X集合的条件熵在给定X（即各个xi）条件下，Y集合的条件熵条件熵是在联合符号集合XY上的条件自信息量的联合概率加权统计平均值。条件熵H(X/Y)表示已知Y后，X的不确定度。3/30/202515联合熵联合熵是联合符号集合XY上的每个元素对xiyj的自信息量的概率加权统计平均值联合熵H(XY)表示X和Y同时发生的不确定度。联合熵、信源熵和条件熵之间的关系3/30/202516互信息定义：xi的后验概率与先验概率比值的对数事件xi是否发生具有不确定性，用I(xi)度量。接收到符号yj后，事件xi是否发生仍保留有一定的不确定性，用I(xi

/yj)度量。接收到某消息yj后获得的关于事件xi的信息量，用I(xi;yj)表示。3/30/202517平均互信息互信息量I(xi;yj)在X集合上的统计平均值为I(X;yj)在Y集合上的概率加权统计平均值平均互信息（量）3/30/202518平均互信息量的物理意义H(X/Y)：信道疑义度，损失熵信源符号通过有噪信道传输后引起的信息量损失。信源X的熵等于接收到的信息量加损失掉的信息量。

H(Y/X)：噪声熵，散布度它反映了信道中噪声源的不确定性。输出端信源Y的熵H(Y)等于接收到关于X的信息量I(X;Y)加上H(Y/X)，这完全是由信道中噪声引起的。3/30/202519熵的性质非负性H(X)＝H(x1,x2,……,xn)≥0等号在p(xi)=1时成立对称性H(x1,x2,……,xn)＝H(x2,x1,……,xn)熵函数只与随机变量的总体结构有关确定性H(0,1)＝H(1,0,0,……,0)＝0只要信源符号集中有一个符号的出现概率为1，信源熵就等于零3/30/202520熵的性质香农辅助定理对于P＝(p1,p2,……,pn)和Q＝(q1,q2,……,qn)对任意概率分布pi，它对其他概率分布qi的自信息量取数学期望时，必不小于pi本身的熵最大熵定理离散无记忆信源输出M个不同的信息符号，当且仅当各个符号出现概率时（即等概率分布），熵最大3/30/202521互信息量与熵H(X/Y)H(X)H(Y)H(XY)H(Y/X)I(X;Y)3/30/202522离散无记忆信源的序列熵设信源输出的随机序列为X

=(X1X2…Xl…XL)序列中的变量Xl∈{x1,x2,…

xn}信源的序列熵可以表示为信源序列中，平均每个符号的熵为离散无记忆信源平均每个符号的符号熵HL(X)等于单个符号信源的符号熵H(X)无记忆无记忆、平稳3/30/202523离散有记忆信源的序列熵若信源输出一个L长序列，则信源的序列熵为平均每个符号的熵为信源无记忆时满足平稳时3/30/202524离散平稳信源结论1：H(XL/XL-1)是L的单调非增函数结论2：HL

(X)≥H(XL/XL-1)结论3：HL

(X)是L的单调非增函数结论4：当L→∞时，H∞(X)称为极限熵3/30/202525马尔可夫信源若一个信源满足下面两个条件，则称为马尔可夫信源：某一时刻信源输出符号的概率只与当前所处的状态有关，而与以前的状态无关；信源的下一个状态由当前状态和下一刻的输出符号唯一确定。符号条件概率信源在某一时刻出现符号xj的概率与信源此时所处的状态si有关，用条件概率表示为p(xj/si)。状态转移概率当信源符号xj出现后，信源所处的状态将发生变化，并转入一个新的状态。这种状态的转移可用状态转移概率p(sj/si)表示。3/30/202526状态转移图（香农线图）齐次马尔可夫链可以用其状态转移图（香农线图）表示每个圆圈代表一种状态

状态之间的有向线代表从某一状态向另一状态的转移有向线一侧的符号和数字分别代表发出的符号和条件概率sos1x2/0.6x1/0.3x1/0.4s2x2/0.2x1/0.8x2/0.7p(x1/s2)=0.8p(s2/s2)=0.83/30/202527稳定的马尔可夫信源极限概率Wj一个不可约的、非周期的、状态有限的马尔可夫链，其k步转移概率pij(k)在k→∞时趋于一个和初始状态无关的概率，即不论起始状态如何，这种马氏链都可以最后达到稳定，即所有变量Xk的概率分布均不变。可以用P这一矩阵充分描述稳定的马氏链。平稳分布Wj可用下列方程组求得3/30/202528马尔可夫信源的熵M阶马尔可夫信源的极限熵齐次、遍历的马尔可夫信源的熵处于状态si时符号的平均不确定性3/30/202529第3章信道与信道容量重点掌握有干扰无记忆信道的数学描述信道容量的定义对称和准对称DMC信道的信道容量计算香农公式一般了解信道的各种分类无干扰离散信道的信道容量信源和信道的匹配3/30/202530信道的分类按信道的用户数量来划分 单用户信道、多用户信道按输入/输出之间的关系来划分

无反馈信道、反馈信道按信道参数与时间的关系来划分 固定参数信道、时变参数信道按信道中的噪声种类来划分

随机差错信道、突发差错信道按输入/输出信号在幅度和时间上的取值划分离散信道、连续信道、半离散半连续信道、波形信道3/30/202531信道模型根据干扰和记忆性分类无干扰（无噪声）信道有干扰无记忆信道有干扰有记忆信道信道模型信道的输入Xi={a1,a2,…,an}信道的输出Yj={b1,b2,…,bm}信道转移概率矩阵p(Y/X)信道输入X输出Yp(Y/X)3/30/202532信道模型二进制离散信道：BSC信道输入符号X取值{0,1}输出符号Y取值{0,1}离散无记忆信道：DMC信道输入符号集

X={a1,a2,…,an}输出符号集

Y={b1,b2,…,bm}3/30/202533信道模型离散输入、连续输出信道输入符号集：X={a1,a2,…,an}输出未经量化，即Y={-∞,∞}输出特性由离散输入X、连续输出Y以及一组条件概率密度函数p(y/X=ai)

来决定。波形信道输入是模拟波形，输出也是模拟波形连续无记忆信道和连续有记忆信道y(t)＝x(t)＋n(t)

n(t)代表加性噪声3/30/202534信道容量的定义信道传输率R＝I(X;Y)bit/符号信道中平均每个符号能传送的信息量信息传输速率Rt＝I(X;Y)/t

bit/s信道中单位时间传送的信息量信道容量给定转移概率矩阵P后，平均互信息I(X;Y)是概率矢量Px的上凸函数。I(Px)的极大值就是信道容量。3/30/202535离散单符号信道离散单个符号信道无干扰离散信道有扰离散信道对称DMC信道准对称DMC信道一般DMC信道无噪无损信道无噪有损信道有噪无损信道3/30/202536无干扰离散信道无噪无损信道C=maxI(X;Y)=logn无噪有损信道C=maxI(X;Y)=maxH(Y)有噪无损信道C=maxI(X;Y)=maxH(X)3/30/202537DMC信道的容量对称DMC信道的性质对称信道的条件熵H(Y/X)与信道输入符号的概率分布无关。如果信道输入符号等概率分布，则信道输出符号也等概率分布；反之，若信道输出符号等概率分布时，信道输入符号也是等概率分布。当信道输入符号等概率分布时，对称DMC信道达到其信道容量。3/30/202538DMC信道的容量准对称DMC信道的容量如果转移概率矩阵P的输入对称而输出不对称，则称该信道是准对称DMC信道。当信道输入符号等概率分布时，准对称DMC信道达到其信道容量C。矩阵分解法：将转移概率矩阵划分成若干个互不相交的对称子矩阵。3/30/202539DMC信道的容量一般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的输入符号对输出提供相同的互信息3/30/202540离散序列信道及其容量信道输入X输出Yp(Y/X)X=(X1,X2,…,XL)Xl={a1,a2,…,an}Y=(Y1,Y2,…,YL)Yl={b1,b2,…,bm}独立、无记忆、平稳离散序列信道的信道容量为：无记忆离散序列信道的转移概率为：3/30/202541连续信道连续单符号加性信道信道的输入和输出都是取值连续的一维随机变量，加入信道的噪声是均值为零、方差为σ2的加性高斯噪声。多维无记忆加性连续信道可等价成L个独立的并联高斯加性信道注水法：噪声小的子信道分配到的输入功率大，传输的比特数多。受加性高斯白噪声干扰的带限波形信道输入x(t)、输出y(t)和噪声n(t)：模拟波形3/30/202542香农公式香农公式W：频带宽度，简称带宽SNR(信噪比)：表示信号功率与噪声功率的比值加性白噪声的功率谱密度为N0/2Pav：信号的平均功率香农限每传输1比特信息所需的能量。当归一化的信噪比小于香农限（-1.6dB）时，归一化信道容量为零，即信道完全丧失通信能力。3/30/202543香农公式的讨论带宽W一定时，信道容量C

随信噪比SNR的增加而单调增加，因此增大信号功率、减小信道噪声可以增加信道容量。信道容量C一定时，带宽W增大，信噪比SNR可降低，即二者可以互换。如果输入信号功率PS固定，信道容量C

随带宽W的增加而增加。但到一定阶段后，增加变得缓慢。3/30/202544信源与信道的匹配符号匹配信源输出的符号必须是信道能够传送的符号，这是实现信息传输的必要条件。信息匹配对于某一信道，只有当输入符号的概率分布满足一定条件时，才能达到其信道容量。信道冗余度信道绝对冗余度＝C－I(X;Y)信道相对冗余度3/30/202545第4章信息率失真函数重点掌握失真函数、平均失真保真度准则信息率失真函数的定义域信息率失真函数与信道容量的比较一般了解信息率失真函数的性质连续信源的平均失真3/30/202546失真函数单符号失真函数定义为：将所有的d(xi,yj)排列起来，用矩阵表示为d称为失真矩阵3/30/202547失真函数如果假定离散信源输出符号序列X=(X1X2…Xl…XL),

Xl∈A={a1,…an}，其中L长符号序列xi=(xi1xi2…xiL)，经信源编码后输出符号序列Y=(Y1Y2…Yl…YL)，Yl∈B={b1,…bm}，其中L长符号序列 yj=(yj1yj2…yjL)， 序列失真函数定义为式中，d(xil,yjl)表示信源输出符号序列xi的第l个符号和编码输出符号序列yj的第l个符号之间的失真函数信源序列的失真度等于序列中对应单个符号的失真度之和3/30/202548平均失真将失真函数的数学期望或统计平均值称为平均失真。失真函数d(xi,yj)描述某个信源符号通过传输后失真的大小。对于不同的信源符号和不同的接收符号，其值是不同的。平均失真：平均失真对信源和信道进行的统计平均。描述某一信源在某一试验信道传输下的失真大小，是从总体上描述整个系统的失真情况。3/30/202549平均失真L维信源符号序列的平均失真度当信源与信道无记忆时，信源符号平均失真度（平均每个符号的平均失真度）表示信源符号序列的第l个符号的平均失真3/30/202550保真度准则保真度准则平均失真度不大于允许的失真D允许信道D允许的试验信道，即满足保真度准则的试验信道。满足保真度准则的所有试验信道，即转移概率分布p(yj/xi)，构成了一个信道集合3/30/202551信息率失真函数信息率失真函数R(D)限定失真为D的条件下，信源输出的最小信息率。R(D)的定义域率失真函数的定义域问题就是在信源和失真函数已知的情况下，讨论允许平均失真度D的最小和最大取值问题，即[Dmin,Dmax]Dmin的计算Dmax的计算3/30/202552信息率失真函数的性质

R(D)是非负的实数，0≤R(D)≤H(X)

定义域为0≤Dmin≤D≤Dmax

当D＞Dmax时，R(D)≡0

R(D)是关于D的下凸函数R(D)在定义域内是失真度D的U型下凸函数。R(D)在定义域内是关于D的连续函数。

R(D)的单调递减性容许的失真度越大，所要求的信息率越小。3/30/202553率失真函数和信道容量的比较平均互信息I(X;Y)信源的概率分布p(xi)的上凸函数。信道传递概率p(yj/xi)的下凸函数。信道容量信息率失真函数信道固定输入概率分布固定3/30/202554率失真函数和信道容量的比较3/30/202555第5章信源编码重点掌握分组码的属性唯一可译码的判断方法信源编码定理香农编码、费诺编码、哈夫曼编码一般了解编码的术语游程编码、算术编码3/30/202556分组码属性码非分组码分组码奇异码非奇异码非唯一可译码唯一可译码非即时码即时码（非延长码）3/30/202557码树中间节点不安排码字，只在终端节点安排码字每个终端节点对应的码字由从根节点出发到终端节点走过的路径上所对应的符号组成当第i阶的节点作为终端节点，且分配码字，则码字的码长为i按树图法构成的码一定满足即时码的定义树码的各个分支都延伸到最后一级端点，则称为满树，否则为非满树

满树码是定长码，非满树码是变长码3/30/202558克劳夫特不等式唯一可译码存在的充分和必要条件为：各码字的长度Ki应满足下式。m是进制数，n是信源符号数注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据。3/30/202559唯一可译码的判断法将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。集合F的构成方法首先观察码C中最短的码字是否是其它码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀（或者某些码字是这些尾随后缀的前缀），再将这些尾随后缀产生的新的尾随后缀列出。依此下去，直到没有一个尾随后缀是码字的前缀为止。按照上述步骤将次短码字、…等等所有码字可能产生的尾随后缀全部列出。最终得到码C的所有可能的尾随后缀的集合F。3/30/202560唯一可译码判断方法和步骤首先，观察是否是奇异码。若是，一定不是唯一可译码。其次，计算码长是否满足Kraft不等式。若不满足，一定不是唯一可译码。按照树图的构造法则，若能将码画成码树则是即时码，也就是唯一可译码。按唯一可译码判断法进行判断。只有唯一可译码判断法能确切判断是否是唯一可译码3/30/202561无失真信源编码设信源符号序列的长度为L变换成由KL个符号组成的 码序列（码字）变换要求能够无失真或无差错地从Y恢复X，也就是能正确地进行反变换或译码传送Y时所需要的信息率最小3/30/202562定长编码定理定长编码定理：由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2…Xl…XL，可用KL个符号Y1,Y2,…,Yk,…YKL（每个符号有m种可能值）进行定长编码。对任意ε>0，δ>0，只要 则当L足够大时，必可使译码差错小于δ；反之，当 时，译码差错一定是有限值，而当L足够大时，译码几乎必定出错。3/30/202563编码效率差错概率当信源序列长度L满足 时， 就能达到差错率要求。编码效率最佳编码效率为3/30/202564变长编码定理单个符号变长编码定理若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式3/30/202565变长编码定理离散平稳无记忆序列变长编码定理对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中，ε为任意小正数。3/30/202566香农编码步骤将信源消息符号按其概率从大到小排列确定满足下列不等式的整数码长Ki令P1=0，计算第i个消息的累加概率将累加概率Pi变换成二进制数，取小数点后Ki位为该消息的码字3/30/202567费诺编码方法费诺编码属于概率匹配编码，不是最佳的编码方法。编码过程如下：将信源消息符号按其出现的概率依次排列

p(x1)≥p(x2)≥…≥p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等，并为每一组分配一位码元。如编二进制码就分成两组，编m进制码就分成m组。将每一分组再按同样原则划分，重复步骤2，直至概率不再可分为止。信源符号所对应的码字即为费诺码。3/30/202568哈夫曼编码方法哈夫曼编码的步骤将信源消息符号按其出现的概率大小依次排列

p(x1)≥p(x2)≥…≥p(xn)取两个概率最小的符号分别配以0和1，并将这两个概率相加作为一个新符号的概率，与未分配码元的符号重新排队。对重排后的两个概率最小符号重复步骤2的过程。继续上述过程，直到最后两个符号配以0和1为止。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。3/30/202569三种编码的比较香农码、费诺码、哈夫曼码都考虑了信源的统计特性，经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现对信源的压缩。香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高。费诺码和哈夫曼码的编码方法都不惟一。费诺码比较适合于对分组概率相等或接近的信源编码。哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。3/30/202570限失真信源编码定理设离散无记忆信源X的信息率失真函数为R(D)当信息率R＞R(D)时，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D＋ε，ε为任意小的正数。反之，若R＜R(D)，则无论采用什么样的编码方法，其译码失真必大于D。如果是二元信源，则对于任意小的ε＞