信息论与编码-总复习.ppt

《信息论与编码-总复习.ppt》由会员分享，可在线阅读，更多相关《信息论与编码-总复习.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、总复习*1l信息l定义：信息是该事物运动的状态和状态改变的方式。l认识论层次的信息是同时考虑语法信息、语义信息和语用信息的全信息。l全信息全信息：同时考虑外在形式/语法信息、内在含义/语义信息、效用价值/语用信息。l语法信息：事物运动状态和状态改变的方式；l语义信息：事物运动状态和方式的具体含义；l语用信息：事物运动状态和方式及其含义对观察者的效用价值。l研究信息论的目的：研究信息论的目的：提高信息系统的可靠性、有效性和安全性以便达到系统最优化。第一章 概 论总复习*2单符号离散信源l自信息量自信息量l设离散信源 X，其概率空间为l如果知道事件 xi 已发生，则该事件所含有的自信息定义为l当事

2、件 xi 发生以前：表示事件 xi 发生的不确定性。l当事件 xi 发生以后：表示事件 xi 所含有（或所提供）的信息量第二章 信源熵总复习*3l联合自信息量联合自信息量l当 X 和 Y 相互独立时，p(xiyj)=p(xi)p(yj)第二章 信源熵总复习*4l条件自信息量：条件自信息量：已知 yj 的条件下 xi 仍然存在的不确定度。l自信息量、条件自信息量和联合自信息量之间的关系自信息量、条件自信息量和联合自信息量之间的关系第二章 信源熵总复习*5l互信息量：互信息量：yj 对 xi 的互信息量定义为的后验概率与先验概率比值的对数。第二章 信源熵总复习*6l观察者站在输出端观察者站在输出端

3、：两个不确定度之差是不确定度被消除的部分，即等于自信息量减去条件自信息量。l观察者站在输入端观察者站在输入端：观察者得知输入端发出 xi 前、后对输出端出现 yj 的不确定度的差。l观察者站在通信系统总体立场上观察者站在通信系统总体立场上：通信后的互信息量，等于前后不确定度的差。第二章 信源熵总复习*7l平均信息量平均信息量信源熵：信源熵：自信息的数学期望。也称为信源的信息熵/信源熵/香农熵/无条件熵/熵函数/熵。l信源熵的三种物理含义信源熵的三种物理含义l信源熵 H(X)是表示信源输出后每个消息/符号所提供的平均信息量；l信源熵 H(X)是表示信源输出前，信源的平均不确定性；l用信源熵 H(

4、X)来表征变量 X 的随机性。第二章 信源熵总复习*8l条件熵：条件熵：是在联合符号集合 XY 上的条件自信息的数学期望。第二章 信源熵总复习*9l信道疑义度信道疑义度H(X/Y)：表示信宿在收到 Y 后，信源 X 仍然存在的不确定度。是通过有噪信道传输后引起的信息量的损失，故也可称为损失熵。l噪声熵噪声熵H(Y/X)：表示在已知 X 的条件下，对于符号集 Y 尚存在的不确定性（疑义），这完全是由于信道中噪声引起的。第二章 信源熵总复习*10l联合熵联合熵 H(XY)：表示输入随机变量 X，经信道传输到达信宿，输出随机变量 Y。即收、发双方通信后，整个系统仍然存在的不确定度。第二章 信源熵总复

5、习*11l最大离散熵定理最大离散熵定理(极值性极值性)：离散无记忆信源输出 n 个不同的信息符号，当且仅当各个符号出现概率相等时(即p(xi)=1/n)，熵最大。Hp(x1),p(x2),p(xn)H(1/n,1/n,1/n)=log2n 出现任何符号的可能性相等时，不确定性最大。第二章 信源熵总复习*12l二进制信源的熵函数 H(p)为第二章 信源熵总复习*13l平均互信息量定义：平均互信息量定义：互信息量 I(xi;yj)在联合概率 P(XY)中的统计平均值。1.站在输出端：站在输出端：I(X;Y)收到 Y 前、后关于 X 的不确定度减少的量。从 Y 获得的关于 X 的平均信息量。2.站在

6、输入端：站在输入端：I(Y;X)发出 X 前、后关于 Y 的先验不确定度减少的量。3.站在总体：站在总体：I(X;Y)通信前、后整个系统不确定度减少量。第二章 信源熵总复习*14lBSC信道的平均互信息量 设二进制对称信道的输入概率空间为 转移概率如图所示。第二章 信源熵总复习*15 平均互信息量l当 q 不变(固定信道特性固定信道特性)时，可得 I(X;Y)随输入概率分布 p 变化的曲线，如图所示；二进制对称信道特性固定后，输入呈等概率分布时，平均而言在接收端可获得最大信息量。第二章 信源熵总复习*16l当固定信源特性固定信源特性 p 时，I(X;Y)就是信道特性 q 的函数，如图所示；当二

7、进制对称信道特性 q=/q=1/2时，信道输出端获得信息量最小，即等于0。说明信源的全部信息信息都损失在信道中了。这是一种最差的信道。第二章 信源熵总复习*17l离散无记忆信源 X 的 N 次扩展信源的熵等于离散信源X 的熵的 N 倍，即H(X)=H(XN)=NH(X)l离散平稳信源：离散平稳信源：各维联合概率均与时间起点无关的完全平稳信源称为离散平稳信源。1.二维离散平稳信源的熵为 H(X)=H(X1X2)=H(X1)+H(X2/X1)2.N维离散平稳信源的熵为 H(X)=H(X1X2XN-1XN)=H(X1)+H(X2/X1)+H(X3/X1X2)+H(XN/X1X2XN-1)第二章 信源

8、熵总复习*18l平均符号熵：平均符号熵：信源平均每发一个符号提供的信息量为l离散平稳有记忆信源的极限熵：离散平稳有记忆信源的极限熵：当 N 时，平均符号熵取极限值称之为极限熵或极限信息量。用 H表示，即l极限熵的存在性：极限熵的存在性：当离散有记忆信源是平稳信源时，极限熵等于关联长度 N时，条件熵H(XN/X1X2XN-1)的极限值，即l极限熵的含义：极限熵的含义：代表了一般离散平稳有记忆信源平均每发一个符号提供的信息量。第二章 信源熵总复习*19l信源熵的相对率信源熵的相对率：=H/H0l信源冗余度信源冗余度：=1=(H0H)/H0l信源的冗余度表示信源可压缩的程度信源的冗余度表示信源可压缩

9、的程度。第二章 信源熵总复习*20l连续信源的熵连续信源的熵为l上式定义的熵在形式上和离散信源相似，也满足离散熵的主要特性，如可加性，但在概念上与离散熵有差异因为它失去了离散熵的部分含义和性质。第二章 信源熵总复习*21l设信源 通过一干扰信道，接收符号为 Y=y1,y2，信道传递矩阵为 (1)信源 X 中事件 x1 和 x2 分别含有的自信息量。(2)收到消息yj(j=1,2)后，获得的关于 xi(i=1,2)的信息量。(3)信源 X 和信宿 Y 的信息熵。(4)信道疑义度 H(X/Y)和噪声熵 H(X/Y)。(5)接收到 Y 后获得的平均互信息量。第二章 信源熵总复习*22(1)信源 X

10、中事件 x1 和 x2 分别含有的自信息量。解：I(x1)=log2 p(x1)=log2 0.6=0.74(bit)I(x2)=log2 p(x2)=log2 0.4=1.32(bit)(2)收到消息 yj(j=1,2)后，获得的关于 xi(i=1,2)的信息量。解：p(y1/x1)=5/6 p(y2/x1)=1/6 p(y1/x2)=1/4 p(y2/x2)=3/4 p(x1y1)=p(x1)p(y1/x1)=0.65/6=0.5 p(x1y2)=p(x1)p(y2/x1)=0.61/6=0.1 p(x2y1)=p(x2)p(y1/x2)=0.41/4=0.1 p(x2y2)=p(x2)p

11、(y2/x2)=0.43/4=0.3 p(y1)=p(x1y1)+p(x2y1)=0.5+0.1=0.6 p(y2)=p(x1y2)+p(x2y2)=0.1+0.3=0.4第二章 信源熵总复习*23第二章 信源熵总复习*24(3)信源 X 和信宿 Y 的信息熵。解：(4)信道疑义度 H(X/Y)和噪声熵 H(Y/X)。(5)接收到 Y 后获得的平均互信息量。第二章 信源熵总复习*25l信道容量信道容量 C：在信道中最大的信息传输速率，单位是比比特特/信道符号信道符号。l单位时间的信道容量单位时间的信道容量 Ct：若信道平均传输一个符号需要 t 秒钟，则单位时间的信道容量为 Ct 实际是信道的最

12、大信息传输速率。第三章 信道容量总复习*26l求信道容量的方法求信道容量的方法l当信道特性 p(yj/xi)固定后，I(X;Y)随信源概率分布 p(xi)的变化而变化。l调整 p(xi)，在接收端就能获得不同的信息量。由平均互信息的性质已知，I(X;Y)是 p(xi)的上凸函数，因此总能找到一种概率分布 p(xi)（即某一种信源），使信道所能传送的信息率为最大。lC 和 Ct 都是求平均互信息 I(X;Y)的条件极大值问题，当输入信源概率分布 p(xi)调整好以后，C 和 Ct 已与 p(xi)无关，而仅仅是信道转移概率的函数，只与信道统计特性有关；l信道容量是完全描述信道特性描述信道特性的参

13、量；l信道容量是信道能够传送的最大信息量能够传送的最大信息量。第三章 信道容量总复习*27l当 n=2 时的强对称离散信道就是二进制均匀信道。l二进制均匀信道二进制均匀信道 的信道容量为的信道容量为：l二进制均匀信道容量 曲线如图所示。第三章 信道容量总复习*28l香农公式说明香农公式说明l当信道容量一定时，增大信道带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，可以通过提高信噪功率比来补偿。l当信道频带无限时，其信道容量与信号功率成正比。第三章 信道容量总复习*29l有一个二元对称信道有一个二元对称信道，其信道矩阵为 设该信源以 1500(二元符号/秒)的速度传输输入符号。现有一消

14、息序列共有 14000 个二元符号，并设 p(0)=p(1)=1/2，问从信息传输的角度来考虑，10 秒钟内能否将这消息序列无失真地传递完？解：信源：等概率分布 1500符号/秒10秒15000(个二元符号)=15000(bit)14000个二元符号的信息量为 14000(bit)信道：强对称型 10秒内信道可传递信息 150000.86=12900(bit)14000(bit)答：10秒钟内不能无失真传完。第三章 信道容量总复习*30l失真度l设离散无记忆信源为第四章 信息率失真函数总复习*31l对每一对(xi,yj)，指定一个非负函数d(xi,yj)0 i=1,2,n j=1,2,m 称

15、d(xi,yj)为单个符号的失真度/失真函数。表示信源发出一个符号 xi，在接收端再现 yj 所引起的误差或失真。第四章 信息率失真函数总复习*32l平均失真度定义ld(xi,yj)只能表示两个特定的具体符号 xi 和 yj 之间的失真。l平均失真度：平均失真度为失真度的数学期望，第四章 信息率失真函数总复习*33l平均失真度意义平均失真度意义l 是在平均意义上，从总体上对整个系统失真情况的描述。它是信源统计特性 p(xi)、信道统计特性 p(yj/xi)和失真度 d(xi,yj)的函数。当 p(xi)，p(yj/xi)和 d(xi,yj)给定后，平均失真度就不是一个随机变量了，而是一个确定的

16、量。l如果信源和失真度一定，就只是信道统计特性的函数。信道传递概率不同，平均失真度随之改变。第四章 信息率失真函数总复习*34l允许平均失真度允许平均失真度：率失真函数中的自变量 D，也就是人们规定的平均失真度 的上限值。l率失真函数的定义域率失真函数的定义域问题就是在信源和失真函数已知的情况下，讨论允许平均失真度允许平均失真度 D 的最小和最大值问的最小和最大值问题题。lD 的选取必须根据固定信源 X 的统计特性 P(X)和选定的失真函数 d(xi,yj)，在平均失真度 的可能取值范围内。第四章 信息率失真函数总复习*35l常用的失真函数l第一种l当a=1时称为汉明失真矩阵汉明失真矩阵。l第

17、二种/平方误差失真矩阵：d(xi,yj)=(yjxi)2第四章 信息率失真函数总复习*36l单符号信源和单符号信道的信息率失真函数l在信源和失真度给定以后，PD 是满足保真度准则 的试验信道集合，平均互信息 I(X;Y)是信道传递概率 p(yj/xi)的下凸函数，所以在 PD 中一定可以找到某个试验信道，使 I(X;Y)达到最小，即 这个最小值 R(D)称为信息率失真函数称为信息率失真函数，简称率失真函数率失真函数。l在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。从接收端来看，就是在满足保真度准则 的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的最

18、小值。第四章 信息率失真函数总复习*37l设信源 ，其失真度为汉明失真 度，试问当允许平均失真度 D=(1/2)p 时，每一信源符号平均最少需要几个二进制符号(码长)？解：失真矩阵第四章 信息率失真函数总复习*38l设一信源 分别为0.5，0.4，和0.。（1）求二进制Huffman编码及效率。（2）求二次扩展Huffman编码及效率。解答见word文档第五章 信源编码总复习*39l最佳译码准则（最大似然译码）l通信是一个统计过程，纠、检错能力最终要反映到差错概率上。l对于FEC方式，采用纠错码后的码字差错概率为pwe，lp(C)：发送码字C 的先验概率lp(C/R)：后验概率l若码字数为 2

19、k，对充分随机的消息源有p(C)=1/2k，所以最小化的pwe等价为最小化p(CCR)，又等价为最大化p(C=CR)；第六章 信道编码总复习*40l对于 BSC 信道：最大化的 p(C=CR)等价于最大化的 p(RC)，最大化的p(RC)又等价于最小化 d(R,C)，所以使差错概率最小的译码是使接收向量 R 与输出码字 C 距离最小的译码。第六章 信道编码总复习*41l伴随式和错误检测 用监督矩阵编码，也用监督矩阵译码：接收到一个接收字 R 后，校验 HRT=0T 是否成立：l若关系成立，则认为 R 是一个码字；l否则判为码字在传输中发生了错误；lHRT的值是否为0是校验码字出错与否的依据。伴

20、随式/监督子/校验子：S=RHT或ST=HRT。如何纠错？l设发送码矢 C=(Cn1,Cn2,C0)l信道错误图样为 E=(En1,En2,E0)，其中Ei=0，表示第i位无错；Ei=1，表示第i位有错。i=n1,n2,0。第六章 信道编码总复习*42l接收字 R 为 R=(Rn1,Rn2,R0)=C+E =(Cn1+En1,Cn2+En2,C0+E0)l求接收字的伴随式（接收字用监督矩阵进行检验ST=HRT=H(C+E)T=HCT+HET l由于HCT=0T，所以 ST=HET 总结l伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式伴随式仅由错误图样决定仅由错误图样决定；l伴随式是错

21、误的判别式：若S=0，则判为没有出错，接收字是一个码字；若S0，则判为有错。第六章 信道编码总复习*43l构造构造(7,4)汉明码的一致监督矩阵并设计编、译码器。汉明码的一致监督矩阵并设计编、译码器。解：监督矩阵为(37)矩阵第六章 信道编码总复习*44l构造(7,4)汉明码的伴随式第六章 信道编码总复习*45l构造(7,4)汉明码的纠错译码电路第六章 信道编码总复习*46l卷积码与分组码的不同之处卷积码与分组码的不同之处 在任意给定单元时刻，编码器输出的 n 个码元中，每一个码元不仅和此时刻输入的 k 个信息元有关，还与前连续 m 个时刻输入的信息元有关。第六章 信道编码总复习*47l求(3

22、,2,2)系统卷积码的编码电路g(1,1)=g0(1,1)g1(1,1)g2(1,1)=100g(1,2)=g0(1,2)g1(1,2)g2(1,2)=000g(1,3)=g0(1,3)g1(1,3)g2(1,3)=101g(2,1)=g0(2,1)g1(2,1)g2(2,1)=000g(2,2)=g0(2,2)g1(2,2)g2(2,2)=100g(2,3)=g0(2,3)g1(2,3)g2(2,3)=110 该码的任一子码 Cl 中前两位与 ml(1)、ml(2)相同，后一位的监督元由下式确定，即第六章 信道编码总复习*48l串行编码电路串行编码电路g(1,1)=g0(1,1)g1(1,1)g2(1,1)=100 g(2,1)=g0(2,1)g1(2,1)g2(2,1)=000g(1,2)=g0(1,2)g1(1,2)g2(1,2)=000 g(2,2)=g0(2,2)g1(2,2)g2(2,2)=100g(1,3)=g0(1,3)g1(1,3)g2(1,3)=101 g(2,3)=g0(2,3)g1(2,3)g2(2,3)=1106.4.1 卷积码的基本概念