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