信息论 总复习new

《信息论 总复习new》由会员分享，可在线阅读，更多相关《信息论 总复习new（70页珍藏版）》请在金锄头文库上搜索。

1、1,总 复 习,1 概论 2 信源及信息熵 3 信源编码 4 信道及信道容量 5 信道编码 6 信息率失真函数 7 考试情况,2,信息与消息和信号的区别 消息：是指包含有信息的语言、文字和图像等，可表达客观物质运动和主观思维活动的状态。 信号：把消息变换成适合信道传输的物理量，这种物理量称为信号（如电信号、光信号、声音信号等）。 信息是事物运动状态和状态改变的方式。,第1章 概论,3,信息 信息是事物运动状态和状态改变的方式。 研究信息论的目的：它的主要目的是提高信息系统的可靠性、有效性和安全性以便达到系统最优化。 在通信系统中形式上传输的是消息，但实质上传输的是信息。消息只是表达信息的工具，

2、载荷信息的客体。,4,编码器,信宿,信道,消息,干扰,消息,通信系统模型,信源,信号,解码器,信号+干扰,噪声源,信息论的研究对象:通信系统模型.,信源 信道 加密,信源 信道 解密,通信系统的基本任务要求 可靠: 要使信源发出的消息经过传输后，尽可能准确地、不失真或限定失真地再现在接收端 有效: 用尽可能短的时间和尽可能少的设备来传输最大的消息,5,单符号离散信源 自信息量 用概率测度定义信息量，设离散信源 X，其概率空间为 如果知道事件 xi 已发生，则该事件所含有的自信息定义为,第2章 信源熵,6,联合自信息量 当 X 和 Y 相互独立时，p(xiyj)=p(xi)p(yj),7,条件自

3、信息量：已知yj 的条件下xi 仍然存在的不确定度。 自信息量、条件自信息量和联合自信息量之间的关系,8,互信息量：yj 对 xi 的互信息量定义为的后验概率与先验概率比值的对数。,两个不确定度之差是不确定度被消除的部分，即等于自信息量减去条件自信息量。,9,平均信息量信源熵：自信息的数学期望。也称为信源的信息熵/信源熵/熵。 信息熵的意义：信源的信息熵 H 是从整个信源的统计特性来考虑的。它是从平均意义上来表征信源的总体特性的。对于某特定的信源，其信息熵是唯一的。不同的信源因统计特性不同，其熵也不同。,10,条件熵：是在联合符号集合 XY 上的条件自信息的数学期望。,联合熵 H(XY)：表示

4、输入随机变量 X，经信道传输到达信宿，输出随机变量 Y。即收、发双方通信后，整个系统仍然存在的不确定度。,11,信道疑义度H(X|Y)：表示信宿在收到 Y 后，信源 X 仍然存在的不确定度。是通过有噪信道传输后引起的信息量的损失，故也可称为损失熵。 噪声熵H(Y|X)：表示在已知 X 的条件下，对于符号集 Y 尚存在的不确定性，这完全是由于信道中噪声引起的。唯一确定信道噪声所需要的平均信息量。,12,平均互信息量定义：互信息量 I(xi;yj) 在联合概率空间 P(XY) 中的统计平均值。 从一个事件获得另一个事件的平均互信息需要消除不确定度，一旦消除了不确定度，就获得了信息。,13,平均互信

5、息和熵的关系,14,数据处理定理（信息不增原理）,当消息通过多级处理器时,随着处理器数目的增多,输入消息和输出消息之间的平均互信息量趋于变小。信息不增,I(X;Z) I(X;f(Z)=I(X;Y) H(X|Z) H(X|f(Z)=H(X|Y),15,最大离散熵定理 (极值性) ：离散无记忆信源输出 n 个不同的信息符号，当且仅当各个符号出现概率相等时 (即p(xi)=1/n)，熵最大。 Hp(x1),p(x2),p(xn)logn,16,二进制信源的熵函数 H(p) 为,17,BSC信道的平均互信息量 设二进制对称信道的输入概率空间为,18,19,连续信源的熵为,定义的熵在形式上和离散信源相似

6、。连续信源熵并不是实际信源输出的信息量(绝对熵)； Hc(X) 也称为相对熵,连续信源的信息量为无限大； Hc(X) 已不能代表信源的平均不确定度，也不能代表连续信源输出的信息量。,20,限峰值的最大熵定理:若信源的N维随机变量的取值在一定的范围之内，则在有限的定义域内，均匀分布的连续信源具有最大熵。 限平均功率的最大熵定理：若信源输出信号的平均功率P或方差受限，则其输出信号幅度的概率密度函数为高斯分布时，信源具有最大熵值。 限均值的最大连续熵定理：若连续信源X输出非负信号的均值受限，则其输出信号幅度呈指数分布时，连续信源X具有最大熵值。,21,离散信源的无失真编码实质上是一种统计匹配编码。信

7、息论指出信源中的统计多余度主要决定于以下两个主要因素： 一是消息概率分布的非均匀性，另一个是消息间的相关性。对无记忆信源主要决定于概率分布的非均匀性，但是，对于有记忆信源，两者都起作用，且后者相关性更加重要。,第3章 信源编码,22,Def. 可达速率：对于给定的信源和编码速率R及任意0，若存在L0、()、D()，使当码长LL0时，Pe ，就称R是可达的，否则R是不可达的。,23,Th. 若RH(U)，则R是可达的；若RH(U)，则R是不可达的。 对于给定的离散无记忆信源，若D元码的速率R超过信源的熵，即NlogD/L H（U）+，则存在编码方法，当L足够大时能使译码错误概率任意小。 logD

8、：一个码符号所能载荷的最大信息量。 H(U)：信源输出一个符号所给出的信息量。 H(U)/logD：每个信源符号所需的最小的码符号数以等长码实现源编码时的理论极限。,24,离散无记忆信源的等长编码,译码错误概率 pe,契比雪夫不等式,无扰编码定理的含义 RH(U),契比雪夫不等式的右边是理论上的误码率的上限， 必须小于给定的误码率才能保证到达编码性能要求,25,定长编码定理,其中差错率满足如下式子,26,凡是能载荷一定的信息量,且码字的平均长度最短,可分离的变长码的码字集合就称为最佳变长码. 必须将概率大的信息符号以短的码字, 将概率小的信息符号以长的码字. 主要有:香农-费诺(Shannon

9、-Fano),哈夫曼(Huffman)编码等,唯一可译性的两种解决方法 Def.逗点码 Def.异字头码,27,2香农费诺编码,费诺编码步骤如下： a.将概率按从大到小的顺序排列，令 b.按编码进制数将概率分组，使每组概率尽可能接近或相等。 c.给每一组分配一位码元。 d.将每一分组再按同样原则划分，重复步骤b和c，直至概率不再可分为止。,28,3 哈夫曼编码,a.将信源符号按概率从大到小的顺序排列，令 b.给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位0和1，将这两个符号合并成一个新符号，其概率之和作为新符号的概率，得到(n1)个符号。 c.将缩减信源符号按概率排列，重复步

10、骤a,b。直至缩减信源只剩两个符号为止。 d.从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。,注意3进制编码？,29,4 算术编码,算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为算术编码 以二元信源输出序列的编码为例01110,u对应区间的宽度等于符号序列的概率,30,算术编码,递推公式编码 P(u=bbbbbbaa)=0.7560.252= F(a)=0, F(b)=0.25,H=HP(ul+1),G=G+HF(al+1),31,LZ编码,利用字典编码方法 信源符号A=(a1aK) 将序列分为不同的段 取最短长度的连续符号构成段，保证互不相同。 先取

11、一个符号分段，若与前面段相同，就再取一个符号，直至序列结束 得到字典表，码字由段号加后一个符号组成。 单符号的码字，段号为0,32,LZ编码的特点 特点一 编码效率可以接近信息熵的上限。 特点二 不需要事先知道信源的概率分布。 特点三 用一种巧妙的方式使用字典技术。 特点四 文件越小，压缩比例越小；文件越大，压缩比例越大。 LZ编码的应用领域 几乎垄断了整个通用数据压缩领域，如PKZIP、WinZIP、WinRAR、gzip等压缩工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者。,33,我们学习了几种信源编码：香农费诺编码、哈夫曼编码、游程编码、算术编码、LZ编码等。 游程编码

12、和算术编码是非分组编码；游程编码是限失真信源编码。本章介绍的都是离散信源变长编码。 优点：提高编码效率； 缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；如果出现了误码，容易引起错误扩散，所以要求有优质的信道。,34,信道容量 C：在信道中最大的信息传输速率，单位是比特/符号。 单位时间的信道容量 Ct：若信道平均传输一个符号需要 t 秒钟，则单位时间的信道容量为 Ct 实际是信道的最大信息传输速率。,第3章 信道容量,35,根据信道中所受噪声种类的不同,可分为随机差错信道和突发差错信道. 在有记忆信道中，噪声干扰的影响往往是前后相关的，错误是成串出现的，一般在编码中我们称

13、这类信道为突发差错信道。实际的衰落信道、码间干扰信道均属于这类信道。有些实际信道既有独立随机差错,也有突发性成串差错，我们称它为混合信道。,36,求信道容量的方法 当信道特性 p(yj|xi) 固定后，I(X;Y)随信源概率分布 p(xi)的变化而变化。 调整 p(xi)，在接收端就能获得不同的信息量。由平均互信息的性质已知，I(X;Y) 是 p(xi) 的上凸函数，因此总能找到一种概率分布 p(xi)（即某一种信源），使信道所能传送的信息率为最大。 C 和 Ct 都是求平均互信息 I(X;Y) 的条件极大值问题，当输入信源概率分布 p(xi) 调整好以后， C 和 Ct 已与 p(xi) 无

14、关，而仅仅是信道转移概率的函数，只与信道统计特性有关； 信道容量是完全描述信道特性的参量；信道容量是信道能够传送的最大信息量。,37,当 n=2 时的强对称离散信道就是二进制均匀信道。 二进制均匀信道 的信道容量为： 二进制均匀信道容量 曲线如图3.2.5所示。,38,对称DMC容量的计算,结论 实现对称DMC信道容量的输入分布为等概分布,信道只关于输入对称的话（输入分布为等概分布）,39,一般DMC的容量计算,40,一般DMC的容量计算,这是K个未知量0, 1, , K-1 =C+logw(0), C+logw(1), , C+logw(K-1) 的线性方程组，系数矩阵是可逆方阵，因此唯一解

15、出0, 1, , K-1 ,41,一般DMC的容量计算,另一个等式： w(0)+w(1)+w(K-1)=1。 于是,i=C+logw(i),42,积信道或独立并行信道,C1maxI(X1,Y1)， C2maxI(X2,Y2) 信道1和信道2同时传递消息，输入集X=X1X2，输出集Y=Y1Y2，转移概率 p(jj|kk)=p(j|k)p(j|k) 称这样组合成的信道为1和2的积信道或独立并行信道,积信道的容量 C=C1+C2,43,和信道或并信道,单位时间内可以且只能随机选用信道1和信道2中的一个，选用信道1的概率为p1，选用信道2的概率为p2， p1p21 输入空间X=X1+X2， Y=Y1+

16、Y2，,44,级联信道或串行信道,信道1的输出作为信道2的输入,（3）令自级连的次数N+，则级连信道的转移概率矩阵趋向于,信道容量趋向于0。,45,香农公式 当信道容量一定时，增大信道带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，可以通过提高信噪功率比来补偿。 当信道频带无限时，其信道容量与信号功率成正比。,46,差错控制的基本方式 前向纠错(FEC)：发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，若传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。 自动请求重发(ARQ)：用于检测的纠错码在译码器输出端只给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字全部或部分。,第6章 信道编码,47,混合纠错(HEC)：是 FEC 与 ARQ 方式的结合。发端发送同时具有自动纠错和检测能力的码组，收端收到码组后，检查差错情况，如果差错在码的纠错能力以内，则自动进行纠正。如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测