信息论基础复习提纲

1、来源：网络转载来源：网络转载1、什么是信息？香农对于信息是如何定义的。答：信息是事物运动状态或存在方式的不确定性的描述（Informationisameasureofonesfreedomofchoicewhenoneselectsamessage）。2、简述通信系统模型的组成及各部分的含义。答：（1）、信源：信源是产生消息的源。信源产生信息的速率-熵率。（2）、编码器：编码器是将消息变成适合于信道传送的信号的设备。包括信源编码器（提高传输效率）、信道编码器（提高传输可靠性）、调制器。（3）、信道：信道是信息传输和存储的媒介。（4）、译码器：译码是编码的逆变换，分为信道译码和信源译码。（5）、

2、信宿：信宿是消息的接收者（人或机器）。3、简述香农信息论的核心及其特点。答：（1）、香农信息论的核心：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输,并得出了信源编码定理和信道编码定理。（2）、特点：、以概率论、随机过程为基本研究工具。、研究的是通信系统的整个过程，而不是单个环节，并以编、译码器为重点。、关心的是最优系统的性能和怎样达到这个性能（并不具体设计系统）。、要求信源为随机过程，不研究信宿。第二章信息的度量2.1自信息和互信息I(x.)=-logp(x.)=log1、自信息（量）：（1）、定义：一个事件（消息）本身所包含的信息量，它是由事件的不确定性决定的。某个消息xi

3、出现的不确定性的大小定义为自信息，用这个消息出现的概率的对数的负值来表示012q扩展性:limH1(p,p,p-,)=H连续性：递推性：极值性：上凸性(1)、(2)、(7)、8)、2、熵函数的性质：limHq(p:p；pqst012q-1qH(p1，p2,pn-1H(p,p,p)Xf(x1(p,p,p)-)q=H(p,p；p)TOC o 1-5 h zq-1q12q,q,qq)=H(p,p,p)+pH(片,叱,)121m1112nnppppH(,-)=logn“一：)+m-九)f2(X)2123、联合熵：联合自信息的H(XY)=工Ep(Xy)I(xy)=-YEp(xy)logp(xy)ijij

4、ij2ij数学期望。它是二维随机i=1j=1i=1j=1变量XY的不确定性的度量。由于不同的x，H(Y/x)是变化的，对H(Y/x)的所有可能值进行统计平均，4、条件熵：iii条件熵就得出给定X时，Y的条件熵5、各类熵之间(的关系=-EEp(xy)logp(y/x)H(X/Y)=-EEp(xy)logp(x/y)ij2jiij2ijijij(1)、联合熵与信息熵、条件熵之间的关系:H(XY)=H(X)+H(Y/X)。推广.H(X1X2X“)=H(X1)+H(X2/X1)+H(X“/X1X2X)推丿：12N121N12N-1；当二维随机变量X,Y相互独立时，联合熵等于X,Y各自熵之和。H(XY)

5、=H(X)+H(Y)。、条件熵与信息熵的关系：H(X/Y)H(X)；H(Y/X)=H(Y)。(3)、联合熵与信息熵的关系：H(XY)H(X)+H(Y)当X、Y相互独立时等号成立。推广到N个随机变量：H&1X2XN)HG1)+HG2)+-+H&N)。6、例2.5:随机变量X，Y的联合概率分布如表2.1所示，求联合熵H&Y)和条件熵H61X)表2.1X,Y的联合概率分布P(XY)0101/41/41/211/201/23/41/41信息1Q；巧)在表2.2条件概率分布P&1X)X0101/21/2110体上表示从一个随机变量Y所给出关于另一个随机变量X的信息量，定义互2.3平均互信息1、乂：从整X

6、Y的联合空间中的统计平均值为随机变量X和Y间的平均互信息。I(X;Y)=X区p(x.;yj)I(x.;y.)=工区p(x.;yj)log2=丫区p(x.;y.)logi=1j=1=H(X)-H(XIY)i=1j=1-工区p(xi;yj)log1i=1j=1i=1j=1条件熵H(X1Y)表示给定随机变量Y后，对随机变量X仍然存在的不确定度。所以Y关于X的平均互信息是收到Y前后关于X的不确定度减少的量，也就是从Y获得的关于X的平均信息量。2、平均互信息的性质：(1)、非负性：1&；Y)、；、互易性(对称性)：1&；Y)=1SX)；、平均互信息与各类熵之间的关系：I(X;Y)=H(X)-H(X/Y)

7、=H(Y)-H(Y/X)=H(X+H&)-H(XY)-+4呻-+*;当X,Y统计独立时，1G；Y)=。(请补充完善右图)、极值性：I&;Y)H(X)I(X;Y)H(XN1X1X2XN_)；（3）、平均符号熵HN在，并且（4）、如果H&丿“，则H=limH18N*NH=limH（X）=limH（XIXXX）8NN12N-14、马尔科夫信源：信源在某一时刻发出某一符号的概率除与该符号有关外，只与此前发出的有限个符号有关。M阶马尔可夫信源只与前面发出的m个符号有关，1阶马尔可夫信源只与前面一个符号有关。5、例题3.3:信源X的信源模型为输出符号序列中，只有前后两个符号有记忆，条件概率P(XIX21求

8、熵率，并比较H（X21X1）、2H（XiX2）和H（X）的大小第五章无失真信源编码5.1信源编码的相关概念非分组码1、各种码的分类：（1）、分组码和非分组码：、分组码:将信源符号集中的每个信源符号si固定地射成码一个码字Wi（个信源符号一一个码字）、非分组码:又称树码，编码器输出的码符号通常与编码器的所有信源符号都有关。（2）、奇异码与非奇异码：定义若一种分组码中的所有码字都不相同，则称此分组码为非奇异码，否则称为奇异码。非奇异码是分组码能够正确译码的必要条件，而不是充分条件。（3）、唯一可译码与非唯一可译码：定义任意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为唯一可译码。条件：、

9、此码本身是非奇异的；、对于任意有限的整数N,其N次扩展码均为非奇异的。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。（4）、即时码与非即时码：定义无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码。条件：、此码是唯一可译码；、不需要通过接收到后面的码字才能译出前面的码字，在收到一个完整的码字后即可以及时译出。一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。奇异码非奇异码丫非唯一可译码唯一可译码4及时码非及时码5.3、变长码及变长信源编码定理1、Kraft不等式McMillan不等式：（1）、Kraft不等式：设信源符号集为S=sl

10、,s2,sq，码符号集为X=x1,x2,xr,对信源进行编码，得到的码为C=w1,w2,-wq，码长分别为11，12,Tq.即时码存在的充要条件是为rli1这称为Krafti=1不等式（其中r是被编码的符号个数；q是信源个数；*是码的长度）。这也就意味着即时码存在于二叉树的叶子节点处。（2）、McMillan不等式：判断唯一可译码的条件与即时码条件一致，都是工r1，条件并不比即时i=1码判断条件宽松。2、唯一可译码的判别准则：定理一个码是唯一可译码的充要条件是F1,F2,的并集中没有C中的码字。设C为码字集合，我们要构造尾随后缀的集合Fl,F2,和F。（1）、F1是C中所有码字尾随后缀的集合：

11、若C中的码字w.是码字w的前缀，即w=wA，则将尾jiij随后缀A列为F1中的元素，所有这样的尾随后缀构成了F1；（2）、考查C和Fi两个集合，若C中任意码字是Fi中元素的前缀，或者Fi中任意元素是C中码字的前缀则将其相应的尾随后缀放入集合F.$（3）、F=UF（即F为码C的尾随后缀集合）；ii（4）、若F中出现了C中的元素，则算法终止，判断C不是唯一可译码；若出现F,为空集或F,中的i+1i+1元素在F中已经全部存在了，则算法终止，判断C是唯一可译码。总而言之，判断一个码是唯一可译码的充要条件是F中不含有C中的码字。3、例5.4:设消息集合共有7个元素s1,s2,s3,s4,s5,s6,s7

12、,他们分别被编码为a，c，ad，abb，bad，deb，bbcde，判断是否为唯一可译码。5.4变长码的编码方法1、香农编码的方法：、信源的q个消息概率从大到小排序，PPC2工PV；（2）计算各个信源符号的累加概率FCpC）i=1,2,q；ikk=1(3)按公式I.=ilog1ii=1,2,，q计算第i个消息的码长1；i（4）将累加概率FC.）变换成二进制小数得到其码字。将累加概率FC.）变换成二进制小数，取小数点ii后p(s)p12(s)oq3、二元霍夫曼编码的方法：（2）、0,1码分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包括q-1个符号的新信源。（

13、3）、将新信源仍按概率从大到小排序，再将最后两个概率最小的信源符号分别用0和1码符号表示，合并成一个新符号，这样形成了q-2个符号的新信源。（4）、依次继续下去，直至信源最后只剩下两个信源符号为止。将这最后两个信源符号用0和1表示。（5）、从最后一级缩减信源开始，进行回溯，将每次标注的码符号连接起来就得到各信源符号所对应的码符号序列，即相应的码字。（1）、信源的q个消息概率从大到小排序。即p(s)p(S)p12(s)oq4、例5.7:以例5.6为例编制二元霍夫曼码。霍夫曼编码码字信源符号编码过程码长10S10.2007200.260.35090.610/丿j211s20.190.190.200

14、.263500.39/丁丫2000s30.1807180.190.2000/2613001s40.170.170.1800.了3010s50.150TT500.171430110s60.1000TX140111s70.01145、费诺编码的过程：（2）、将依次排列的信源符号以概率分为两组，使两组的概率和基本相等。并赋予符号0和1。（3）、再分组，使划分后的两组的概率和基本相等，并赋予符号0和1。4）、重复，直至每组只剩下一个信源符号为止。5）、信源符号对应的码符号序列即为费诺码。6、例5.9：信源与例5.6和例5.7相同，请编制费诺码。费诺码信源符号概率第1次分组第2次分组第3次分组第4次分组

15、二元码码长S10.2000002S20.19100103S30.1810113S40.1710102S50.15101103S60.101011104S70.011111147、总结：霍夫曼码是即时码，他的两个特点：（1）保证了概率大的信源符号对应的码长小，概率小的信源符号对应的码长大，充分利用了短码（2）每次缩减信源的最长两个码字有相同的码长，最后一位码符号不同。（码长相差的小）编码最短，传输效率最高。&习题5.8:下面是4种不同的编码:000,10,00,11；100,101,0,11；01,100,011,00,111,1010,1011,1101；01,111,011,00,010,1

16、10；请计算：（1）、此码的码长分布是否满足Kraft-McMillan不等式？（2）、此码是否为即时码？如果不是，请说明。（3）、此码是否为唯一可译码？如果不是，请说明（可以画出树图说明）。5.5实用的无失真编码方法各种编码的应用（小题）：（1）、游程编码（REL,REC）应用于：BMPTIFAVI；（2）、LZW码应用于：GIFZIPARC；（3）、算术编码应用于：JPEG2000；参考答案I（a）log0.0643.96bit例2.1:、2I（c）log0.0225.51bit、由于前后字母出现是互相独立的，“ac”出现的概率为0.064*0.022,所以I（ca）=-log20.04=

17、4.64bit即两个相对独立的事件的自信息量满足可加性，也就是由两个相对独立的事件的积事件所提供的信息量应等于他们分别提供的信息量之和。、“a”出现的条件下，“c”出现的频率变大，它的不确定性变小。例2.5:H（XY）=log+log+log二log4+log2二x2+x1比特/联合符号41/441/421/242422由联合概率分布得x的边缘概率分布：PX02,px12和条件概率分布p（旳丨xi）（如表2.2所示），得到H（YIX0）1,H（YIX1）0和H（YIX）2x1+2x02。注意到H（Y）二OW2二H（Y1x）例2.15:由X,Y的联合概率分布求出X,Y的边缘概率分布如下图表所示：

18、来源：网络转载来源：网络转载例3.3：(1)、熵率：H=H2=HC2IX1)=0.870比特/符号；2)、如果不考虑符号间的相关性，则信源熵为H(X)=-log4+-log9+11log36=1.542比特/符号4943611由此可见，H&21x丿H&)=H&2)，这是由于Xx2之间存在统计依赖关系，在x1已知的情况下，x2的不确定性减少，即条件熵HG21x)小于无条件熵hG)。因此在考虑序列符号之间相关性之后，序列的熵减小。如果信源输出的符号序列看成是分组发出的，每两个符号作为一组，这样可以把符号序列看成是由一个新信源发出的，新信源每次发出的是由两个符号构成的消息。新信源的数学模型是一个二维的随机变量，新信源的熵为HC1X2)=HC1LHC2IX1)=1.542+0.870=2.41