信息论与编码(第三版).ppt

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）互信息 先验的不确定性减去尚存的不确定性。 后验

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

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

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

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

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

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

9、： 独立P(X)= P(X1, X2, ,XN)= P1(X1) P2(X2) PN(XN) 平稳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重空间：

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

11、起点 i 无关，信源输出的符号序列可看成为时齐马尔可夫链，则此信源称为时齐马尔可夫信源。,27,2.2 离散信源的信息熵,基本的离散信源： 输出单符号消息，且这些消息间两两互不相容。用一维随机变量X来描述信源的输出，其数学模型可抽象为:,问题：这样的信源能输出多少信息? 每个消息的出现携带多少信息量?,28,信息的度量,要点： 信息的度量（信息量）和不确定性消除的程度有关，消除的不确定性获得的信息量； 不确定性就是随机性，可以用概率论和随机过程来测度； 推论： 概率小信息量大，即信息量是概率的单调递减函数； 信息量应该具有可加性； 信息量的计算公式为（香农（自）信息量的度量）：,29,2.1.

12、1 自信息,设离散信源X的概率空间为：,I(ai)代表两种含义： （1）当事件ai发生以前，表示事件ai发生的不确定性 （2）当事件ai发生以后，表示事件ai所提供的信息量,自信息量：事件ai发生所含有的信息量,30,度量单位,计算自信息量时要注意有关事件发生概率的计算； 自信息量的单位取决于对数的底； 底为2，单位为“比特（bit, binary unit）”； 底为e，单位为“奈特（nat, nature unit）”； 底为10，单位为“哈特（hat, Hartley）”； 根据换底公式得：,一般计算都采用以“2”为底的对数，为了书写简洁，常把底数“2”略去不写,1 nat = 1.44

13、bit , 1 hat = 3.32 bit；,31,收信者收到某消息获得的信息量 不确定性减少的量 (收到此消息前关于某事件的不确定性) - (收到此消息后关于某事件的不确定性) 通信的实质？ 即：传递信息，消除不确定性。,32,2.2.2 信息熵,对一个信源发出不同消息所含有的信息量也不同。所以自信息I(ai)是一个随机变量，不能用它来作为整个信源的信息测度。 信息熵：自信息的数学期望，平均自信息量Hr(X)：,r进制单位/符号,33,熵的含义,熵是从整个集合的统计特性来考虑的，它从平均意义上来表征信源的总体特征。 信源输出前，熵H(X)表示信源的平均不确定性； 信源输出后，熵H(X)表示

14、每个消息的平均信息量； 信息熵H(X)表征了变量X的随机性。,34,信息熵是信源概率空间的一种特殊函数。这个函数的取值大小，与信源的符号数及其概率分布有关。 用概率矢量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个符号信源的信息

15、熵。 若当 q =2 时，因为 p1+p2 = 1, 所以将两个符号的熵函数写成H(p1)或H(p2)。 熵函数H(P)是一种特殊函数，具有以下性质。,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,Pil

16、ogPi=0；其他Pj趋于0 ，PjlogPj 趋于0。由罗比塔法则：,因此,38,3、非负性： H(P) 0 说明： 随机变量X的概率分布满足0pi1，对数函数的底大于1时，log(pi) 0，-pilog(pi ) 0，即得的熵为正值。只有当随机变量是一确知量时熵才等于零。 这种非负性合适于离散信源的熵，对连续信源来说这一性质并不存在（基于差熵、相对熵概念）。,非负性体现信息是非负的。,39,4、扩展性,说明：信源的符号数增多时，若这些取值对应的概率很小(接近于零)，则信源的熵不变。,所以，上式成立。,因为,趋于0,40,5、可加性 统计独立信源X和Y的联合信源XY的熵等于信源X和Y各自的

17、熵之和： H(XY) = H(X)+ H(Y) 即：,另外：可加性是熵函数的一个重要特性，正因具有可加性， 才能保证熵函数的形式是唯一的。,信源XY的符号联合概率,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

18、的各个符号，由X、Y信源中的符号构成，每个联合符号的联合概率为：,44,显然,则,联合概率,45,=1,条件熵,条件熵,46,条件熵： H（Y|X）表示信源 X 输出一符号的条件下，信源Y再输出一符号所能提供的平均信息量。,也即：,由前面的推导，可得：,47,7、递增性,若原信源 X 中有一个符号分割成了m个元素(符号)，这m个元素的概率之和等于原元素的概率，而其他符号的概率不变，则新信源的熵增加。 熵的增加量等于由分割而产生的不确定性量。,48,#（选讲）# 证明: 可以从熵的定义或强可加性得出：,49,即得：,50,递增性的推广,它表示n个元素的信源熵可以递推成(n-1)个二元信源的熵函数

19、的加权和。这样，可使多元信源的熵函数的计算简化成计算若干个二元信源的熵函数。因此，熵函数的递增性又可称为递推性。,51,#（选讲）# 例：运用熵函数的递增性（的推广），计算熵函数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”。符号输出的概率分别为“”和

20、“1- ”，即信源的概率空间为：,H(X) = -log (1-) log(1-) =H(),即信息熵H(x)是的函数。 取值于0，1区间，可画出熵函数H() 的曲线来，如右图所示。,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、上凸性,5

21、5,扩展信源的由来： 当离散无记忆信源信源发出固定长度的消息序列时，则得到原信源的扩展信源。 例如：在电报系统中，若信源输出的是二个符号组成的符号序列，此时可认为是一个新的信源，它由四个符号（00，01，10，11）组成，我们把该信源称为二元无记忆信源的二次扩展信源。 更进一步，如果把N个二元符号组成一组，则信源等效成一个具有2N个符号的新信源，把它称为二元无记信源的N次扩展信源。,2.4 离散无记忆的扩展信源,56,概念： 一般地，对一个离散无记忆信源X，其样本空间为a1,a2, ,aq ，对它的输出消息序列，可用一组组长度为N的序列来表示它。这时，它等效成一个新信源。 新信源输出的符号是N

22、维离散随机矢量 X =(X1 ，X2 , XN)， 其中每个分量Xi (i1,2,N)都是随机变量，它们都取值于同一信源符号集，并且分量之间统计独立，则由随机矢量X组成的新信源称为离散无记忆信源X的N次扩展信源。,57,单符号离散无记忆信源X的数学模型：,N次扩展信源与单符号离散信源比较，其输出不是单个符号，而是一串N个相互独立的符号序列： X(X1,X2, XN) ， 联合分布密度 P(X)=P(X1X2XN) 它们把 X 等效为一个新信源-X的N次扩展信源。,N次扩展,N次扩展信源,N次扩展信源的数学模型,58,N次扩展信源数学模型表示为：,因为是无记忆的(彼此统计独立)则：,59,性质：

23、离散平稳无记忆N次扩展信源的熵 H(XN) = NH(X),其中：,同理计算式中其余各项，得到：,H(XN) = H(X)+H(X)+H(X)= N H(X),证明：,分解为N重求和,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,一维平稳信源

24、： 若当t = i，t = j时 (i,j 是大于1的任意整数)，信源输出的随机序列满足一维概率分布时间起点无关条件 P(xi)=P(xj )=P(x) 二维平稳信源： 除满足上述一维平稳信源条件外，如果联合概率分布P(xixi+1)也与时间起点无关，即 P(xixi+1)=P(xjxj+1) (i,j为任意整数且ij) 它表示任何时刻，信源先后发出二个符号的联合概率分布也完全相等。,62,完全平稳信源： 如果各维联合概率分布均与时间起点无关，那么信源是完全平稳的（N为任意正整数）。,由于联合概率与条件概率有以下关系：,63,平稳信源的特点： 对于平稳信源发出的随机序列，其前后符号依赖的条件概

25、率均与时间起点无关，只与关联长度N有关。 如果某时刻发出什么符号只与前面发出的N个符号有关，那么由平稳性，则任何时刻它们的依赖关系都是一样的。,则由前面两个关系，可推知各维条件概率也满足时间起点无关性：,64,三、离散平稳信源的极限熵 对于一般平稳有记忆信源，设其概率空间为：,发出的符号序列为(X1，X2，XN， )，假设信源符号之间的依赖长度为N，且各维概率分布为：,65,且满足完备集条件，各维概率密度之和皆为1：,66,已知联合概率分布，可得离散平稳信源的一系列联合熵：,N长的信源符号序列中平均每符号携带的信息量为：,平均符号熵:,信息度量1平均符号熵,67,另一方面，因信源符号之间的依赖

26、关系长度为N, 所以可以求出已知前面N-1个符号时，后面出现一个符号的平均不确定性。 条件熵: 若已知前面N一1个符号，后面出现一个符号的平均不确定性（平均信息量），即得一系列的条件熵：,信息度量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章

28、离散信道及其信道容量,第一节 信道的数学模型及分类,第二节 平均互信息,第三节 平均互信息的特性,第四节 信道容量及其计算方法,第五节 离散无记忆扩展信道及其信道容量,第六节 信源与信道的匹配,74,信道的任务： 以信号方式传输信息和存储信息。 研究内容： 信道中能够传送或存储的最大信息量，即信道容量。,75,3.1 信道的数学模型和分类,数字通信系统的一般模型,76,二、离散信道的数学模型,条件概率 P(y|x) 描述了输入信号和输出信号之间统计依赖关系，反映了信道的统计特性。根据信道的统计特性的不同，离散信道又可分成3种情况：,1.无干扰信道 2.有干扰无记忆信道 3.有干扰有记忆信道,7

29、7,(1)无干扰(无噪声)信道 信道中没有随机性的干扰或者干扰很小，输出符号 y 与输入符号 x 之间有确定的、一 一对应的关系。即： y f (x),78,(2) 有干扰无记忆信道 信道输入和输出之间的条件概率是一般的概率分布。 如果任一时刻输出符号只统计依赖于对应时刻的输入符 号，则这种信道称为无记忆信道。,(3) 有干扰(噪声)有记忆信道 实际信道往往是既有干扰(噪声)又有记忆的这种类型。 例如在数字信道中，由于信道滤波频率特性不理想时造成了码字间串扰。 在这一类信道中某一瞬间的输出符号不但与对应时刻的输入符号有关，而且还与此以前其他时刻信道的输入符号及输出符号有关，这样的信道称为有记忆

30、信道。,80,三、单符号离散信道,单符号离散信道特性： 输入符号为X，取值于a1,a2, ,ar 输出符号为Y，取值于b1,b2, ,bs 条件概率：P(y|x)P(y=bj|x=ai)P(bj|ai) 这一组条件概率称为信道的传递概率或转移概率。 信道中有干扰(噪声)存在，可以用传递概率 P(bj|ai) 来描述干扰影响的大小。,81,一般简单的单符号离散信道可用 X, P(y|x) , Y 三者加以表述，其数学模型可以用如下概率空间 X, P(y|x) ,Y 也可用图形来描述：,单符号离散信道,82,信道矩阵（转移矩阵）模型 一般离散单符号信道的传递概率可用矩阵形式表示，即,矩阵P完全描述

31、了信道的特性，可用它作为离散单符号信道的另一种数学模型的形式。矩阵 P中元素有些是信道干扰引起的错误概率，有些是信道正确传输的概率。,83,例 二元对称信道，BSC，Binary Symmetrical Channel,解：此时，X:0,1 ; Y:0,1 ; r=s=2，a1=b1=0；a2=b2=1。 传递概率:,p是单个符号传输发生错误的概率。 （1-p）表示是无错误传输的概率。 转移矩阵:,0 1 0 1,84,（1）联合概率,其中,前向概率，描述信道的噪声特性,后向概率（后验概率）,输入符号的先验概率,单符号离散信道的相关概率关系,（2）输出某符号的概率,85,含义： 输出端收到的某

32、符号，必是输入端某一符号输入所致。,（3）后验概率,且,根据贝叶斯定理，可知：,86,3.2 信道疑义度与平均互信息,研究离散单符号信道的信息传输问题。,一、信道疑义度,先验熵：即信道输入信源X的熵,H(X)是在接收到输出Y以前，关于输入变量X的先验不确定性。,87,后验熵： 接收到bj后，关于输入变量X的不确定性。,后验熵是当信道接收端接收到输出符号bj后，关于输入符号的不确定性的信息测度。,88,信道疑义度： 后验熵在输出符号集Y范围内是随机量。对后验熵在符号集Y中求数学期望，即-信道疑义度：,89,互信息量 I(x ; y)： 收到消息y 后获得关于x的信息量，即消除的不确定性量。,互信

33、息量表示先验的不确定性减去尚存的不确定性，是收信者获得的信息量。 若互信息I(x ; y)0，说明在收到信息量y以前对消息x是否出现的不确定性较小；但由于信道噪声的存在，反而使得接收到消息y后，反而对x是否出现的不确定程度增加了。,二、平均互信息,90,平均互信息I(X; Y)：,接收到符号 Y 后, 平均每个符号获得的关于 X 的信息量，体现输入与输出两个随机变量间的统计约束程度。,91,另一角度：平均互信息=通信过程所消除的不确定性：,I(X;Y)是I (x ; y)的统计平均，可以证明I(X;Y)0 。 若I(X;Y) = 0，表示在信道输出端接收到符号后不获得任何关于输入符号的信息。,

34、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,维拉图： 可用于各类熵与平均互信息之间关系 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)后剩余的部分代表两个疑义

35、度。,94,信息传输率 信道中平均每个符号所能传送的信息量。 而平均互信息I(X;Y)则反映了接收到一符号Y后 平均每个符号获得的关于X的信息量。 因此，信息传输率可作如下定义： 信息传输率 R R = I(X;Y) = H(X) 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)是输入随机变量的型凸函数 ，所以对一固定的信道，总存在一种信源的输入分布概率，使传输每个

36、符号平均获得的信息量最大。 信道容量：对任何一个固定信道，存在一个最大的信息传输率,（比特/符号）,与之相对应的输入分布概率P(X)则称为最佳输入分布。,96,(Bit/s),Ct仍称为信道容量：,若平均传输一个符号需要 t 秒钟，则信道在单位时间内平均传输的最大信息量为Ct：,性质 信道容量与输入信源的概率分布无关，只是信道传输概率的函数，只与信道的统计特性有关。 信道容量是完全描述信道特性的参量，是信道的最大信息传输率。,97,即：,例 二元对称信道容量的计算,因此，二元对称信道的信道容量为：,前述二元对称信道，I(X;Y),(比特符号),98,1.无噪无损信道（无噪一一对应信道）,二、简

37、单离散信道的信道容量,例如：,也即,99,其信道矩阵是单位矩阵：,满足：损失熵H(X|Y)=0、噪声熵H(Y|X)=0，故 I(X;Y)=H(X)=H(Y),则信道容量：,维拉图：,最佳输入分布：等概率分布,100,2.有噪无损信道,信道特点：输入一个符号X对应若干个输出符号Y，且每一个X值所对应的Y值不重合。 输入符号通过传输变换成了若干个输出符号，不满足一一对应关系，但这些输出符号仍可以分成互不相交的一些子集合。,例,101,一旦接收到符号Y后，可消除对X符号的不确定性。分析一下： 损失熵H(X|Y)， 噪声熵H(Y|X),信道矩阵特点：除了每行元素之和为1外，每一列中只有一个非零项。表明

38、一个接收符号只对应一个发送符号，而一个发送符号对应多个接收符号，是一对多关系。,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) 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)、噪

39、声熵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),则信道容量为：,输出符号等概率分布时H(Y)最大，且一定可以找到一种输入分布，使得输出符号Y达到等概率分布。,维拉图,106,三类信道特点： 无噪无损信道：损失熵、损失熵皆为0； 无损信道：损失熵H(X|Y)为0，噪声熵不为0； 无噪信道: 噪声熵H(Y|X)为0，损失熵不为0； 这三类信道的信道容量的计算，从求平均互信息的极限问题退化为求信息熵的极值问题。,107,信道特

40、点： 信道矩阵P中每一行都是由同一集合p1，p2，ps 中的诸元素不同排列组成；信道矩阵P每一列也都是由同一集合 q1，q2，qr 中的诸元素不同排列组成。 一般sr。 当r=s，两个集合相同； 若rs，则qi是 pi的子集。,三、对称离散信道的信道容量,例：,对称离散信道,108,非对称离散信道,强对称信道（均匀信道）：若输入/输出符号个数相同，都等于r，且信道矩阵为,特点：总的错误概率为 p ，对称地平均分配给r-1个输出符号。它是对称离散信道的特例。,109,该项是固定Xx 时对Y求和，即对信道矩阵的行求熵。由于是对称信道，所以H(Y/X= x )与 x 无关，为一常数。则,考察：对称离

41、散信道的平均互信息 I(X;Y)=H(Y)-H(Y/X),其中,110,因此对称离散信道的信道容量应为：,可以看出，这是在某种P(x)分布情况下，使得输出等概分布时，即 H(Y)=logs 时的信道容量。,在什么样的信源输入情况下，信道输出等概分布呢？可以证明，输入等概分布时，输出也等概分布： 若输入概率为等概率p(x)=1/r，则,111,因是对称离散信道，信道矩阵的每一列元素之和相等 ：,则有,也就是：信道的输出也是等概分布的：,112,注意： 信道容量本身与输入无关；但只有当满足输入的等概分布时，信息传输率才能达到信道容量。,那么对称离散信道的信道容量：,113,在这个信道中，每个符号平

42、均能够传输的最大信息为0.0817比特。,例 某对称离散信道的信道矩阵如下，求其信道容量。,解：s=4, r=2,114,特例：对于二元对称信道,这个式子很重要。,特例：对于强对称信道，其信道容量为：,115,信道容量计算步骤 当信道矩阵P是非奇异矩阵，信道容量计算过程： 1）计算j 2）计算信道容量C 3）计算输出分布概率P(bj) 4）计算输入分布概率P(ai),116,例 离散无记忆信道,不是对称信道。r=s=4, 信道矩阵非奇异。利用：,117,则有,计算信道容量,计算输出概率分布,可得,118,计算最佳输入分布,根据方程组求解输入分布,可得：,119,3.5 离散无记忆信道的扩展信道

43、,对于离散无记忆信道 ( DMC，Discrete Memoryless Channel) ，其传递概率满足：,可用 X，P( y / x )，Y 概率空间来描述。 设离散无记忆信道的 输入符号集Aa1， ， ar， 输出符号集Bb1 ， ， bs，信道矩阵为:,120,则此无记忆信道的N次扩展信道的数学模型如图所示:,而信道矩阵：,其中：,121,例 求二元无记忆对称信道（BSC）的二次扩展信道。 解：BSC的输入和输出变量X和Y的取值都是0或1，因此，二次扩展信道的输入符号集为A00，01，10，11，共有224个符号，输出符号集为B 00，01，10，11。 由于是无记忆信道，可求得二次

44、扩展信道的传递概率：,信道矩阵：,122,考察：无记忆信道的N次扩展信道的平均互信息,123,定理3.5：对于一般离散信道，若信道的输入随机序列为X= (X1X2XN)，通过信道传输，接收到的随机序列为Y(Y1Y2YN)。其中，Xi ，Yi是对应第 i 时刻的随机变量。 1）假若信道是无记忆的，即信道传递概率满足：,2）假若输入信源是无记忆的，即满足,3）若信道和信源都是无记忆的，则：,124,无记忆N次扩展信道的平均互信息 1）信道的输入序列 X= (X1X2XN)中的随机变量 Xi 取自于同一信源符号集，并且具有同一种概率分布; 2）通过相同的信道传输到输出端（信道传递概率不随 i 改变）

45、随机向量Y= (Y1Y2YN)中随机变量Yi也取自同一符号集，则,由定理3.5，无记忆信道的N次扩展信道 若信源也是无记忆的，则：,说明：信源无记忆时，无记忆的N次扩展信道的平均互信息等于原信道的平均互信息的N倍。,125,无记忆N次扩展信道的信道容量 一般的离散无记忆信道的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,意 义 提高无损信道的信息传输率，就等于减少信源的剩余度。对于无损信道，

47、可通过信源编码，减少信源剩余度，使信息传输率达到信道容量。 因此在通信系统中，应将信源发出的符号转换成适合信道传输的符号，从而使信源与信道匹配。,例 某离散无记忆信源,通过一个无噪无损二元离散信道进行传输。,129,分析： 此二元信道的信道容量为： C1 (比特信道符号) 信源的信息熵为 H(X)1.937 (比特信源符号) 要使多符号信源在此二元信道传输，须对X进行二元编码：,对于码,(比特信道符号),对于码,(比特信道符号),信道有剩余。因此，必须通过合适的信源编码，使信道的信息传输率接近或等于信道容量。,130,第5章 无失真信源编码定理,第一节 编码器,第二节 等长码,第五节 变长信源

48、编码定理,第三节 等长信源编码定理,第四节 变长码,131,信息通过信道传输到信宿的过程。要做到既不失真又快速地通信，需要解决两个问题： 信源编码: 在不失真或允许一定失真条件下，提高信息传输率. 信道编码: 在信道受到干扰的情况下，增加信号的抗干扰能力，同时又使得信息传输率最大. 最佳编码： 一般来说，抗干扰能与信息传输率二者相互矛盾。而编码定理理论上证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。 信源编码： 信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的就是要减少冗余，提高编码效率。,引 言

49、,132,研究方法 研究信源编码时，将信道编码与译码看成是信道的一部分，从而突出信源编码； 研究信道编码时，将信源编码与译码看成是信源与信宿的一部分，从而突出信道编码。,5.1 编码器,编码器： 对信源的符号按一定的数学规则进行的变换。 它可以看作这样一个系统，它的输入端为原始信源S，其符号集为 而信道所能传输的符号集为,133,编码器功能：用符号集X中的元素，将原始信源的符号 变换为相应的码字符号 ，编码器输出符号集为 (码或码书) 称为码字，li 为码字 的码元个数（码字长度，码长）。码字集合C称为码或码书。,134,若要实现无失真编码，这种映射应是一一对应的可逆映射。,编码的形式化描述：

50、 从信源符号到码符号的一种映射,或：,135,6、唯一可译码(单义可译码） 由码构成的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列。 否则,就为非惟一可译码或非单义可译码。,例：对于二元码 ，当任意给定一串码字序列，例如 10001101 只可唯一地划分为1,00,01,1,01，因此是惟一可译码； 而对另一个二元码 ，当码字序列为 01001 可划分为0,10,01或01,0,01，所以是非惟一可译的。,136,唯一可译码的条件 1）不同的信源符号变换成不同的码字(非奇异码)； 2）任意有限长的信源序列所对应的码元序列各不相同. 即: 码的任意有限长N次扩展码都是非奇异码。

51、 Or: 码符号序列的反变换也唯一的（扩展码非奇异） 原因： 若要使某一码为惟一可译码，则对于任意有限长的码符号序列，必须只能被惟一地分割成一个个的码字，才能实现唯一的译码。,137,无失真的编码的一般条件 1）码字与信源符号之间一一对应（非奇异码）； 2）码符号序列的反变换也唯一的（扩展码非奇异）。 即：编码必须是唯一可译码。否则，就会引起译码的错误与失真。 等长码是唯一可译码的条件 若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。 因此，等长非奇异码字一定是唯一可译码,因为采用固定长度划分码字序列.,5.2 等长码,138,1）若对每个信源符号进行等长编码，则必须满足: 其

52、中: l是码长，r是码符号集的码元数，q信源符号数。,2）若对信源的N次扩展信源进行编码，必须满足:,表示平均每个信源符号所需的码符号个数。,即,为了使等长码为非奇异码（唯一可译码），那么:,139,例证：根据依赖关系，信源符号平均所需码符号数可减少。 例 设信源,而其依赖关系为：,1）若不考虑符号间的依赖关系，可得每符号码长l2； 2）若考虑符号间的二元依赖关系，可作二次扩展信源进行分析。根据条件概率仅有4项的概率不为零，可得扩展信源的码长 l=2，而每个信源符号的平均码长为 l/N=1 。,140,5.3 等长信源编码定理,给出了等长信源编码所需码长的极限值。,定理 等长信源编码定理 一熵

53、为H(S)的离散无记忆信源，若对其N次扩展信源进行等长 r 元编码，码长为l，对于任意 大于0，只要满足,当N足够大时，则可以实现几乎无失真编码，反之，若：,则不可能实现无失真编码，当N趋向于无穷大时，译码错误率接近于1。,141,1、唯一可译变长码,5.4 变长码,优势：容易实现效率很高的编码。,变长码也必须是唯一可译码，才能实现无失真编码。,码1是一个奇异码，故不是唯一可译码； 码2也不是唯一可译码，因为收到一串序列，无法唯一译出对应的原符号序列，如01000，即可译作s4s3s1,也可译作s4s1s3,s1s2s3或s1s2s1s1；,142,因此，对于码C： 若其为唯一可译码，则必为非

54、奇异码； 若其为即时码，则必是唯一可译码；反之，作为唯一可译码，则不一定是即时码。,所有的码,非奇异码,唯一可译码,即时码（非延长码）,143,2、即时码（非延时码）的树图构造法,对于给定码字集合C，可用码树来描述。 同时，树图法可构造即时码。,144,非即时码的树图 中间节点安排为码字,1.树图中间节点不作为码字； 2.一旦某节点作为码字，则 不再继续进行分枝。 这样可保证每个码字不同，且满足前缀条件码的条件。,一般编码方法 选择相应节点作为码字：不同的路径上的分支，对应了相应的码元符号，则可得到所编码字。,构造即时码,145,译码方法 因为每一码元对应于一个的树图分枝路径，则即时码的树图可

55、以用来译码。译码器系统对一串符号序列译码过程： 1）首先从树根出发，根据接收的第一个码元符号来选择应走的第一条路径； 2）若沿着所选路径走到某中间节点，再根据接收的第二个码元符号来选择第二条路经； 3）若又走到中间节点，再依次继续选择路径，直到终端节点为止。这时，可根据所经历的枝路，判断出所接收的码字。 4）重新返回树根，再作下一个接收码字的判断。 这样，便可将接收到的一串码符号序列译成信源符号序列。,146,3、克拉夫特（Kraft）不等式,定理 对于码符号为 的任意r元即时码 ，若所对应的码长 ， 则必定满足： 反之，若码长满足上式，则一定存在这样的即时码 。,*可以证明，对于唯一可译码也

56、须满足Kraft不等式。,这说明，其他唯一可译码并不比即时码占优。 而即时码很容易用树图法构造，所以在讨论唯一可译码时，只需要讨论即时码就可以了。,定理 若存在一个码长为 的唯一可译码，则一定存在一个同样长度的即时码。,147,例：设二进制码树中X=(a1 , a2 , a3 , a4), L1=1, L2=2,L3=2,L4=3,应用Kraft不等式,得：,不存在满足这种Li的唯一可译码,如果将各码字长度改成L1=1,L2=2,L3=3,L4=3,则,存在满足这种Li唯一可译码,码树,148,设信源,编码后的码字为：,码长为：,码的平均长度（平均码长）为：,5.5 变长信源编码定理,（码符号

57、/信源符号）,码的平均长度,信息传输率（码率）： 平均每个码元携带的信息量，即编码后信道的信息传输率：,（比特/码符号）,149,若信道传输一个码符号平均需要t秒钟，则编码后信道的每秒传输的信息量为：,（比特/秒）,由此可见： 平均码长越短，信息传输效率越高。,紧致码（最佳码） 对于某一信源和某一个码符号集合，若有一个唯一可译码，它的平均码长小于其他唯一可译码的长度。 无失真信源编码的基本问题就是寻找紧致码。,150,定理 若对一熵为H(S)的离散无记忆信源 S 进行r 元编码，则总是可以找到一种无失真编码方法构成唯一可译码，使其平均码长满足：,说明： 下界：平均码长不能小于极限H(s)/lo

58、gr,否则唯一可译码不存在。 上界：给出了平均码长的上界。但并不是说大于这个上界就不能构成唯一可译码。而是说在上界范围内，可找到唯一可译码。,151,无失真变长信源编码定理（香农第一定理） 离散无记忆信源S的N次扩展信源 ，其熵为 ，且编码器码元符号集为 . 对信源 进行编码，总可以找到一种编码方法，构成唯一可译码，使信源S中每个信源符号si所需要的平均码长 满足,当 则得：,152,定理含义： 要做到无失真信源编码，变换每个信源符号平均所需最少的r元码元数是信源的熵值。 若编码的平均码长小于信源的熵，则唯一可译码不存在，在译码时必然带来失真或差错。 同时，通过对扩展信源进行变长编码，当扩展长度N足够大时，平均码长可达到此极限值。 信源的