信息论基础讲义课件.ppt_163文库

资源描述

1、Fundamentals of Information Theoryl参考书1.应用信息论基础朱雪龙编著清华大学出版社,2001年3月,清华大学电子与信息技术系列教材 2.信息论与编码理论(第二版)【美】Robert J.McEliece 著(美国加州理工学院，写于19721976年)电子工业出版社，2004年1月，国外电子与通讯教材系列3.信息论、编码与密码学 Ranjan Bose 著(印度理工学院)机械工业出版社，2005年1月,计算机科学丛书l1948年，Claude Shannon（克劳得香农）在他的经典论文“A Mathematical Theory of Communica

2、tion”(通讯的数学理论)的引言部分中写道：“通讯中的基本问题就是在某一点精确或近似地再生另一点选择的信息。”为解决这一问题，他在该论文中提出了应用数学的一个全新分支，现在称之为信息理论和/或编码理论。香农提出的信息理论是一种基于统计意义上的信息理论。这一理论对通讯技术的发展产生了持久和深刻的影响。l一个可以发出定义为“0”和“1”的两种特定符号的实体l 速率为单位时间内 R 个符号。l 我们称这些符号为比特（bits）。l信源随机地发出这些比特，“0”和“1”发出的概率相同。l假设信源速率 R 是连续变化的，即 R 可以是任何非负的数值。l在一个单位时间内可以传输 1 比特数据的实体。l但

3、该信道并不是完全可靠的：存在一个固定的概率 p（称为原始误比特率），满足 ,使输出比特与输入比特不相同。01/2pl假设 R1/3，（信道传输数据的速度是信源产生数据的3倍）l对每1比特重复编码3次，（在传输之前）l信源输出的前5个比特是 10100l编码流为111000111000000l接收到为101011111001100（由于存在信道“噪声”，第2，5，6，12，13比特被改变了）l译码为 11100（采用3个比特多票表决），出现了一个错误。lPe P 2个信道错误 P 3个信道错误 3 p 2（1 p)+p 3 3 p 2 2 p 3 其中(p=1/2)，所以 Pe 0，有：nlim

4、P|0Np信道错误的数目也就是说，只要N的取值足够大，接收比特中出错的比例就不可能与p相差很多。(21)nP0ne 当时，确实趋近于。(21)11121242121|2nePPnnnPPp接收的传输比特中出错的比例比例比例-p|l如果R的值很小，即使信道本身的噪声很大，也可以使最终的错误概率很小。l如果R1，不妨只传输信源比特的1/R部分，并让接收者以抛硬币的方式猜测其余部分。这种简单方式的最终的误比特率为：e111P21()/122RpRRpRl信道只能传输信源所产生比特的三分之一。因此发送者将信源输出分为三比特一组，并且只传输这三比特中占多数的比特。l信源输出：10111010

5、1000101l发送者将在信道中传输11101l如果信道干扰了传输的第2个比特，接收者将收到10101l并扩展为111000111000111，于是就产生了五比特的错误。13(1)441/24ePppp l注意到，R=3时，前一种“抛硬币”方法的结果为1/3+p/3,因此现在的结果要更小些。0123456412350236013,(mod2)(mod2)(mod2)xx xxxxxxxxxxxxxxxxx四个信源比特表示为:附加的比特表示为：或称为冗余位、奇偶校验位)它们由下列等式确定：0123,)(0 1 1 0)xxxx(则456,)(0 1 1)xxx(如果信道将传输的全部七比特码字为：

6、(0110011)l定义二进制矩阵H为：123402350136000 xxxxxxxxxxxx 0 1 1 1 1 0 01 0 1 1 0 1 01 1 0 1 0 0 1H0123456(,)xxx xx xx x000THx 0011660123456012(,.,)z(,)s(,)TTTTTTyxz xzxzzz z z z z z zss s ssHyH xzHxHzHz接收矢量y,错误图案，计算矢量，01601010.0111Tszzz 假设接收到y=(0111001),则s=(101)01011 1 1001101 1 01011 0 1110 1 001001z可能的16种候

7、选值：0100000 00100111100011 00010100000101 0111001 0110110 10100000101111 10010011000110 11110101110101 00111001101100 1011111重量最小的错误图案(0100000)只有一个，这里重量代表错误图案中1的个数。传输码字的估计是xyz（0011001）；而最终对四个信源比特的估计是（0011）。1.计算伴随式；2.如果s=0，设置；到4步。3.寻找H中唯一与s相同的列，称它为第i列，并设置的第i位等于1，其余位都为0。4.设置。（这是接收者对传输码字的估计。）5.输出的前

8、四个分量（）。（这是解码器对原始信源比特的估计。）0z TTsH y zxyz x0123,x x x xPxx772237170.kkEkPppkppetc()2534435267239(1)19(1)16(1)12(1)7(1)926.iePpppppppppppppetciiP xxl将信源序列分为七比特一组，通过前面的译码算法（在将信源序列分为七比特一组，通过前面的译码算法（在此变为此变为“编码算法编码算法”）将每组七比特减少到每组四比特，）将每组七比特减少到每组四比特，并在信道中传输这四比特，接收者译码时利用接收到的并在信道中传输这四比特，接收者译码时利用接收到的四比特，通过运算奇偶

9、校验式产生附加的三比特。四比特，通过运算奇偶校验式产生附加的三比特。()ieiiPP xx6()0/7ieeiPPl误比特率与误比特率与i有关，有关，l平均的误比特率：平均的误比特率：432234153(1)(1)3(1)828597(1)288139.828ePpppppp pppetc 现在通过一个特定的BSC总结一下所了解的知识。给定p=0.1，设x=R表示速率，y=Pe表示最终误比特率，对前面讨论的每一个通讯模式在（x，y）平面画出一个点，如图0.1所示。如果有足够的耐心和智慧，可以继续提出一些特殊的方式，并在图0.1中用点标明。当然我们的最终目标是希望了解哪些点能够达到而哪些点不能达

10、到。令人难以置信的是，香农已经实现了这个目标。图0.1 对应BSC(p=0.1)的一些可达到的(R，Pe)点l如果存在一个（n,k)码满足 ,就称图0.1中的点(x,y)是“可达到”的。k/nx,Pey图0.2 对应二进制对称信源和BSC的一个（n，k）码12121212,uxknyvnku uux xxy yyv vv 信源编码信道信道译码信宿l速率为R=k/n 误比特率定义为：()1()1,1,2,kieeiieiiPPkPP vuikH2(x)=-x log2 x (1-x)log2(1-x),0 x0,1log-1 log1xxxx 另外，对任意有或111(p)log(1)

11、0NnnnNnnnHpppp所以，l有关凸性的概念若对区域D中任意两点DD和，均有(1),01D 则称区域D是凸域。我们可以这样来理解，若两点在凸域D内，则之间的线段也整个在区域D内。和和凸域的例子很多。例如实数域是凸域，但整数、有理数不是凸域。有N个概率分量组成的概率矢量的集合Sp是一个N1维的凸域。如N2时，设1p0,1,2,.,1NpnnnSpnNp：(0.5,0.5)(0.4,0.6)和则有：1212(1)(1),(1)(1)(1)pppp 此时仍然有1212(1)(1)(1)(1)(1)1pppp故(1)pS l凸函数若在凸域上的f(x)满足关系式(1)()(1)(),D,01ff

12、f 则称函数f(x)为凸函数。若上式中的不等式是严格不等式，则称f(x)是定义在凸域D上的严格凸函数。若在凸域上的f(x)满足关系式(1)()(1)(),D,01fff l凹函数则称函数f(x)为凹函数。若上式中的不等式是严格不等式，则称f(x)是定义在凸域D上的严格凹函数。凸函数和凹函数又分别称为下凸函数和上凸函数。lJenson不等式1212MXJensonM若将，.,看成是由概率值组成的概率矢量，将，.,看成是随机矢量可能取的值，则不等式可以写成如下的形式:fEXEfXmmm()DD m=1,2,.,M,011,()mmmmf xff Mm=1MMm=1m=1设是凸域上的凸函数,且,则对

13、，有性质性质2.2 熵函数具有凸性，即H(p)是p的上凸函数。证明我们可以分两步进行证明。121112121222(1),.,(D)D,.,.,01NNNp pppppppp 1212设概率矢量p=的集合组成一个区域记做，p，p 是区域中的任意两个概率矢量，p=，p=，则对有121121122212(1)(1),(1),.,(1)NNpppppp pp且11211222121112121222(1)(1).(1).(1).(1)1NNNNpppppppppppp1212012(1)D,.,D(1)Np pp所以有 pp。这说明概率矢量p=的集合组成的区域是一个凸域。可令ppp（2）证明

14、下列不等式成立。1212(1)()(1)()HHHpppp因为121212121112211(1)()(1)()(1)log(1)log(1)logNnnnnnNNnnnnnnHHHpppppppp pppp1212111212log(1)log(1)(1)NNnnnnnnnnnnpppppppp12111(1)1Nnnnnnpppp12212(1)(1)1Nnnnnnpppp（2.4）102011()(1)()NNnnnnnnpppp10201111(1)NNNNnnnnnnnnpppp0所以，式 2.4 成立，即H(p)是p的上凸函数。l联合熵和条件熵联合熵和条件熵在前面我们已知道，一个随

15、机变量的不确定性可以用熵来表示。这一概念可以方便地推广到多元随机变量。利用多元随机变量的联合概率分布联合概率分布和条件概率分布条件概率分布，可以相应得到联合熵与条件熵。下面我们以两个随机变量来讨论。设二元随机变量(X,Y)可能的取值为(ak,bj),k=1,2,K,j=1,2,J,其联合概率密度为：1,2,.,1,2,.,kjkKjJp ab定义二元随机变量(X,Y)的联合熵联合熵：11,log,KJkjkjkjHXYp abp ab 式2.9联合熵是二元随机变量的不确定性的量度。l条件熵条件熵根据式(2.9)可以转化为11(),log()(|)KJkjkjkkjHXYp abp ap ba

16、1111,log(),log(|)KJKJkjkkjjkkjkjp abp ap abp ba 11()log()()(|)KKkkkkkkp ap ap aH Ya()(|)H XH YX(|)XY(|)(|)XYkkkkH YXaH Y aH Y aa我们称为条件熵。它是取值条件下的熵的平均值，称为取值条件下的条件熵，即11(),(),()(|)()(|)JKkkjjkjjkkjkjkjkjp ap abp bp abp abp ap bap bp ab1111111(|),log(|)()(|)log(|)()(|)log(|)()(|)KJkjjkkjKJkjkjkkjKJkjkjkk

18、熵等于无条件熵对于X的了解平均来说减少了Y的不确定性（3）若X和Y有确定的函数关系，且X可以完全确定Y，有(|)0,()()(|)0()()H YXH XYH XH X YH XYH Y因为于是或，或Y完全确定X时l互信息的定义对于两个随机变量X和Y，它们之间在某种程度上存在统计依赖（或依存）关系。在获知一个随机变量(如Y)的取值的条件下的条件熵H(X|Y)总是不大于另一随机变量(如X)的无条件熵H(X)，也就是说，未知Y时，X的不确定度为H(X)，已知Y时，X的不确定度变为H(X|Y)，且有这说明H(X|Y)表示了已知Y后X“残留”的不确定度。这样，在了解Y以后，X的不确定度的减少量为H(X

20、KKJkkkjkjkkjp ap ap abp ab 1(),Kjkjkp bp a b111()log(),log(|)JKJjjkjjkjkjp bp bp abp ba (|),/()jkkjkp bap a bp a()(|)(;)HYHYXI YXl给出互信息的另一个定义：11(,)(;),log()()KJkjkjkjkjp abI Y Xp abp ap b可以得到(;)()()()IXYHXHYHX Y一般情况下，互信息的值满足关系式0(;)min(),()I X YH XH Y当X、Y统计独立时，I(X;Y)=0。因为 H(X|Y)=H(X),H(Y|X)=H(Y)。互信息是

21、X和Y之间统计依存程度的信息量度。单个事件互信息（自信息）(,)(|)(|)(;)logloglog()()()()kjkjjkkjkjkjp abp abp baI abp ap bp ap b它代表已知随机变量Y取值bj后所获得的关于X的取值为ak的信息量。在这定义下，互信息是单个互信息的数学期望值。(,)(|)(;)loglog()()()kjkjkjkp a bp abI X YEEp ap bp a当X和Y为同一随机变量，且bj=ak时，有(|)1(,)loglog()()()kkkkkkkp aaI a aH ap ap a而H(ak)的数学期望就是熵，即()(,)()kkkH X

22、E I a aE H a所以由互信息可以导出熵l多个随机变量下的互信息(1)两组多元随机矢量之间的互信息(2)条件互信息(3)随机矢量中各随机变量之间的互信息l两组多元随机矢量之间的互信息考虑随机变量X和二元随机矢量（Y,Z）之间的互信息。其密度矩阵分别是：121212121212k1,2,.,Kkjlj1,2,.,Jl1,2,.,L.()().()().()().()().()().()()p(a,b,c)kkkkkkaaaXpapapapxbbbYpbpbpbpycccZpcpcpcpz其联合分布密度矩阵为定义随机变量X和二元随机矢量（Y,Z）之间的联合互信息 I(X;Y

24、(X|Z)H(X|Y Z)I(X;Y|Z)H(Y|Z)H(Y|X Z)I(X;Y|Z)H(X|Z)H(Y|Z)H(X Y|Z)I(X;Y|Z)H(X Z)H(Z)H(Y Z)H(Z)H(X Y Z)H(Z)H(X Z)H(Y Z)H(X Y Z)H(Z)条件互信息也是非负的。I(X;Y|Z)0含义是，随机变量（Y，Z）所提供的关于X的信息量等于Y所提供的关于X的信息量加上在已知Y的条件下，Z所提供的关于X的信息量。I(X;YZ)=H(X)H(X|YZ)=H(X)H(X|Y)+H(X|Y)H(X|YZ)=I(X;Y)+I(X;Z|Y)l联合互信息与条件互信息的关系联合互信息与条件互信息的关系l两

25、组随机矢量之间的互信息的更一般的表示为两组随机矢量之间的互信息的更一般的表示为：同理，存在关系式I(X;YZ)=I(X;Z)+I(X;Y|Z)I(XY;UVW)=I(XY;W)+I(XY;V|W)+I(XY;U|VW)l随机矢量中各随机变量之间的互信息以三个随机变量X，Y和Z为例。互信息I(X;Y;Z)为 111,I(X;Y;Z)=,log,KJLkjjllkkjlkjlkjlkjlp abp bcp c ap abcp ap bp cp abc可以推导出:I(X;Y;Z)=I(X;Y)I(X;Y|Z)I(X;Y;Z)=I(Y;Z)I(Y;Z|X)I(X;Y;Z)=I(Z;X)I(Z;X|Y)

26、需要说明的是,互信息 I(X;Y;Z)没有明确的物理意义,且可以大于0,小于0或等于0。但它在数学上有一定的价值，可以帮助推导一些关系式。除此之外，它很少在实际问题中应用。l互信息的性质11(,)(;),log()()KJkjkjkjkjp abI Y Xp abp ap b根据11(),(),()(|)()(|)JKkkjjkjjkkjkjkjkjp ap a bp bp a bp a bp a q bap b q ab111|(;)|log()|KJjkkjkKkjijiiq baI Y Xp aq bap a q ba12(;)Xp(),(),.,()(|)(p,)p,kjkk jI Y

27、 Xp ap ap aq baI,于是，就成了随机变量的概率矢量=()和条件概率矩阵Q=()的函数，记作Q。互信息作为Q的函数，具有凸函数的性质。l性质性质2.3 互信息I(p,Q)是p的上凸函数。l性质性质2.4 互信息I(p,Q)是Q的下凸函数。性质性质2.3 证明按凸函数的定义，要证明12012p+(1-)ppp+(1-)p12由于p，pD，所以D，并令121201,(p,)(1)(p,)(p+(1-)p,)III 12对 p，pD，及有QQQ12ZZP()1ddz引入随机变量，其密度矩阵为并且将Z，X，Y看成是如下图所示的输入与输出关系，并假设X的概率分布由随机变量Z来控制，即121

28、11|1222|2Xp()(|)Xp()(|)kx z dkkx z dkzdp apxazdzdp apxazd时，的概率分布为时，的概率分布为(|)jkq ba图2.4 Z、X与Y构成的输入与输出关系示意图所以p1,p2就成了Z取不同值时X取值的条件概率矢量。但是，此时条件概率矩阵Q与随机变量Z的取值无关，于是有120(p+(1-)p,)(p,)(;)III Y XQQ1211221122(p,)+(1-)(p,)()(p,)()(p,)()(;|)()(;|)(;|)IIp dIp dIp dI X Yzdp dI X YzdI Y XZ而 QQQQZXZY(;|)0I Z Y X由于

30、)JjkjkjJJjkjkjjqbaqbaqbaqba12对Q，QD，及有QQD，故条件概率矩阵组成的集合D是一个凸域。12+(1-)0令QQQ12ZZP()1ddz引入随机变量，其密度矩阵为设Z的取值与随机变量X无关，只影响条件概率矩阵Q，即当 z=d1时，条件概率矩阵Q Q1 当 z=d2时，条件概率矩阵Q Q21122(p,)(1)(p,)()(,|)()(,|)(;|)IIp dI pzdp dI pzdI X YZ1212QQQQ于是而12(p,+(1-)(p,)(;)III X Y0QQQZX(;)0,(;)(;)(;|)(;)(;|)(;|)0I X ZI X Y ZI X Y

31、I X Y ZI X ZI X Z YI X Z Y 由于与无关，即则12(;|)(;)(p,)(1)(p,)(p,+(1-)I X YZI X YIII12所以即 QQQQl连续随机变量下的微分熵()()log()h Xp xp x dx 设连续随机变量X的可能取值在整个实数域上，即其概率密度函数为。定义X的熵为（称微分熵）：(,)x ()p x两个连续随机变量X和Y的联合微分熵:()(,)log(,)h XYp x yp x y dxdy 连续随机变量X和Y的条件微分熵：(|)(,)log(|)()(|)log(|)h XYp x yp xy dxdyp y dyp xyp xy d

32、x 微分熵可以作为连续随机变量不确定程度的相对量度。下列关系式成立。()()(|)()(|)(|)(),(|)()()()()h XYh Xh YXh Yh XYh XYh Xh YXh Yh XYh Xh Yl关于微分熵的讨论我们可以按照微分的方法，将离散随机变量的熵的概念推广到连续随机变量X的情形下。将X的值域分成间隔为的小区间，则X的值在小区间内的概率近似为。于是，熵的近似值为x(,)iix xx()ip xx()()log()xiiiHXp xxp xx 00000lim()lim()log()()log()lim log()()log()lim logxiixxixxxHXp

33、xxp xxp xp x dxxp x dxp xp x dxx 当时，有可以看出，上式中的后一项极限值为无穷大，按照离散熵的概念，连续随机变量的熵应为无穷大，失去意义。0 x 当时，l随机变量函数的微分熵设有连续随机向量(X,Y),其联合分布密度函数为p(x,y),边缘分布函数分别为p(x),p(y)。(X,Y)经变换变换前后的随机向量的关系如下所示：(,)(,)Uu X YVv X Y后，得到新的随机向量(U,V),其联合分布密度函数为p(u,v),边缘分布函数分别为p(u),p(v)。(,)(,)(,)(,)u X Yv X YX YU V取值(x,y)(u,v)变换后，U和V的联合微分

34、熵为()(,)log(,)h UVp u vp u v dudv,(,)log(,),x yx yp x yJp x yJdudvu vu v(,)log(,)(,)logp x yp x y dxdyp u vJ dxdy()()(,)logh UVh XYp u vJ dxdy如果变换是线性的，即，其中A为线性变换矩阵。UXAVY1,1det,detx yJAu vA()()log deth UVh XYA若变换不仅是线性变换，且仅有平移和旋转，则有 Det A=1于是，()()h UVh XYl连续随机变量下的互信息(,)(;)(,)log()()p x yI X Yp x ydxdy

35、p x p y下列关系式成立(;)(;)(;)()(|)(;)()()()(;)()(|)(;|)(|)(|)I X YI Y XI X Yh Xh X YI X Yh Xh Yh XYI X YZh Xh X YZI X Y Zh X Zh X YZl鉴别信息的定义（1）离散随机变量的情形设随机变量X的可能取值为a1,a2,aK,且X的概率分布情况与假设H1和H2有关，即在假设H1下，X的概率分布为 12111121.KKXaaaPxpapapa在假设H2下，X的概率分布为 12221222.KKXaaaP xpapapa另外，假设H1和H2成立的概率分别为p(H1)和p(H2)，有1111

36、122222112211221212()()(|)()()()()()()(|)()()()()()(|),()(|)(|)(|)Xkkkkkkkkkkkkkkkp Hpap Hap Hpap Hpap Hpap Hap Hpap Hpapap aHpap aHp Hap HaaHH其中，和分别是取条件下，假设和成立的条件概率。222111()(|)()loglog()(|)()kkkkpap Hap Hpap Hap Hlog上面的对数似然比在假设H2下的数学期望就称为鉴别信息：22,1211()(;)()log()KkkkkpaI p p Xpap al本章我们介绍了信息论中的三个基本概念

37、：熵、互信息和鉴别信息。这三个概念的要点可以归结为：（1）信息论的三个基本概念分别给出了随机变量不确定性的量度以及在消除或减少这一不确定性时所获得的信息的量度。(a)随机变量的不确定性的量度：香农定义的熵是随机变量不确定性的最合理的量度。这可以从以下几个方面来理解：尽管在不同的条件下可以得到不同形式的不确定性的量度，但是，直到目前为止，从理论上以及函数形式上讲，香农定义的熵函数仍然是最好的。在连续分布下只存在微分熵这一问题并不是香农定义的致命缺陷。因为从概念上讲，连续随机变量所取的值应该是无穷精度，其不确定性为无穷是完全合理的。在实际应用中，由于变量所取的数值只能是有限精度，因此，连续随机变量

38、的熵为无穷这一点不会给实际应用带来困难。我们只需要用一个相对尺度来衡量连续随机变量的不确定性即可。（b）减少或消除随机变量的不确定性的两个途径和信息的两种量度：一条是对另一个与我们感兴趣的随机变量统计关联的随机变量进行观察、试验，从而获得关于原随机变量的信息，减少或消除其不确定性。该信息量可以用互信息进行量度。另一条是对我们感兴趣的随机变量本身进行观察、试验，从而获得信息，减少或消除其不确定性。该信息量可以用鉴别信息进行量度。（2）从统计数学的角度来看，信息论的三个基本概念给出了三个统计量，代表了三种量度，其中：l熵是一个系统无序性的量度；l鉴别信息是两种概率分布之间差异性的量度；l互信息是两

39、个随机变量之间统计依存性的量度。因此，熵、互信息和鉴别信息大大丰富了统计数学中对随机现象的描述方法，其意义超过了随机变量一般的数字特征。（3）三者的相互关系：在信息论的三个基本概念中，熵是最基础的。鉴别信息则是最普遍的，由鉴别信息可以推出互信息，故互信息是鉴别信息的特例。由互信息又可以推出熵，故熵是互信息的特例。三者的上述关系，使得它们的函数性质也存在相似之处，特别是三者均有凸性。凸性使得三者都特别适合作为优化问题中的目标函数，因为由此导出的极值总是全局极值。但三者的表达式中都含有对数函数，这给实际使用又带来一定的困难。l信源、信源模型与信源编码l离散稳恒信源的熵率与冗余度l离散无记忆信源的渐

40、近等同分割性与信源的定长编码定理l离散无记忆信源的变长编码l变长编码的平均码长与最优编码l离散无记忆信源的变长数码l离散马尔可夫信源的熵率l离散马尔可夫信源的编码定理与最优编码信源的熵率、冗余度与冗余度压缩编码l信源信息的来源信源发送器信道接收器信宿噪声消息信号发送信号接收消息图3.1 通讯系统的组成图l信源模型信源分类（1）按信号取值和取值时刻分为：数字信源（离散信源）模拟信源（波形信源）连续信源（2）按概率分布函数：是一种随机过程。按随机变量前后取值是否独立，分为：无记忆信源（独立随机信源）有记忆信源（不独立随机信源）按随机过程是否平稳分为：稳恒（平稳）信源非稳恒（非平稳）信源与特殊

41、随机过程相对应的信源模型，如高斯信源，马尔可夫信源等。l信源编码编码编码将一种字母序列或符号序列映射映射为另一种字母序列或符号序列。包括离散数列和连续数列之间的映射。映射及其映射前后的序列（或数列）一起构成码码。实现映射的装置称为编码器编码器。编码器的输入字母称为源字母源字母；编码器的输出字母称为码字母码字母。源字母的集合称为源字母表源字母表；码字母的集合称为码字母表码字母表。l两种典型的映射方式分组码分组码将编码器的源字母序列和码字母序列均分成组，映射在分组的基础上独立进行。即一定的源字母组（源字源字）唯一地确定了一定的码字母组（码字码字）。分组码可以分为：定长到定长分组码定长到变长

42、分组码变长到定长分组码变长到变长分组码树码树码编码器输出的码字母不仅由当前输入的源字母决定，而且还可能与以前的源字母或码字母有关。树码的映射关系可以用树图清楚地加以表示。如滑动分组码，卷积码等。l信源编码简介信源编码主要有冗余度压缩编码冗余度压缩编码和熵压缩编码熵压缩编码。冗余度压缩编码可以保证码字母序列在译码后无失真地复原为源字母序列熵压缩编码只能保证译码时能按一定的失真允许度恢复源字母序列，但同时又能保留尽可能多的信息量。稳恒信源是信源研究中最主要的一种信源。稳恒信源输出的信号是一个稳恒的随机过程。当信源字母表是离散的，且信号取值时刻也是离散时，此时的稳恒信源就称为离散稳恒信源离散稳

43、恒信源。1221012,Ka aauuuu u设离散稳恒信源的字母表为，信源的输出序列用来表示。根据稳恒随机过程的定义，信源输出序列的一切有限维概率分布与时间轴起点的选择无关，即11(,)(,)iiiNjjjNP u uuAP uuuA其中，A为某一特定的字母序列。l计算离散稳恒信源输出的信息量假设信源字母序列的序列长度有限，设为N，并用来表示。该有限长度的序列组成一个随机矢量该随机矢量的熵用联合熵来表示，12,Nu uu12()NH U UU平均每个字母的熵表示为：121()()NNHUH U UUN()()lim()NNxNHUH UHU当时，若趋于某一极限，则定义该极限为信源的熵率对于

44、独立稳恒信源，即无记忆稳恒信源，前后时刻信源的输出彼此独立，则有1211211()()()()lim()1lim()()()()NNiiiNxNxiH U UUH UNH UHUHUH U UUNH UH UHU 12NUU UUl定理3.1 对于离散稳恒信源，1(),()H UHU 若则存在，且有121N()lim(|)NNHUH UU UU()HU 证明（）证明的存在性。根据信源的稳恒性以及无条件熵不小于条件熵的性质，可知112221121(|)(|)(|)NNNNNNH UU UUH UUUH UU UU121(|)NNNH UU UU这说明条件熵是随着的增大而减小的，12111111

45、11()()(|)(|)()(|)(|)(|)NNNNNNNNNNNHUH UH UUH UUUH UH UUH UUUNH UUU另一方面，又有11121111()(|)()(|)(1)()NNNNNNNNHUH UUUH U UUH UUUNHU11()()(1)()()()NNNNNNHUHUNHUHUHU根据熵的非负性，有110()()()NNHUHUHU 这说明此数列单调有界，故极限必存在，且为0和H1(U)之间的某一有限值。lim()NxHU1211211211()()(|)(|)N MNNNN MNNN MNM HUH U UUH UU UUH UU UUUU121(2)()l

46、im(|)NNxHUH UU UU证明。11211(1)()()(|)NMNNNNMHUHUH UU UUNMNM121,()(|)()NNNNMHUH UU UUHU 固定，并令则得121()lim(|)lim()()NNNxxNHUH UU UUHUHU 现在令，则有121()lim(|)NNxHUH UU UU因此，(式3.11)由式3.11可知，HN(U)随着N的减少而不断增大，其最大值为H1(U)。由熵的极限性可知1()logH UKK其中，为源字母表的字母数。定义log()()1logKHUHUK 冗余度相对冗余度2log K1()H U()H W熵英语法语德语西班牙语4.704.

47、704.704.704.1243.9844.0954.0151.653.021.081.97表3.2 西方几种语言的熵值(单位：比特)离散无记忆稳恒信源是最简单的一种信源模型，其输出信号是一个离散的独立随机序列。对这一信源其熵率1()()HUHU即渐近等同分割性(AEP)定理定理3.2(渐近等同分割性定理渐近等同分割性定理)200u00,log(u)()1Nu uuNNNPPHUN 1设=是离散无记忆信源输出的一个特定序列，则任给定和可以找到一个整数，使当时，有式又称熵定理或遍历性定理。2u(1,2,)Nkku uuan kK1证明设序列=出现字母值的次数为由独立随机序列的性质可知：111

48、11(u)()log(u)log()()()()log()log(u)()()log()knKkkKkkkKkkkKkkkkPp aPnp aHUH Up ap anPHUp ap aNN=kknaN是序列出现的频率，表示为max1max1()maxlog(u)()log()log()kkkkkKkkkKkknp aNPHUp aNp a ，max如果在所有的可能序列中，有部分序列其满足max10log()Kkkp a，u则该序列即能满足log(u)()PHUN（式3.26）满足条件（式3.26）的序列称为典型序列，并将典型序列的集合记作G，即log(u)G=u:()PHUN不满足条件（式

49、3.26）的序列的集合记为G(式3.25)估计序列落入两个集合的概率对于集合，其中的序列不满足（式3.25），即至少存在一个值l，使Gm ax()llnp aN 如果把发生上述情况的记作事件El ,则中所有序列的概率之和为G11()max()KKllllllPEEKP ENNNN00但按照大数定律，当足够大时，对于任何l值总是可以有一个整数，使当时，有max()()lllnP EPp aNK()Gllnp aN即依概率收敛到。得到中序列的概率之和小于。即1()KllPE所以，G中序列的概率之和大于1l定长编码定理设离散无记忆信源1212,K;,J;KJa aab bb源字母表为字母总数

50、为码字母表为字母总数为定长编码就是将长度为N的源字母组映射为长度为M的码字母组；或者说把长为N的源字映射为长为M的码字。扩展信源的概念离散无记忆信源的N次扩展信源也是一个无记忆信源，其字母表有KN个字母，每个扩展源字母各对应N个原信源字母，而扩展源字母的概率即为其对应的N个原信源概率之积，共有KN个源字，JM个码字。可以证明 H(XN)=NH(X)。定理3.3 设熵率为的离散无记忆信源被分成长N的源字母组，并用长为M的码字母组进行编码，码字母表的大小为J。则对任给的数，只要N足够大，且满足不等式()HU00和log()MJHUN0则源字母组没有自己特定码字的概率P可以小于。证明由渐近等同

展开阅读全文