信息论 复习(傅祖芸版本)课件.ppt

《信息论 复习(傅祖芸版本)课件.ppt》由会员分享，可在线阅读，更多相关《信息论 复习(傅祖芸版本)课件.ppt（248页珍藏版）》请在三一办公上搜索。

1、信息论与编码,计算器,2,简 介,是一门应用概率论、随机过程、数理统计和近代代数的方法，来研究信息传输、提取和处理中一般规律的学科。,奠基人：美国数学家香农（C.E.Shannon） 1948年“通信的数学理论”,3,简 介,信息论的基本问题信息的度量无失真信源编码定理香农第一定理信道编码定理香农第二定理信源编码、信道编码,绪 论,第1章,5,1.1 信息的概念,6,情报：是人们对于某个特定对象所见、所闻、所理解而产生的知识。知识：一种具有普遍和概括性质的高层次的信息 ，以实践为基础，通过抽象思维，对客观事物规律性的概括。消息：用文字、符号、语音、图像等能够被人们感觉器官所感知的形式，把客观物

2、质运动和主观思维活动的状态表达出来。,几个常见概念,7,香农信息的度量,（1）样本空间 某事物各种可能出现的不同状态。（2）概率测度 对每一个可能选择的消息指定一个概率。（3）概率空间 先验概率p(xi)：选择符号xi作为消息的概率。,样本空间概率测度,8,例：气象预报 甲乙,“甲地晴”比“乙地晴”的不确定性小。某一事物状态出现的概率越小，其不确定性越大。某一事物状态出现的概率接近于1,即预料中肯定会出现的事件，那它的不确定性就接近于零。,9,对xi的不确定性可表示为先验概率p(xi)的倒数的某一函数。（4）自信息（5）互信息 先验的不确定性减去尚存的不确定性。后验概率p(ai | bj)：接

3、收端收到消息bj后而发送端发的是ai的概率。,10,信息的特征,信息是物质存在的普遍属性，信息和能量、物质规定了事物的功能和性能；接收者在收到信息之前，对它的内容是不知道的，所以，信息是新知识、新内容；它使认识主体对某一事物的未知性或不确定性减少的有用知识；信息的存在具有普遍性、无限性、动态性、时效性和相对独立性；信息可以产生，也可以消失，同时信息可以被传递、转换、扩散、复制、贮存、分割，具有可共享性；信息是可以量度的，信息量有多少的差别。,11,1.2 信息论研究的对象、目的和内容,12,研究对象：通信系统模型,加密密钥,解密密钥,13,信源：发送消息的源离散信源模拟信源信源是信息论的主要研

4、究对象之一.我们不探讨信源的内部结构和机理，而关注信源的输出。重点讨论其描述方法及性质。信宿：信息归宿之意，亦即收信者或用户，是信息传送的终点或目的地。信道：传输信息的物理媒介。,信源、信道、信宿,14,信源编码器通过信源编码可以压缩信源的冗余度,以提高通信系统传输消息的效率。 信源编码器分为两类无失真信源编码：适用于离散信源或数字信号； 限失真信源编码：用于连续信源或模拟信号,如语音、图像等信号的数字处理。,信源编码器与译码器,信源编码器的主要指标是它的编码效率。一般来说，效率越高，编译码器的代价也将越大。 信源译码器把信道译码器的输出变换成信宿所需的消息形式，相当于信源编码器的逆过程。,1

5、5,信道编码器与译码器,信道编码主要作用是提高信息传送的可靠性。信道编码器的作用在信源编码器输出的代码组上有目的地增加一些监督码元,使之具有检错或纠错的能力。信道编码的主要方法增大码率或频带,即增大所需的信道容量。这恰与信源编码相反。信道译码器的作用具有检错或纠错的功能,它能将落在其检错或纠错范围内的错传码元检出或纠正,以提高传输消息的可靠性。,16,1.3 信息论的形成和发展,17,信息论是在长期的通信工程实践和理论研究的基础上发展起来的。简 史现代信息论是从20世纪20年代奈奎斯特和哈特莱的工作开始的：1924年奈奎斯特(Nyquist)的 “影响电报速率因素的确定” 。1928年哈特莱(

6、Hartley) 的“信息传输” 一文研究了通信系统传输信息的能力，并给出了信息度量方法。,信息论的形成,18,1946年柯切尔尼柯夫的学位论文“起伏噪声下的潜在抗干扰理论”，根据最小错误概率准则和最小均方误差准则研究了离散和连续信道的最佳接收问题。1948年香农的权威性长文“通信的数学理论”，讨论了信源和信道特性，1949年香农“噪声中的通信”，两论文奠定了现代信息论的理论基础。此后，在基本理论和实际应用方面，信息论都得到了巨大的发展。,第2章 离散信源及其信息测度,2.1 信源的数学模型及分类,2.2 离散信源的信息熵,2.3 信息熵的基本性质,2.5 离散无记忆的扩展信源,2.6 离散平

7、稳信源,2.7 马尔可夫信源,2.8 信源剩余度与自然语言的熵,20,信源 产生消息或消息序列的源。消息携带信息，是信息的具体形式。描述方法 通信过程中，信源发出何种消息是不确定的、是随机的。 因此，信源可用随机变量、随机矢量或随机过程（或样本空间及其概率测度）来描述。 不同的信源根据其输出消息的不同的随机性质进行分类。,2.1 信源的数学模型及分类,21,1、随机变量描述的信源（单符号）,特点：输出单符号消息。符号集的取值A:a1,a2,aq是有限的或可数的,可用离散型随机变量X描述。数学模型：设每个信源符号ai出现的(先验)概率p(ai) (i=1,2,q) 满足：,概率空间能表征离散信源

8、的统计特性，因此也称概率空间为信源空间。,1）离散信源,22,1）平稳信源,特点: 信源输出的消息由一符号序列所组成。 可用N维随机矢量 X(X1,X2,XN)描述，且随机矢量X的各维概率分布都与时间起点无关 。离散平稳信源：每个随机变量Xi (i1,2,N)是取值离散的随机变量。连续平稳信源：每个随机变量Xi (i1,2,N)是取值连续的随机变量。,2、随机矢量描述的信源,23,2）离散无记忆平稳信源,离散平稳信源的特例，信源发出的符号都相互统计独立，即各随机变量Xi (i1,2,N)之间统计独立。性质：独立P(X)= P(X1, X2, ,XN)= P1(X1) P2(X2) PN(XN)

9、平稳P1(Xi) = P2(Xi)= = PN(Xi) = P(Xi) （下标1-N为时间标志）,N维随机矢量的一个取值，i(ai1 ai2aiN),P(aik)是符号集A的一维概率分布,若各随机变量Xi取值同样符号集A:a1,a2,aq，则,24,信源X的各输出Xi间统计独立、且取值同一符号集A。该信源输出的N维随机矢量X为离散无记忆信源X的N次扩展信源。 此扩展信源取值为符号集i (ai1ai2aiN), 其中(i1 , i2 ,iN =1,2 , ,q)，其数学模型是X信源空间的N重空间：,3）离散无记忆信源的N次扩展信源,若X为离散无记忆信源：,25,4）有记忆信源,信源在不同时刻发出

10、的符号之间是相互依赖的，即信源输出的随机序列X中，各随机变量Xi之间相互依赖。 须使用随机矢量的联合概率分布和条件概率分布来说明它们之间的关联关系。 例：汉字组成的中文序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的中文句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，是彼此相关的。,26,5）m阶马尔可夫信源（非平稳信源）,不同时刻发出的符号间的依赖关系,记忆信源的记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。 若上述条件概率与时间起点 i 无关，信源输出的符号序列可看成为时齐马尔可夫链，则此信源称为时齐马尔可夫信源。,27,2.

11、2 离散信源的信息熵,基本的离散信源： 输出单符号消息，且这些消息间两两互不相容。用一维随机变量X来描述信源的输出，其数学模型可抽象为:,问题：这样的信源能输出多少信息? 每个消息的出现携带多少信息量?,28,信息的度量,要点：信息的度量（信息量）和不确定性消除的程度有关，消除的不确定性获得的信息量；不确定性就是随机性，可以用概率论和随机过程来测度；推论：概率小信息量大，即信息量是概率的单调递减函数；信息量应该具有可加性；信息量的计算公式为（香农（自）信息量的度量）：,29,2.1.1 自信息,设离散信源X的概率空间为：,I(ai)代表两种含义：（1）当事件ai发生以前，表示事件ai发生的不确

12、定性（2）当事件ai发生以后，表示事件ai所提供的信息量,自信息量：事件ai发生所含有的信息量,30,度量单位,计算自信息量时要注意有关事件发生概率的计算；自信息量的单位取决于对数的底；底为2，单位为“比特（bit, binary unit）”；底为e，单位为“奈特（nat, nature unit）”；底为10，单位为“哈特（hat, Hartley）”；根据换底公式得：,一般计算都采用以“2”为底的对数，为了书写简洁，常把底数“2”略去不写,1 nat = 1.44bit , 1 hat = 3.32 bit；,31,收信者收到某消息获得的信息量 不确定性减少的量 (收到此消息前关于某事件

13、的不确定性) - (收到此消息后关于某事件的不确定性)通信的实质？ 即：传递信息，消除不确定性。,32,2.2.2 信息熵,对一个信源发出不同消息所含有的信息量也不同。所以自信息I(ai)是一个随机变量，不能用它来作为整个信源的信息测度。信息熵：自信息的数学期望，平均自信息量Hr(X)：,r进制单位/符号,33,熵的含义,熵是从整个集合的统计特性来考虑的，它从平均意义上来表征信源的总体特征。信源输出前，熵H(X)表示信源的平均不确定性；信源输出后，熵H(X)表示每个消息的平均信息量；信息熵H(X)表征了变量X的随机性。,34,信息熵是信源概率空间的一种特殊函数。这个函数的取值大小，与信源的符号

14、数及其概率分布有关。 用概率矢量P来表示概率分布P(x)：,3.3 信息熵的基本性质,则信息熵H(X)是概率矢量P或它的分量p1，p2，pq的q-1元函数(独立变量只有q-1元)。则 H(X)可写成：,35,熵函数的向量形式,H(P)是概率矢量P的函数，称为熵函数。我们用下述表示方法：用H(x)表示以离散随机变量x描述的信源的信息熵；用H(P)或H(p1, p2 , , pq )表示概率矢量为P = (p1, p2 , , pq )的q个符号信源的信息熵。若当 q =2 时，因为 p1+p2 = 1, 所以将两个符号的熵函数写成H(p1)或H(p2)。熵函数H(P)是一种特殊函数，具有以下性质

15、。,36,熵函数性质,1、对称性： H(P)的取值与分量 p1, p2 , , pq的顺序无关。说明： H(P)= pi log pi 中的和式满足交换率； 熵只与随机变量的总体统计特性有关。例子：,37,2、确定性：H(1,0)=H(1,0,0)=H(1,0,0,0)=0说明：从总体来看，信源虽然有不同的输出符号，但它只有一个符号几乎必然出现，而其它符号则是几乎不可能出现，那么，这个信源是一个确知信源，其熵为零。,分析： 若Pi=1,PilogPi=0；其他Pj趋于0 ，PjlogPj 趋于0。由罗比塔法则：,因此,38,3、非负性： H(P) 0说明：随机变量X的概率分布满足0pi1，对数

16、函数的底大于1时，log(pi) 0，-pilog(pi ) 0，即得的熵为正值。只有当随机变量是一确知量时熵才等于零。这种非负性合适于离散信源的熵，对连续信源来说这一性质并不存在（基于差熵、相对熵概念）。,非负性体现信息是非负的。,39,4、扩展性,说明：信源的符号数增多时，若这些取值对应的概率很小(接近于零)，则信源的熵不变。,所以，上式成立。,因为,趋于0,40,5、可加性 统计独立信源X和Y的联合信源XY的熵等于信源X和Y各自的熵之和： H(XY) = H(X)+ H(Y) 即：,另外：可加性是熵函数的一个重要特性，正因具有可加性，才能保证熵函数的形式是唯一的。,信源XY的符号联合概率

17、,41,证明：,=1,=1,42,例如，甲信源为,它们的联合信源是,可计算得联合信源的联合熵：H(Z)=H(XY)=log(nm)=log m + log n =H(X) + H(Y),乙信源为,43,6、强可加性 两个互相关联的信源X和Y的联合信源XY的熵等于信源X的熵加上在X已知条件下信源Y的条件熵。H（XY）=H（X）+ H（Y | X）,证明： 设X、Y的概率分布为 X、Y之间存在关联，用条件概率描述：,同时，联合信源XY的各个符号，由X、Y信源中的符号构成，每个联合符号的联合概率为：,44,显然,则,联合概率,45,=1,条件熵,条件熵,46,条件熵： H（Y|X）表示信源 X 输出

18、一符号的条件下，信源Y再输出一符号所能提供的平均信息量。,也即：,由前面的推导，可得：,47,7、递增性,若原信源 X 中有一个符号分割成了m个元素(符号)，这m个元素的概率之和等于原元素的概率，而其他符号的概率不变，则新信源的熵增加。 熵的增加量等于由分割而产生的不确定性量。,48,#（选讲）#证明: 可以从熵的定义或强可加性得出：,49,即得：,50,递增性的推广,它表示n个元素的信源熵可以递推成(n-1)个二元信源的熵函数的加权和。这样，可使多元信源的熵函数的计算简化成计算若干个二元信源的熵函数。因此，熵函数的递增性又可称为递推性。,51,#（选讲）#例：运用熵函数的递增性（的推广），计

19、算熵函数H(1/3，1/3，1/6，1/6)的数值。,52,8、极值性 在离散信源情况下，信源各符号等概率分布时，熵值达到最大。,等概率分布信源的平均不确定性为最大。这是一个重要结论，称为最大离散熵定理。,证明： 因为对数函数是型凸函数，满足詹森不等式 Elog Y log EY，令矢量Y=1/P即（yi=1/pi），则有：,=1,53,特例：二进制离散信源。 该信源符号只有二个，设为“0”和“1”。符号输出的概率分别为“”和“1- ”，即信源的概率空间为：,H(X) = -log (1-) log(1-) =H(),即信息熵H(x)是的函数。取值于0，1区间，可画出熵函数H() 的曲线来，如

20、右图所示。,54,熵函数H(P)是概率矢量P(p1，p2， ，pq)的严格型凸函数(或称上凸函数)。（因为H(P)是由具有严格上凸性的对数函数-xlogx（二阶导数0）的线性组合。）即：对任意概率矢量 P1(p1,p2, ,pq )和 P2 (p1,p2, ,pq)， 和任意的 01，有： H P1+(1- )P2 H(P1)+(1-)H(P2) 因为熵函数具有上凸性，所以熵函数具有极值，其最大值存在。,9、上凸性,55,扩展信源的由来： 当离散无记忆信源信源发出固定长度的消息序列时，则得到原信源的扩展信源。例如：在电报系统中，若信源输出的是二个符号组成的符号序列，此时可认为是一个新的信源，它

21、由四个符号（00，01，10，11）组成，我们把该信源称为二元无记忆信源的二次扩展信源。 更进一步，如果把N个二元符号组成一组，则信源等效成一个具有2N个符号的新信源，把它称为二元无记信源的N次扩展信源。,2.4 离散无记忆的扩展信源,56,概念： 一般地，对一个离散无记忆信源X，其样本空间为a1,a2, ,aq ，对它的输出消息序列，可用一组组长度为N的序列来表示它。这时，它等效成一个新信源。 新信源输出的符号是N维离散随机矢量X =(X1 ，X2 , XN)， 其中每个分量Xi (i1,2,N)都是随机变量，它们都取值于同一信源符号集，并且分量之间统计独立，则由随机矢量X组成的新信源称为离

22、散无记忆信源X的N次扩展信源。,57,单符号离散无记忆信源X的数学模型：,N次扩展信源与单符号离散信源比较，其输出不是单个符号，而是一串N个相互独立的符号序列： X(X1,X2, XN) ， 联合分布密度 P(X)=P(X1X2XN) 它们把 X 等效为一个新信源-X的N次扩展信源。,N次扩展,N次扩展信源,N次扩展信源的数学模型,58,N次扩展信源数学模型表示为：,因为是无记忆的(彼此统计独立)则：,59,性质：离散平稳无记忆N次扩展信源的熵 H(XN) = NH(X),其中：,同理计算式中其余各项，得到：,H(XN) = H(X)+H(X)+H(X)= N H(X),证明：,分解为N重求和

23、,60,一、概念 在一般情况下，信源在 t = i 时刻将要发出什么样的符号决定于两方面： (1) 信源在 t = i 时刻，随机变量Xi 取值的概率分布P(xi)。 一般 P(xi) P(xj) (2) t= i 时刻以前信源发出的符号。 即与条件概率P(xi|xi-1 xi-2)有关平稳随机序列：其统计性质与时间的推移无关，即信源发出符号序列的概率分布与时间起点无关。,2.5 离散平稳信源,61,一维平稳信源： 若当t = i，t = j时 (i,j 是大于1的任意整数)，信源输出的随机序列满足一维概率分布时间起点无关条件 P(xi)=P(xj )=P(x)二维平稳信源： 除满足上述一维平

24、稳信源条件外，如果联合概率分布P(xixi+1)也与时间起点无关，即 P(xixi+1)=P(xjxj+1) (i,j为任意整数且ij) 它表示任何时刻，信源先后发出二个符号的联合概率分布也完全相等。,62,完全平稳信源： 如果各维联合概率分布均与时间起点无关，那么信源是完全平稳的（N为任意正整数）。,由于联合概率与条件概率有以下关系：,63,平稳信源的特点：对于平稳信源发出的随机序列，其前后符号依赖的条件概率均与时间起点无关，只与关联长度N有关。如果某时刻发出什么符号只与前面发出的N个符号有关，那么由平稳性，则任何时刻它们的依赖关系都是一样的。,则由前面两个关系，可推知各维条件概率也满足时间

25、起点无关性：,64,三、离散平稳信源的极限熵对于一般平稳有记忆信源，设其概率空间为：,发出的符号序列为(X1，X2，XN， )，假设信源符号之间的依赖长度为N，且各维概率分布为：,65,且满足完备集条件，各维概率密度之和皆为1：,66,已知联合概率分布，可得离散平稳信源的一系列联合熵：,N长的信源符号序列中平均每符号携带的信息量为：,平均符号熵:,信息度量1平均符号熵,67,另一方面，因信源符号之间的依赖关系长度为N,所以可以求出已知前面N-1个符号时，后面出现一个符号的平均不确定性。条件熵: 若已知前面N一1个符号，后面出现一个符号的平均不确定性（平均信息量），即得一系列的条件熵：,信息度量

26、2条件熵,68,对离散平稳信源，若H1(X) ，则有：1) 条件熵、平均符号熵都随序列长度N的增加是非递增的；2) 对于任意序列长度N，平均符号熵不小于条件熵；3) 极限熵 H 存在，并且等于序列长度N无穷大时的平均符号熵或条件熵。,对于一般平稳信源，求 H相当困难（N取无穷大）。但N不很大时有： H HN(X) 或 H H(XN|X1X2XN-1)。,离散平稳信源性质总结,近似计算,69,对离散二维平稳信源，一维和二维概率分布确定，且与时间推移无关。 对于这样的二维平稳信源，二符号之间的条件概率反映了前面输出某一个符号、后面再输出某一个符号的概率，其输出符号序列中依赖关系是有限的，所以有：,

27、特例分析：离散二维平稳信源,70,联合概率满足完备性,边缘分布概率,另外，可从联合概率得到边缘分布概率：,则条件熵表示为：,71,此时：,可见：离散二维平稳信源的极限熵，等于条件熵 H(X2|X1) 。,N-2维边缘概率,72,推广： 一般情况，如果平稳信源的记忆长度有限，也即某时刻输出什么符号只与前面的m个符号有关。 此时，则可用有限记忆长度的条件熵来测度离散平稳信源的极限熵：,73,第3章 离散信道及其信道容量,第一节 信道的数学模型及分类,第二节 平均互信息,第三节 平均互信息的特性,第四节 信道容量及其计算方法,第五节 离散无记忆扩展信道及其信道容量,第六节 信源与信道的匹配,74,信

28、道的任务： 以信号方式传输信息和存储信息。研究内容： 信道中能够传送或存储的最大信息量，即信道容量。,75,3.1 信道的数学模型和分类,数字通信系统的一般模型,76,二、离散信道的数学模型,条件概率 P(y|x) 描述了输入信号和输出信号之间统计依赖关系，反映了信道的统计特性。根据信道的统计特性的不同，离散信道又可分成3种情况：,1.无干扰信道 2.有干扰无记忆信道 3.有干扰有记忆信道,77,(1)无干扰(无噪声)信道 信道中没有随机性的干扰或者干扰很小，输出符号 y 与输入符号 x 之间有确定的、一 一对应的关系。即：y f (x),78,(2) 有干扰无记忆信道 信道输入和输出之间的条

29、件概率是一般的概率分布。 如果任一时刻输出符号只统计依赖于对应时刻的输入符号，则这种信道称为无记忆信道。,(3) 有干扰(噪声)有记忆信道 实际信道往往是既有干扰(噪声)又有记忆的这种类型。 例如在数字信道中，由于信道滤波频率特性不理想时造成了码字间串扰。 在这一类信道中某一瞬间的输出符号不但与对应时刻的输入符号有关，而且还与此以前其他时刻信道的输入符号及输出符号有关，这样的信道称为有记忆信道。,80,三、单符号离散信道,单符号离散信道特性：输入符号为X，取值于a1,a2, ,ar输出符号为Y，取值于b1,b2, ,bs条件概率：P(y|x)P(y=bj|x=ai)P(bj|ai) 这一组条件

30、概率称为信道的传递概率或转移概率。 信道中有干扰(噪声)存在，可以用传递概率 P(bj|ai) 来描述干扰影响的大小。,81,一般简单的单符号离散信道可用 X, P(y|x) , Y 三者加以表述，其数学模型可以用如下概率空间 X, P(y|x) ,Y也可用图形来描述：,单符号离散信道,82,信道矩阵（转移矩阵）模型 一般离散单符号信道的传递概率可用矩阵形式表示，即,矩阵P完全描述了信道的特性，可用它作为离散单符号信道的另一种数学模型的形式。矩阵 P中元素有些是信道干扰引起的错误概率，有些是信道正确传输的概率。,83,例 二元对称信道，BSC，Binary Symmetrical Channe

31、l,解：此时，X:0,1 ; Y:0,1 ; r=s=2，a1=b1=0；a2=b2=1。传递概率:,是单个符号传输发生错误的概率。（1-p）表示是无错误传输的概率。 转移矩阵:,0 101,84,（1）联合概率,其中,前向概率，描述信道的噪声特性,后向概率（后验概率）,输入符号的先验概率,单符号离散信道的相关概率关系,（2）输出某符号的概率,85,含义： 输出端收到的某符号，必是输入端某一符号输入所致。,（3）后验概率,且,根据贝叶斯定理，可知：,86,3.2 信道疑义度与平均互信息,研究离散单符号信道的信息传输问题。,一、信道疑义度,先验熵：即信道输入信源X的熵,H(X)是在接收到输出Y以

32、前，关于输入变量X的先验不确定性。,87,后验熵： 接收到bj后，关于输入变量X的不确定性。,后验熵是当信道接收端接收到输出符号bj后，关于输入符号的不确定性的信息测度。,88,信道疑义度： 后验熵在输出符号集Y范围内是随机量。对后验熵在符号集Y中求数学期望，即-信道疑义度：,89,互信息量 I(x ; y)： 收到消息y 后获得关于x的信息量，即消除的不确定性量。,互信息量表示先验的不确定性减去尚存的不确定性，是收信者获得的信息量。 若互信息I(x ; y)0，说明在收到信息量y以前对消息x是否出现的不确定性较小；但由于信道噪声的存在，反而使得接收到消息y后，反而对x是否出现的不确定程度增加

33、了。,二、平均互信息,90,平均互信息I(X; Y)：,接收到符号 Y 后, 平均每个符号获得的关于 X 的信息量，体现输入与输出两个随机变量间的统计约束程度。,91,另一角度：平均互信息=通信过程所消除的不确定性：,I(X;Y)是I (x ; y)的统计平均，可以证明I(X;Y)0 。 若I(X;Y) = 0，表示在信道输出端接收到符号后不获得任何关于输入符号的信息。,92,I(X;Y) I(X;Y) = H(X) - H(X|Y) I(X;Y) = H(Y) - H(Y|X) I(X;Y) = H(X) + H(Y) - H(XY)其中：,平均互信息与各类熵的关系,93,维拉图： 可用于各

34、类熵与平均互信息之间关系 H(X|Y) = H(X) - I(X;Y) 损失熵 / 信道疑义度 H(Y|X) = H(Y) - I(X;Y) 噪声熵 / 散布度 H(XY) = H(X)+H(Y)- I(X;Y),H(X),图中，左边的圆代表随机变量X的熵，右边的圆代表随机变量Y的熵，两个圆重叠部分是平均互信息I(X;Y)。每个圆减去I(X;Y)后剩余的部分代表两个疑义度。,94,信息传输率 信道中平均每个符号所能传送的信息量。 而平均互信息I(X;Y)则反映了接收到一符号Y后平均每个符号获得的关于X的信息量。 因此，信息传输率可作如下定义：信息传输率 R R = I(X;Y) = H(X)

35、H(X|Y) (比特/符号),3.4 离散信道的信道容量,信息传输速率Rt ： 信道在单位时间内平均传输的信息量。即信道中平均每秒传输的信息量：,Rt R/t = I(X;Y)/t = H(X)/t H(X|Y)/t （bit/s）,95,一、信道容量由于平均互信息I(X;Y)是输入随机变量的型凸函数 ，所以对一固定的信道，总存在一种信源的输入分布概率，使传输每个符号平均获得的信息量最大。信道容量：对任何一个固定信道，存在一个最大的信息传输率,（比特/符号）,与之相对应的输入分布概率P(X)则称为最佳输入分布。,96,(Bit/s),Ct仍称为信道容量：,若平均传输一个符号需要 t 秒钟，则信

36、道在单位时间内平均传输的最大信息量为Ct：,性质 信道容量与输入信源的概率分布无关，只是信道传输概率的函数，只与信道的统计特性有关。 信道容量是完全描述信道特性的参量，是信道的最大信息传输率。,97,即：,例 二元对称信道容量的计算,因此，二元对称信道的信道容量为：,前述二元对称信道，I(X;Y),(比特符号),98,1.无噪无损信道（无噪一一对应信道）,二、简单离散信道的信道容量,例如：,也即,99,其信道矩阵是单位矩阵：,满足：损失熵H(X|Y)=0、噪声熵H(Y|X)=0，故 I(X;Y)=H(X)=H(Y),则信道容量：,维拉图：,最佳输入分布：等概率分布,100,2.有噪无损信道,信

37、道特点：输入一个符号X对应若干个输出符号Y，且每一个X值所对应的Y值不重合。 输入符号通过传输变换成了若干个输出符号，不满足一一对应关系，但这些输出符号仍可以分成互不相交的一些子集合。,例,101,一旦接收到符号Y后，可消除对X符号的不确定性。分析一下：损失熵H(X|Y)， 噪声熵H(Y|X),信道矩阵特点：除了每行元素之和为1外，每一列中只有一个非零项。表明一个接收符号只对应一个发送符号，而一个发送符号对应多个接收符号，是一对多关系。,102,所以 ： I(X;Y) = H(X) H(X|Y) = H(X)且 I(X;Y) = H(Y) H(Y/X) H(Y) 则 I(X;Y) = H(X)

38、 H(Y),损失熵(信道疑义度)=0：,噪声熵（散布度）0,103,则信道容量为：,最佳输入分布：等概率分布。,维拉图,104,3.无噪有损信道（确定信道）,信道特点：输入X与输出Y之间为多对一关系，接收到符号Y后不能完全消除对X的不确定性。 前向概率 P(y | x) = 0 or 1 后向概率 P(x | y) 0 or 1 可计算损失熵H(X|Y)、噪声熵H(Y|X)。,噪声熵（散布度）=0,损失熵（信道疑义度）0,105,满足： I(X;Y)=H(Y) H(Y/X) = H(Y) I(X;Y)=H(X) H(X/Y) H(X)因此： I(X;Y)=H(Y) H(X),则信道容量为：,输

39、出符号等概率分布时H(Y)最大，且一定可以找到一种输入分布，使得输出符号Y达到等概率分布。,维拉图,106,三类信道特点： 无噪无损信道：损失熵、损失熵皆为0； 无损信道：损失熵H(X|Y)为0，噪声熵不为0； 无噪信道: 噪声熵H(Y|X)为0，损失熵不为0； 这三类信道的信道容量的计算，从求平均互信息的极限问题退化为求信息熵的极值问题。,107,信道特点： 信道矩阵P中每一行都是由同一集合p1，p2，ps 中的诸元素不同排列组成；信道矩阵P每一列也都是由同一集合 q1，q2，qr 中的诸元素不同排列组成。 一般sr。 当r=s，两个集合相同； 若rs，则qi是 pi的子集。,三、对称离散信

40、道的信道容量,例：,对称离散信道,108,非对称离散信道,强对称信道（均匀信道）：若输入/输出符号个数相同，都等于r，且信道矩阵为,特点：总的错误概率为 p ，对称地平均分配给r-1个输出符号。它是对称离散信道的特例。,109,该项是固定Xx 时对Y求和，即对信道矩阵的行求熵。由于是对称信道，所以H(Y/X= x )与 x 无关，为一常数。则,考察：对称离散信道的平均互信息 I(X;Y)=H(Y)-H(Y/X),其中,110,因此对称离散信道的信道容量应为：,可以看出，这是在某种P(x)分布情况下，使得输出等概分布时，即 H(Y)=logs 时的信道容量。,在什么样的信源输入情况下，信道输出等

41、概分布呢？可以证明，输入等概分布时，输出也等概分布： 若输入概率为等概率p(x)=1/r，则,111,因是对称离散信道，信道矩阵的每一列元素之和相等 ：,则有,也就是：信道的输出也是等概分布的：,112,注意：信道容量本身与输入无关；但只有当满足输入的等概分布时，信息传输率才能达到信道容量。,那么对称离散信道的信道容量：,113,在这个信道中，每个符号平均能够传输的最大信息为0.0817比特。,例 某对称离散信道的信道矩阵如下，求其信道容量。,解：s=4, r=2,114,特例：对于二元对称信道,这个式子很重要。,特例：对于强对称信道，其信道容量为：,115,信道容量计算步骤 当信道矩阵P是非

42、奇异矩阵，信道容量计算过程：1）计算j2）计算信道容量C 3）计算输出分布概率P(bj)4）计算输入分布概率P(ai),116,例 离散无记忆信道,不是对称信道。r=s=4,信道矩阵非奇异。利用：,117,则有,计算信道容量,计算输出概率分布,可得,118,计算最佳输入分布,根据方程组求解输入分布,可得：,119,3.5 离散无记忆信道的扩展信道,对于离散无记忆信道 ( DMC，Discrete Memoryless Channel) ，其传递概率满足：,可用 X，P( y / x )，Y 概率空间来描述。设离散无记忆信道的输入符号集Aa1， ， ar，输出符号集Bb1 ， ， bs，信道矩阵

43、为:,120,则此无记忆信道的N次扩展信道的数学模型如图所示:,而信道矩阵：,其中：,121,例 求二元无记忆对称信道（BSC）的二次扩展信道。解：BSC的输入和输出变量X和Y的取值都是0或1，因此，二次扩展信道的输入符号集为A00，01，10，11，共有224个符号，输出符号集为B 00，01，10，11。由于是无记忆信道，可求得二次扩展信道的传递概率：,信道矩阵：,122,考察：无记忆信道的N次扩展信道的平均互信息,123,定理3.5：对于一般离散信道，若信道的输入随机序列为X= (X1X2XN)，通过信道传输，接收到的随机序列为Y(Y1Y2YN)。其中，Xi ，Yi是对应第 i 时刻的随

44、机变量。1）假若信道是无记忆的，即信道传递概率满足：,2）假若输入信源是无记忆的，即满足,3）若信道和信源都是无记忆的，则：,124,无记忆N次扩展信道的平均互信息 1）信道的输入序列 X= (X1X2XN)中的随机变量 Xi 取自于同一信源符号集，并且具有同一种概率分布; 2）通过相同的信道传输到输出端（信道传递概率不随 i 改变）随机向量Y= (Y1Y2YN)中随机变量Yi也取自同一符号集，则,由定理3.5，无记忆信道的N次扩展信道若信源也是无记忆的，则：,说明：信源无记忆时，无记忆的N次扩展信道的平均互信息等于原信道的平均互信息的N倍。,125,无记忆N次扩展信道的信道容量 一般的离散无

45、记忆信道的N次扩展信道的信道容量是,某时刻 i 通过DMC传输的最大信息量,信道的输入随机序列X= (X1X2XN)在同一信道中传输，故Ci=C,一般情况下，消息序列在离散无记忆的N次扩展信道中传输的信息量： I（X;Y） NC 信道容量在信源是无记忆信源且每一个输入变量Xi达到最佳分布时达到。,126,3.8 信源与信道的匹配,在一般情况下，当信源与信道相连接时，其信息传输率并未达到最大。若使信息传输率能达到或尽可能接近于信道容量，只有在信源取最佳分布时才能实现。 “匹配” 当信道确定后，信道的实际信息传输率与信源分布是密切相关的。当达到信道容量时，称信源与信道达到匹配，否则认为信道有剩余。

46、,127,信道剩余度,相对信道剩余度,信道的实际信息传输率和信道传输能力之差。,可以用来衡量信道利用率的高低。,特例 在无损信道中，信道容量 Clogr (r是信道输入符号数)。而I(X;Y)H(X)，因而： 信道的相对剩余度 = = 信源的剩余度,128,意 义 提高无损信道的信息传输率，就等于减少信源的剩余度。对于无损信道，可通过信源编码，减少信源剩余度，使信息传输率达到信道容量。 因此在通信系统中，应将信源发出的符号转换成适合信道传输的符号，从而使信源与信道匹配。,例 某离散无记忆信源,通过一个无噪无损二元离散信道进行传输。,129,分析： 此二元信道的信道容量为： C1 (比特信道符号

47、) 信源的信息熵为 H(X)1.937 (比特信源符号)要使多符号信源在此二元信道传输，须对X进行二元编码：,对于码,(比特信道符号),对于码,(比特信道符号),信道有剩余。因此，必须通过合适的信源编码，使信道的信息传输率接近或等于信道容量。,130,第5章 无失真信源编码定理,第一节 编码器,第二节 等长码,第五节 变长信源编码定理,第三节 等长信源编码定理,第四节 变长码,131,信息通过信道传输到信宿的过程。要做到既不失真又快速地通信，需要解决两个问题：信源编码: 在不失真或允许一定失真条件下，提高信息传输率.信道编码: 在信道受到干扰的情况下，增加信号的抗干扰能力，同时又使得信息传输率

48、最大.最佳编码： 一般来说，抗干扰能与信息传输率二者相互矛盾。而编码定理理论上证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。信源编码： 信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的就是要减少冗余，提高编码效率。,引 言,132,研究方法研究信源编码时，将信道编码与译码看成是信道的一部分，从而突出信源编码；研究信道编码时，将信源编码与译码看成是信源与信宿的一部分，从而突出信道编码。,5.1 编码器,编码器： 对信源的符号按一定的数学规则进行的变换。 它可以看作这样一个系统，它的输入端为原始信源S

49、，其符号集为 而信道所能传输的符号集为,133,编码器功能：用符号集X中的元素，将原始信源的符号 变换为相应的码字符号 ，编码器输出符号集为 (码或码书) 称为码字，li 为码字 的码元个数（码字长度，码长）。码字集合C称为码或码书。,134,若要实现无失真编码，这种映射应是一一对应的可逆映射。,编码的形式化描述： 从信源符号到码符号的一种映射,或：,135,6、唯一可译码(单义可译码） 由码构成的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列。 否则,就为非惟一可译码或非单义可译码。,例：对于二元码 ，当任意给定一串码字序列，例如10001101只可唯一地划分为1,00,01

50、,1,01，因此是惟一可译码；而对另一个二元码 ，当码字序列为01001可划分为0,10,01或01,0,01，所以是非惟一可译的。,136,唯一可译码的条件 1）不同的信源符号变换成不同的码字(非奇异码)； 2）任意有限长的信源序列所对应的码元序列各不相同. 即: 码的任意有限长N次扩展码都是非奇异码。Or: 码符号序列的反变换也唯一的（扩展码非奇异） 原因： 若要使某一码为惟一可译码，则对于任意有限长的码符号序列，必须只能被惟一地分割成一个个的码字，才能实现唯一的译码。,137,无失真的编码的一般条件 1）码字与信源符号之间一一对应（非奇异码）； 2）码符号序列的反变换也唯一的（扩展码非奇