信息论-复习资料(傅祖芸版本).ppt

信息论与编码,计算器,2,简介,是一门应用概率论、随机过程、数理统计和近代代数的方法，来研究信息传输、提取和处理中一般规律的学科。,奠基人：美国数学家香农（C.E.Shannon）1948年“通信的数学理论”,3,简介,信息论的基本问题信息的度量无失真信源编码定理香农第一定理信道编码定理香农第二定理信源编码、信道编码,绪论,第1章,5,1.1信息的概念,6,情报：是人们对于某个特定对象所见、所闻、所理解而产生的知识。知识：一种具有普遍和概括性质的高层次的信息，以实践为基础，通过抽象思维，对客观事物规律性的概括。消息：用文字、符号、语音、图像等能够被人们感觉器官所感知的形式，把客观物质运动和主观思维活动的状态表达出来。,几个常见概念,7,香农信息的度量,（1）样本空间某事物各种可能出现的不同状态。（2）概率测度对每一个可能选择的消息指定一个概率。（3）概率空间先验概率p(xi)：选择符号xi作为消息的概率。,样本空间概率测度,8,例：气象预报甲乙,“甲地晴”比“乙地晴”的不确定性小。某一事物状态出现的概率越小，其不确定性越大。某一事物状态出现的概率接近于1,即预料中肯定会出现的事件，那它的不确定性就接近于零。,9,对xi的不确定性可表示为先验概率p(xi)的倒数的某一函数。（4）自信息（5）互信息先验的不确定性减去尚存的不确定性。后验概率p(ai|bj)：接收端收到消息bj后而发送端发的是ai的概率。,10,信息的特征,信息是物质存在的普遍属性，信息和能量、物质规定了事物的功能和性能；接收者在收到信息之前，对它的内容是不知道的，所以，信息是新知识、新内容；它使认识主体对某一事物的未知性或不确定性减少的有用知识；信息的存在具有普遍性、无限性、动态性、时效性和相对独立性；信息可以产生，也可以消失，同时信息可以被传递、转换、扩散、复制、贮存、分割，具有可共享性；信息是可以量度的，信息量有多少的差别。,11,1.2信息论研究的对象、目的和内容,12,研究对象：通信系统模型,加密密钥,解密密钥,13,信源：发送消息的源离散信源模拟信源信源是信息论的主要研究对象之一.我们不探讨信源的内部结构和机理，而关注信源的输出。重点讨论其描述方法及性质。信宿：信息归宿之意，亦即收信者或用户，是信息传送的终点或目的地。信道：传输信息的物理媒介。,信源、信道、信宿,14,信源编码器通过信源编码可以压缩信源的冗余度,以提高通信系统传输消息的效率。信源编码器分为两类无失真信源编码：适用于离散信源或数字信号；限失真信源编码：用于连续信源或模拟信号,如语音、图像等信号的数字处理。,信源编码器与译码器,信源编码器的主要指标是它的编码效率。一般来说，效率越高，编译码器的代价也将越大。信源译码器把信道译码器的输出变换成信宿所需的消息形式，相当于信源编码器的逆过程。,15,信道编码器与译码器,信道编码主要作用是提高信息传送的可靠性。信道编码器的作用在信源编码器输出的代码组上有目的地增加一些监督码元,使之具有检错或纠错的能力。信道编码的主要方法增大码率或频带,即增大所需的信道容量。这恰与信源编码相反。信道译码器的作用具有检错或纠错的功能,它能将落在其检错或纠错范围内的错传码元检出或纠正,以提高传输消息的可靠性。,16,1.3信息论的形成和发展,17,信息论是在长期的通信工程实践和理论研究的基础上发展起来的。简史现代信息论是从20世纪20年代奈奎斯特和哈特莱的工作开始的：1924年奈奎斯特(Nyquist)的“影响电报速率因素的确定”。1928年哈特莱(Hartley)的“信息传输”一文研究了通信系统传输信息的能力，并给出了信息度量方法。,信息论的形成,18,1946年柯切尔尼柯夫的学位论文“起伏噪声下的潜在抗干扰理论”，根据最小错误概率准则和最小均方误差准则研究了离散和连续信道的最佳接收问题。1948年香农的权威性长文“通信的数学理论”，讨论了信源和信道特性，1949年香农“噪声中的通信”，两论文奠定了现代信息论的理论基础。此后，在基本理论和实际应用方面，信息论都得到了巨大的发展。,第2章离散信源及其信息测度,2.1信源的数学模型及分类,2.2离散信源的信息熵,2.3信息熵的基本性质,2.5离散无记忆的扩展信源,2.6离散平稳信源,2.7马尔可夫信源,2.8信源剩余度与自然语言的熵,20,信源产生消息或消息序列的源。消息携带信息，是信息的具体形式。描述方法通信过程中，信源发出何种消息是不确定的、是随机的。因此，信源可用随机变量、随机矢量或随机过程（或样本空间及其概率测度）来描述。不同的信源根据其输出消息的不同的随机性质进行分类。,2.1信源的数学模型及分类,21,1、随机变量描述的信源（单符号）,特点：输出单符号消息。符号集的取值A:a1,a2,aq是有限的或可数的,可用离散型随机变量X描述。数学模型：设每个信源符号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)之间统计独立。性质：独立P(X)=P(X1,X2,XN)=P1(X1)P2(X2)PN(XN)平稳P1(Xi)=P2(Xi)=PN(Xi)=P(Xi)（下标1-N为时间标志）,N维随机矢量的一个取值，i(ai1ai2aiN),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）有记忆信源,信源在不同时刻发出的符号之间是相互依赖的，即信源输出的随机序列X中，各随机变量Xi之间相互依赖。须使用随机矢量的联合概率分布和条件概率分布来说明它们之间的关联关系。例：汉字组成的中文序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的中文句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，是彼此相关的。,26,5）m阶马尔可夫信源（非平稳信源）,不同时刻发出的符号间的依赖关系,记忆信源的记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。若上述条件概率与时间起点i无关，信源输出的符号序列可看成为时齐马尔可夫链，则此信源称为时齐马尔可夫信源。,27,2.2离散信源的信息熵,基本的离散信源：输出单符号消息，且这些消息间两两互不相容。用一维随机变量X来描述信源的输出，其数学模型可抽象为:,问题：这样的信源能输出多少信息?每个消息的出现携带多少信息量?,28,信息的度量,要点：信息的度量（信息量）和不确定性消除的程度有关，消除的不确定性获得的信息量；不确定性就是随机性，可以用概率论和随机过程来测度；推论：概率小信息量大，即信息量是概率的单调递减函数；信息量应该具有可加性；信息量的计算公式为（香农（自）信息量的度量）：,29,2.1.1自信息,设离散信源X的概率空间为：,I(ai)代表两种含义：（1）当事件ai发生以前，表示事件ai发生的不确定性（2）当事件ai发生以后，表示事件ai所提供的信息量,自信息量：事件ai发生所含有的信息量,30,度量单位,计算自信息量时要注意有关事件发生概率的计算；自信息量的单位取决于对数的底；底为2，单位为“比特（bit,binaryunit）”；底为e，单位为“奈特（nat,natureunit）”；底为10，单位为“哈特（hat,Hartley）”；根据换底公式得：,一般计算都采用以“2”为底的对数，为了书写简洁，常把底数“2”略去不写,1nat=1.44bit,1hat=3.32bit；,31,收信者收到某消息获得的信息量不确定性减少的量(收到此消息前关于某事件的不确定性)-(收到此消息后关于某事件的不确定性)通信的实质？即：传递信息，消除不确定性。,32,2.2.2信息熵,对一个信源发出不同消息所含有的信息量也不同。所以自信息I(ai)是一个随机变量，不能用它来作为整个信源的信息测度。信息熵：自信息的数学期望，平均自信息量Hr(X)：,r进制单位/符号,33,熵的含义,熵是从整个集合的统计特性来考虑的，它从平均意义上来表征信源的总体特征。信源输出前，熵H(X)表示信源的平均不确定性；信源输出后，熵H(X)表示每个消息的平均信息量；信息熵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个符号信源的信息熵。若当q=2时，因为p1+p2=1,所以将两个符号的熵函数写成H(p1)或H(p2)。熵函数H(P)是一种特殊函数，具有以下性质。,36,熵函数性质,1、对称性：H(P)的取值与分量p1,p2,pq的顺序无关。说明：H(P)=pilogpi中的和式满足交换率；熵只与随机变量的总体统计特性有关。例子：,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，对数函数的底大于1时，log(pi)0，-pilog(pi)0，即得的熵为正值。只有当随机变量是一确知量时熵才等于零。这种非负性合适于离散信源的熵，对连续信源来说这一性质并不存在（基于差熵、相对熵概念）。,非负性体现信息是非负的。,39,4、扩展性,说明：信源的符号数增多时，若这些取值对应的概率很小(接近于零)，则信源的熵不变。,所以，上式成立。,因为,趋于0,40,5、可加性统计独立信源X和Y的联合信源XY的熵等于信源X和Y各自的熵之和：H(XY)=H(X)+H(Y)即：,另外：可加性是熵函数的一个重要特性，正因具有可加性，才能保证熵函数的形式是唯一的。,信源XY的符号联合概率,41,证明：,=1,=1,42,例如，甲信源为,它们的联合信源是,可计算得联合信源的联合熵：H(Z)=H(XY)=log(nm)=logm+logn=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输出一符号的条件下，信源Y再输出一符号所能提供的平均信息量。,也即：,由前面的推导，可得：,47,7、递增性,若原信源X中有一个符号分割成了m个元素(符号)，这m个元素的概率之和等于原元素的概率，而其他符号的概率不变，则新信源的熵增加。熵的增加量等于由分割而产生的不确定性量。,48,#（选讲）#证明:可以从熵的定义或强可加性得出：,49,即得：,50,递增性的推广,它表示n个元素的信源熵可以递推成(n-1)个二元信源的熵函数的加权和。这样，可使多元信源的熵函数的计算简化成计算若干个二元信源的熵函数。因此，熵函数的递增性又可称为递推性。,51,#（选讲）#例：运用熵函数的递增性（的推广），计算熵函数H(1/3，1/3，1/6，1/6)的数值。,52,8、极值性在离散信源情况下，信源各符号等概率分布时，熵值达到最大。,等概率分布信源的平均不确定性为最大。这是一个重要结论，称为最大离散熵定理。,证明：因为对数函数是型凸函数，满足詹森不等式ElogYlogEY，令矢量Y=1/P即（yi=1/pi），则有：,=1,53,特例：二进制离散信源。该信源符号只有二个，设为“0”和“1”。符号输出的概率分别为“”和“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，有：HP1+(1-)P2H(P1)+(1-)H(P2)因为熵函数具有上凸性，所以熵函数具有极值，其最大值存在。,9、上凸性,55,扩展信源的由来：当离散无记忆信源信源发出固定长度的消息序列时，则得到原信源的扩展信源。例如：在电报系统中，若信源输出的是二个符号组成的符号序列，此时可认为是一个新的信源，它由四个符号（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组成的新信源称为离散无记忆信源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)=NH(X),证明：,分解为N重求和,60,一、概念在一般情况下，信源在t=i时刻将要发出什么样的符号决定于两方面：(1)信源在t=i时刻，随机变量Xi取值的概率分布P(xi)。一般P(xi)P(xj)(2)t=i时刻以前信源发出的符号。即与条件概率P(xi|xi-1xi-2)有关平稳随机序列：其统计性质与时间的推移无关，即信源发出符号序列的概率分布与时间起点无关。,2.5离散平稳信源,61,一维平稳信源：若当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,平稳信源的特点：对于平稳信源发出的随机序列，其前后符号依赖的条件概率均与时间起点无关，只与关联长度N有关。如果某时刻发出什么符号只与前面发出的N个符号有关，那么由平稳性，则任何时刻它们的依赖关系都是一样的。,则由前面两个关系，可推知各维条件概率也满足时间起点无关性：,64,三、离散平稳信源的极限熵对于一般平稳有记忆信源，设其概率空间为：,发出的符号序列为(X1，X2，XN，)，假设信源符号之间的依赖长度为N，且各维概率分布为：,65,且满足完备集条件，各维概率密度之和皆为1：,66,已知联合概率分布，可得离散平稳信源的一系列联合熵：,N长的信源符号序列中平均每符号携带的信息量为：,平均符号熵:,信息度量1平均符号熵,67,另一方面，因信源符号之间的依赖关系长度为N,所以可以求出已知前面N-1个符号时，后面出现一个符号的平均不确定性。条件熵:若已知前面N一1个符号，后面出现一个符号的平均不确定性（平均信息量），即得一系列的条件熵：,信息度量2条件熵,68,对离散平稳信源，若H1(X)，则有：1)条件熵、平均符号熵都随序列长度N的增加是非递增的；2)对于任意序列长度N，平均符号熵不小于条件熵；3)极限熵H存在，并且等于序列长度N无穷大时的平均符号熵或条件熵。,对于一般平稳信源，求H相当困难（N取无穷大）。但N不很大时有：HHN(X)或HH(XN|X1X2XN-1)。,离散平稳信源性质总结,近似计算,69,对离散二维平稳信源，一维和二维概率分布确定，且与时间推移无关。对于这样的二维平稳信源，二符号之间的条件概率反映了前面输出某一个符号、后面再输出某一个符号的概率，其输出符号序列中依赖关系是有限的，所以有：,特例分析：离散二维平稳信源,70,联合概率满足完备性,边缘分布概率,另外，可从联合概率得到边缘分布概率：,则条件熵表示为：,71,此时：,可见：离散二维平稳信源的极限熵，等于条件熵H(X2|X1)。,N-2维边缘概率,72,推广：一般情况，如果平稳信源的记忆长度有限，也即某时刻输出什么符号只与前面的m个符号有关。此时，则可用有限记忆长度的条件熵来测度离散平稳信源的极限熵：,73,第3章离散信道及其信道容量,第一节信道的数学模型及分类,第二节平均互信息,第三节平均互信息的特性,第四节信道容量及其计算方法,第五节离散无记忆扩展信道及其信道容量,第六节信源与信道的匹配,74,信道的任务：以信号方式传输信息和存储信息。研究内容：信道中能够传送或存储的最大信息量，即信道容量。,75,3.1信道的数学模型和分类,数字通信系统的一般模型,76,二、离散信道的数学模型,条件概率P(y|x)描述了输入信号和输出信号之间统计依赖关系，反映了信道的统计特性。根据信道的统计特性的不同，离散信道又可分成3种情况：,1.无干扰信道2.有干扰无记忆信道3.有干扰有记忆信道,77,(1)无干扰(无噪声)信道信道中没有随机性的干扰或者干扰很小，输出符号y与输入符号x之间有确定的、一一对应的关系。即：yf(x),78,(2)有干扰无记忆信道信道输入和输出之间的条件概率是一般的概率分布。如果任一时刻输出符号只统计依赖于对应时刻的输入符号，则这种信道称为无记忆信道。,(3)有干扰(噪声)有记忆信道实际信道往往是既有干扰(噪声)又有记忆的这种类型。例如在数字信道中，由于信道滤波频率特性不理想时造成了码字间串扰。在这一类信道中某一瞬间的输出符号不但与对应时刻的输入符号有关，而且还与此以前其他时刻信道的输入符号及输出符号有关，这样的信道称为有记忆信道。,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完全描述了信道的特性，可用它作为离散单符号信道的另一种数学模型的形式。矩阵P中元素有些是信道干扰引起的错误概率，有些是信道正确传输的概率。,83,例二元对称信道，BSC，BinarySymmetricalChannel,解：此时，X:0,1;Y:0,1;r=s=2，a1=b1=0；a2=b2=1。传递概率:,p是单个符号传输发生错误的概率。（1-p）表示是无错误传输的概率。转移矩阵:,0101,84,（1）联合概率,其中,前向概率，描述信道的噪声特性,后向概率（后验概率）,输入符号的先验概率,单符号离散信道的相关概率关系,（2）输出某符号的概率,85,含义：输出端收到的某符号，必是输入端某一符号输入所致。,（3）后验概率,且,根据贝叶斯定理，可知：,86,3.2信道疑义度与平均互信息,研究离散单符号信道的信息传输问题。,一、信道疑义度,先验熵：即信道输入信源X的熵,H(X)是在接收到输出Y以前，关于输入变量X的先验不确定性。,87,后验熵：接收到bj后，关于输入变量X的不确定性。,后验熵是当信道接收端接收到输出符号bj后，关于输入符号的不确定性的信息测度。,88,信道疑义度：后验熵在输出符号集Y范围内是随机量。对后验熵在符号集Y中求数学期望，即-信道疑义度：,89,互信息量I(x;y)：收到消息y后获得关于x的信息量，即消除的不确定性量。,互信息量表示先验的不确定性减去尚存的不确定性，是收信者获得的信息量。若互信息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，表示在信道输出端接收到符号后不获得任何关于输入符号的信息。,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)后剩余的部分代表两个疑义度。,94,信息传输率信道中平均每个符号所能传送的信息量。而平均互信息I(X;Y)则反映了接收到一符号Y后平均每个符号获得的关于X的信息量。因此，信息传输率可作如下定义：信息传输率RR=I(X;Y)=H(X)H(X|Y)(比特/符号),3.4离散信道的信道容量,信息传输速率Rt：信道在单位时间内平均传输的信息量。即信道中平均每秒传输的信息量：,RtR/t=I(X;Y)/t=H(X)/tH(X|Y)/t（bit/s）,95,一、信道容量由于平均互信息I(X;Y)是输入随机变量的型凸函数，所以对一固定的信道，总存在一种信源的输入分布概率，使传输每个符号平均获得的信息量最大。信道容量：对任何一个固定信道，存在一个最大的信息传输率,（比特/符号）,与之相对应的输入分布概率P(X)则称为最佳输入分布。,96,(Bit/s),Ct仍称为信道容量：,若平均传输一个符号需要t秒钟，则信道在单位时间内平均传输的最大信息量为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.有噪无损信道,信道特点：输入一个符号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)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,信道特点：信道矩阵P中每一行都是由同一集合p1，p2，ps中的诸元素不同排列组成；信道矩阵P每一列也都是由同一集合q1，q2，qr中的诸元素不同排列组成。一般sr。当r=s，两个集合相同；若r=H(S),就存在唯一可译变长编码；若Rp(xj)，lip(sj)，则码长li=lj；2）r个最小概率信源符号所对应的码字必具有相同码长；3）r个最小概率的信源符号所对应的码字，其除最后一位码元不同外，前面各位码元都相同。,霍夫曼编码的最佳性,定理r元霍夫曼码一定是最佳即时码（其平均码长最小）。若C为霍夫曼码，C为其他任意即时码：,前述Huffman编码恰好满足定理条件。可见,Huffman编码是信源所有可能唯一可译码中平均码长最短的码：,206,第9章信道的纠错编码,差错控制的基本形式,纠错码分类及其基本概念,线性分组码,*循环码,*卷积码,香农第二定理指出，只要信息传输率小于信道容量，通过适当的编译码方法，就能以任意小的错误概率传输信息。但从实际工程看，并没有指出具体的编译码方法。这正是信道纠错编码要解决的问题。,207,香农第二定理指出，在信道中以信息传输率R小于信道容量条件下，使差错概率尽可能小的信道编译码原则是：编码原则：在n次扩展信道输入符号序列中选取M个作为码字构成一组码C，并尽量使选取的M个码字中两两不相同码字的汉明距离尽可能地大；译码原则：当收到符号序列后，翻译成与之汉明距离最近的码字（最大似然准则）。几十年来，基于香农编码定理和以上编译码原则，科技工作者们开发了很多具有纠错能力的信道编码，如线性分组码、循环码、BCH码、卷积码、TCM码、Tuobo码等，在通信系统中得到了广泛应用。,208,9.1差错控制的基本形式,现代数字通信系统中，利用检错和纠错的编码技术，使得信道编译码具备一定的差错控制能力。主要方式有：1、前向纠错(FEC)方式：发送端信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字译码，若传输中产生的差错数目在码的纠错能力之内，译码器对差错进行定位并加以纠正。,检错、纠错,209,FEC特点单向控制，不需要反馈信道；时延小，实时性好。为适应较差信道，冗余码元