信息论与编码复习期末考试要点市公开课一等奖百校联赛特等奖课件.pptx

信息论与编码信息论与编码信息论与编码信息论与编码第 1 页2课程内容课程内容信息论基本问题信息度量无失真信源编码定理香农第一定理信道编码定理香农第二定理限失真信源编码定理香农第三定理信源编码信道编码第 2 页绪绪绪绪 论论论论第一章第一章第 3 页41、信息论奠基人香农及其主要著作；2、信息、消息、信号区分和联络3、通信系统模型各主要功效模块（包含信源、信道、信宿、信源编译码器、信道编译码器）及其作用第 4 页5信息论奠基人：香农主要著作：1948年香农在贝尔系统技术杂志上发表通信数学理论(A mathematical theory of communication)。第一次提出了信息量概念，并应用数理统计方法来研究通信系统，创建了信息论。通信基本问题就是在一点重新准确地或近似地再现另一点所选择消息 -香农（一）信 息 论 形 成 与 发 展第 5 页6（二）信息、消息和信号区分与联络（二）信息、消息和信号区分与联络信息是事物运动状态或存在方式。信息基本概念在于它不确定性不确定性,任何已确定事物都不含信息。消息是指包含有信息语言、文字和图像等 信号是消息物理表达。信号是信息载荷子或载体，是物理性。第 6 页7（三）数字通信系统模型（三）数字通信系统模型信道信源信源编码加密信道编码干 扰 源信宿信源解码解密信道解码加密密钥解密密钥u u u ux x x xy y y yk k k kz z z zv v v vz z z z y y y y x x x x 第 7 页信源与信息熵信源与信息熵信源与信息熵信源与信息熵第二章第二章第 8 页1、掌握相关概念信源分类（如离散与连续、有记忆和无记忆等）自信息、信源熵、平均互信息等概念及性质2、熟练熵、互信息相关计算3、掌握马尔科夫信源中状态转移概率、符号转移概率相关概念以及运算4、了解数据处理定理5、了解连续信源中，最大熵定理1）限峰功率最大熵定理2）限平均功率最大熵定理9第 9 页10一、一、自信息量自信息量设离散信源X，其概率空间为自信息量：某符号出现后提供给收信者信息量第 1 0页11特征特征I(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)两个独立事件联合自信息量等于它们分别自信息量之和。第 1 1页12二、离散信源熵二、离散信源熵离散信源熵H(X)(平均不确定度/香农熵)单位为比特/符号或比特/符号序列 第 1 2页13条件熵条件熵（极限情况条件熵）当X，Y相互独立时，条件熵等于无条件熵第 1 3页14几个概念几个概念联合熵联合熵联合熵H(X,Y)表示X 和Y同时发生不确定度。第 1 4页15三、互信息三、互信息互信息定义为 xi后验概率与先验概率比值对数互信息互信息互信息互信息I(xi;yj)：表示接收到某消息表示接收到某消息表示接收到某消息表示接收到某消息y yj j后取得后取得后取得后取得关于事件关于事件关于事件关于事件x xi i信息量。信息量。信息量。信息量。第 1 5页16平均互信息平均互信息平均互信息定义 互信息=先验不确定性后验不确定性 =不确定性降低量Y未知,X 不确定度为H(X)Y已知,X 不确定度变为H(X|Y)第 1 6页17i.对称性：ii.非负性：iii.极值性：四、平均互信息性质四、平均互信息性质iv.凸函数性（1）平均互信息量I(X;Y)是输入信源概率分布 p(xi)上凸函数，这一点研究信道容量理论基础。（2）平均互信息量I(X;Y)是信道转移概率 p(yj|xi)下凸函数，这一点是研究信源信息率失真函数理论基础。第 1 7页18维拉图维拉图 H(X|Y)H(X)H(Y)H(XY)H(Y|X)I(X;Y)平平均均互互信信息息与与各各类类熵熵关关系系 第 1 8页收、发两端熵关系收、发两端熵关系 I(X;Y)H(X)H(Y)H(X/Y)损损失失熵熵 H(Y/X)噪噪 声声 熵熵第 1 9页20条件熵条件熵H(X|Y)：信道疑义度，损失熵信源符号经过有噪信道传输后所引发信息量损失。信源X熵等于接收到信息量加上损失掉信息量。H(Y|X)：噪声熵，散布熵它反应了信道中噪声源不确定性。输出端信源Y 熵H(Y)等于接收到关于X信息量I(X;Y)加上H(Y|X),这完全是因为信道中噪声引发。第 2 0页21五、数据处理定理五、数据处理定理 数据处理定理说明：当对信号、数据或消息进行多级处理时,每处理一次,就有可能损失一部分信息,也就是说数据处理会把信号、数据或消息变成更有用形式，不过绝不会创造出新信息,这就是所谓信息不增原理。第 2 1页六、熵性质六、熵性质1.非负性 H(X)H(p1，p2，pn)0式中等号只有在pi=1时成立。2.对称性 H(p1，p2，pn)=H(p2，p1，pn)3.确定性 H(X)H(p1，p2，pn)0只要信源符号中有一个符号出现概率为1,信源熵就等于零。第 2 2页23熵性质熵性质4.极值性(香农辅助定理)对任意两个消息数相同信源 5.最大熵定理(sl)离散无记忆信源输出M个不一样信息符号,当且仅当各个符号出现概率相等时即(pi1/M)熵最大。第 2 3页24熵性质熵性质6.条件熵小于无条件熵 第 2 4页25七、七、马尔可夫信源马尔可夫信源马尔可夫信源一类相对简单离散平稳有记忆信源该信源在某一时刻发出字母概率除与该字母相关外,只与以前发出有限个字母相关m阶马尔可夫信源：信源输出某一符号概率仅与以前m个符号相关，而与更前面符号无关。条件概率第 2 5页26马氏链基本概念马氏链基本概念 令si=(xi1,xi2,xim)xi1,xi2,xim(a1,a2,an)状态集S=s1,s2,sQ Q=nm信源输出随机符号序列为：x1,x2,xi-1,xi 信源所处随机状态序列为：s1,s2,si-1,si 例：二元序列为01011100考虑m=2，Q=nm=22=4s1=00 s2=01 s3=10 s4=11变换成对应状态序列为 s2 s3 s2 s4 s4 s3 s1第 2 6页27若信源处于某一状态si,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻状态和发出符号决定。系统在任一时刻可处于状态空间S=s1,s2,sQ中任意一个状态,状态转移时,转移概率矩阵符号条件概率矩阵区区区区分分分分第 2 7页28马尔可夫信源马尔可夫信源一个不可约、非周期、状态有限马尔可夫链其k步转移概率pij(k)在k时趋于一个和初始状态无关极限概率Wj，它是满足方程组 唯一解；Wj：马尔可夫链一个平稳分布，Wj 或或p(sj)就是系统此时处于状态sj概率。不不论论随随机机点点从从哪哪一一个个状状态态si出出发发，当当转转移移步步数数k足足够够大大时时，转转移移到到状状态态sj概概率率pij(k)都都近近似似于于一一 个个 常常 数数Wj第 2 8页29例5：有一个二元二阶马尔可夫信源,其信源符号集为0，1，已知符号条件概率：p(0|00)=1/2 p(1|00)=1/2 p(0|01)=1/3 p(1|01)=2/3 p(0|10)=1/4 p(1|10)=3/4 p(0|11)=1/5 p(1|11)=4/5求：信源全部状态及状态转移概率画出完整二阶马尔可夫信源状态转移图。求平稳分布概率 第 2 9页30状态转移概率矩阵符号条件概率矩阵(1)1/2(0)1/2(0)1/3(1)2/30 00 11 11 0s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/5第 3 0页31稳态分布概率第 3 1页八、连续信源熵和互信息八、连续信源熵和互信息 32相对熵/连续熵第 3 2页33限峰功率最大相对熵定理 对于定义域为有限随机矢量X，当它是均匀分布时，其熵最大。随机变量X幅度取值限制在a,b，当信源到达最大熵。第 3 3页34限平均功率最大相对熵定理 对于相关矩阵一定随机矢量X，当它是正态分布(高斯分布)时含有最大相对熵。即随机变量X概率密度分布为信源熵最大。奈特/样值第 3 4页信道与信道容量信道与信道容量信道与信道容量信道与信道容量第三章第三章第 3 5页36熟练掌握信道容量相关概念 信道分类（有记忆和无记忆信道）、信道容量、信源与信道匹配熟练计算信道容量以及到达信道容量时对应输入概率分布 重点：无干扰离散信道、对称DMC（离散无记忆）信道、准对称信道 习题5、6第 3 6页37信道容量信道容量信道容量C：最大信息传输率第 3 7页381 1、无干扰离散信道、无干扰离散信道设信道输入X XA=a1 an,输出YB=b1 bm 1 1）无嗓无损）无嗓无损信道输入和输出符号之间有确定一一对应关系第 3 8页392 2）无嗓有损）无嗓有损信道多个输入变成一个输出(nm)噪声熵H(Y|X)0 损失熵H(X|Y)0第 3 9页403 3）有嗓无损有嗓无损信道一个输入对应多个输出(nm)接收到符号Y后,对发送X符号是完全确定。噪声熵H(Y|X)0 损失熵H(X|Y)=0第 4 0页412 2、对称、对称DMCDMC信道信道对称离散信道：对称性:每一行都是由同一集q1,q2,qm诸元素不一样排列组成输入对称每一列都是由p1,p2,pn集诸元素不一样排列组成输出对称由输入对称推出由输出对称推出最正确输入分布以及信道容量详细表示式第 4 1页42对称DMC信道容量（最正确输入为等概率分布）：上式是对称离散信道能够传输最大平均信息量,它只与对称信道矩阵中行矢量p1,p2,pm 和输出符号集个数m相关。强对称信道信道容量：第 4 2页433、准对称、准对称DMC信道信道 准对称信道转移概率矩阵P是输入对称而输出不对称将信道矩阵P列划分成若干个互不相交子集mk,由mk为列组成矩阵Pk是对称矩阵。它们满定对称性,所以P1所对应信道为准对称信道。第 4 3页44准对称信道信道容量准对称信道信道容量 当输入分布为等概率时：其中n是输入符号集个数,(p1,p2,pm)为准对称信道矩阵中行元素。设矩阵可划分成r个互不相交子集。Nk是第k个子矩阵Pk中行元素之和,Mk是第k个子矩阵Pk中列元素之和。第 4 4页45例：设信道传递矩阵为 计算得：N1=3/4,N2=1/4,M1=3/4,M2=1/4将它分成 第 4 5页信息率失真函数信息率失真函数信息率失真函数信息率失真函数 第第4 4章章第 4 6页471、概念、定义：失真函数、平均失真、允许失真度、试验信道2、信息率失真函数（注意与信道容量比较)3、信息率失真函数定义域(即Dmin和Dmax）、R(Dmin)、R(Dmax)及对应信道转移概率计算第 4 7页48失真函数d(xi,yj)(信号空间中某类“距离”)：描述了某个信源符号经过传输后失真大小平均失真 ：描述某个信源在某一试验信道传输下失真大小,它对信源和信道进行了统计平均,是从总体上描述整个系统失真失真矩阵:1 1、失真函数和、失真函数和平均失真 第 4 8页49xi和yj都是随机变量,所以失真函数d(xi,yj)也是随机变量,限失真时失真值只能用数学期望表示将失真函数数学期望称为平均失真：允许失真D：平均失真上界 第 4 9页502 2、试验信道、试验信道若平均失真度 小于我们所允许失真,即则称此为保真度准则满足 条件全部转移概率分布pij,组成了一个信道集合称为D失真允许试验信道：满足保真度准则试验信道。第 5 0页514 4、信息率失真函数、信息率失真函数R(D)R(D)R(D)：在限定失真为D条件下信源输出最小信息速率。第 5 1页52R(D)定义域率失真定义域问题就是在信源和失真函数已知情况下,讨论允许平均失真度D最小和最大取值问题。因为平均失真度是非负实数d(xi,yj)数学期望,所以也是非负实数,即 下界是0。R(D)=0意味着不需传输任何消息，D越大，直至无穷大都能满足这种情况。Dmin Dmax为R(D)定义域。（确界）第 5 2页53Dmin 和R(Dmin)计算信源最小平均失真度：只有当失真矩阵每一行最少有一个0元素时,信源平均失真度才能到达下限值0。只有当失真矩阵每一行最少有一个0，每一列至多只有一个0，才能确保R(0)=H(X)。第 5 3页54Dmax和R(Dmax)选择全部满足R(D)0中D最小值，定义为R(D)定义域上限Dmax，即 因为I(X,Y)=0充要条件是X与Y统计独立,即：第 5 4页55例4-3:设输入输出符号表为X=Y=0,1,输入概率分布p(x)=1/3,2/3,失真矩阵 求：Dmin 和Dmax、R(Dmin)和R(Dmax)及对应编码器转移概率 失真矩阵每一行最少有一个0元素时,Dmin=0第 5 5页56第五章第五章 信源编码信源编码1、编码定义和分类：信源编码、信道编码、安全编码2、信源存在冗余原因2、信源编码目标、任务和编码基本路径4、熟练掌握三种能取得最正确变长编码方法：香农编码、费诺编码、哈夫曼编码；了解游程编码5、计算编码效率、平均码长第 5 6页