信息论基础复习提纲

第一章绪论、什么是信息？香农对于信息是如何定义的。答：信息是事物运动状态或存在方式的不确定性的描述Informationisameasureofone'sfreedomofchoicewhenoneselectsamessage）。2、简述通信系统模型的组成及各部分的含义。答：（1）、信源：信源是产生消息的源。信源产生信息的速率---熵率。（2）、编码器：编码器是将消

息变成适合于信道传送的信号的设

备。包括信源编码器（提高传输效

率）、信道编码器（提高传输可靠性）、调制器。3）、信道：信道是信息传输和存储的媒介。（4） 、译码器：译码是编码的逆变换，分为信道译码和信源译码。（5） 、信宿：信宿是消息的接收者（人或机器）。、简述香农信息论的核心及其特点。答：（1）、香农信息论的核心：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输，并得出了信源编码定理和信道编码定理。（）、特点：①、以概率论、随机过程为基本研究工具。、研究的是通信系统的整个过程，而不是单个环节，并以编、译码器为重点。、关心的是最优系统的性能和怎样达到这个性能（并不具体设计系统）。1自信息和互信息i自信息（量）：1自信息和互信息i自信息（量）：（1）、定义：一个事件（消息）本身所包含的信息量，它是由事件的不确定性决定的。某个消息叫出现的不确定性的大小定义为自信息，用这个消息出现的概率的对数的负I€xi)„-logp(X)„log€x)值来表示：p€x1),pp€x1),p€x2)时I(x1)>I(x2)概率越小，事件发生的不确定性越大，事件发生以后所包含的自信息量越大。②、极限情况下，当p(x.)„0时IG/t…；p(x.)=1时，I(x.)t0③、两个相对独立的不同的消息所提供的信息量应等于它们分别提供的信息量之和，即自信息论满足可加性。p(X1x2)„p(xi)p(x2I(X1x2)„I(X])+I(x2)

息论满足可加性。(3)、例2.：1、英文字母中“a”出现的概率为 ，4”出现的概率为 ，分别计算他们的自信息量。、假定前后字母出现是互相独立的，计算“ac”的自信息。、假定前后字母出现不是互相独立的，当“a”出现以后，“c”出现的概率为，计算“a”出现以后，“c”出现的自信息量。2互信息：一个事件y7-所给出关于另一个事件x的信息定义为互信息，用1€xi;y)表示：I(x.;y.)=I(x.)-1(x.Iy.)=logij i ij平均自信息、定义：随机变量的每一个可能取值的自信息1(xi)H(X)二E[I(x)]二一工p(x)logp(x)..2.的统计平均值定义为随机变量的平均自信息量。2、 熵函数的性质：均对称性：H的统计平均值定义为随机变量的平均自信息量。2、 熵函数的性质：均对称性：H(p,p,，，，p)二H(p,p,，，，p)=•••=H(p,p,，，，p)12q21qq1 q-1确定性非负性扩展性连续性递推性极值性上凸性i3、 联合熵：联合自信息的数学期望。它是二维随机变量的不确定性的度量。4条件熵：由于不同的X均.1)、2)3)4)5)6)7)8)、H(1,0)3H(iqo,0)=，，2=H(10，，，0)=0H(p)二H(p,p，…p)>01 2qlimH(p,p,…p-£,£)二H(p,p,…p)urnH*》,'p:pq-£,p+£『二H(p,p:…p)—0 12 q-1 q 12qH(p,p,…p,q,q…q)-H(p,p,…p)+PH("】,,…化)nnnn12 n-1121m1 112nnpppnnnnH(p,p,…p)<pH(_,_,…_)=lognf[<x+Z)x]><f(x)+U-<)f2(x)1212H(XY)=工区p(xy)I(xy)=-Y区p(xy)logp(xy).j.j .j 2 .j.=1j=1 .=1j=1H(Y/x)是变化的，对H(Y/x)的所有可能值进行统计平均，..就得出给定X时，Y的条件熵H(Y/X)=—工工p(xy)logp(y/x)H(X/Y)=—工工p(xy)logp(x/y).j2 j. .j2 .j.j .j、各类熵之间的关系：()、联合熵与信息熵、条件熵之间的关系:H(XY)=H(X)+H(Y/X)。推广:H(x1X2...XN)=H(x1)+H(x2/X1)+..+H(XN/X1X2,,XN-1)当二维随机变量 相互独立时，联合熵等于各自熵之和。H(XY)=H(X)+H(Y)。(2)、条件熵与信息熵的关系：H(X/Y)<H(X);H(Y/X)=H(Y)。()、联合熵与信息熵的关系：H(XY)<H(X)+H(Y)当、相互独立时等号成立。推广到个随机变量：H&1X2，，，XN)<H&1)+H&2)+，，，+HR)。

、例：随机变量，的联合概率分布如表 所示，求联合熵H€xy）和条件熵H€y1X）表 的联合概率分布p表 的联合概率分布p（xy）p(xi)p(yj)表 条件概率分布P（Y1x）\3平均互信息、定义：从整体上表示从一个随机变量所给出关于另一个随机变量的信息量，定义互信息I€xi；y）在的联合空间中的统计平均值为随机变量和间的平均互信息。I(XI(X；Y)=„„p(xi；y)I(X：；y.)=„„p(xi；y.)logi=1j=1 i=1j=1—„„〃6.；y}og- 1 、=H(X)—H(XIY)zj帀i.i=1j=1条件熵H€x1Y）表示给定随机变量Y后，对随机变量X仍然存在的不确定度。所以Y关于X的平均互；当4）、；当4）、FH(Y)，H(XY)补 -+<— —>*-+° 4 ► ►信息是收到Y前后关于X的不确定度减少的量，也就是从Y获得的关于X的平均信息量。2平均互信息的性质：（）、非负性：I&；y）n0；（）、互易性（对称性）：1€x；Y）=1€y；X）；（3）、平均互信息与各类熵之间的关系：I（X;Y）=H（X）-H（X/Y）=H（Y）-H（Y/X）=H（X统计独立时，I€x；Y）=0。（请补充完善右图）5）、凸函数性：当条件概率分布｛p（刀1xi入给定时，平均互信息I€x；Y）是输入分布平均互信息量1€x；Y）是条件概率分布5）、凸函数性：当条件概率分布｛p（刀1xi入给定时，平均互信息I€x；Y）是输入分布平均互信息量1€x；Y）是条件概率分布、例：给定 的联合概率分布，如表所示。求:第三章信源及信源熵信1源的分类弄清楚以下信源分类的标准）离散无记忆信源随机过程：波形信源„平稳信源„离散平稳信源„离散有记忆信源…记忆长度无限€I记忆长度有限也尔科夫信源连续平稳信源非平稳信源3离散多符号信源、离散平稳信源的特征：统计特性不随时间推移而变化。随机过程：波形信源„平稳信源„离散平稳信源„离散有记忆信源…记忆长度无限€I记忆长度有限也尔科夫信源连续平稳信源非平稳信源3离散多符号信源、离散平稳信源的特征：统计特性不随时间推移而变化。2熵率：随机变量序列中，对前个随机变量的联合熵求平均：H€X）=—H€XX…X）称为平均N N1 2N符号熵。如果当N—a时上式极限存在，则limHw€x）称为熵率，或称为极限熵，记为NN—aH=limHaN—aN、离散平稳信源的几点结论（小题）：条件熵H匕1X1X2…XN_11）、的增加是递减的（即已知条件越多，不确定性越少）；2）、给定时平均符号熵大于等于条件熵，即hn€x）'H（xn1x1x2…xn丿；平均符号熵HN女口果H（X）＜a，则H=limH1 aN—aNH=limH（X）=limH（XIXX…X）3）、4）、号有记忆，条件概率p€x21X1，求熵率，并比较H（X2IX丿、2H（X1X2）和H（X）的大小。第五章无失真信源编码1信源编码的相关概念1、各种码的分类：(1)、分组码和非分组码：、分组码将信源符号集中的每个信源符号固定地射成一个码字i1、各种码的分类：(1)、分组码和非分组码：、分组码将信源符号集中的每个信源符号固定地射成一个码字i(一个信源符号一一个码字)、非分组码又称树码，编码器输出的码符号通常与编码器的所有信源符号都有关。()、奇异码与非奇异码：非分组码奇异码码1分组码1… …非奇异码非唯一可译码唯一可译码1I非及时码定义若一种分组码中的所有码字都不相同,则称此分组码为非奇异码，否则称为奇异码。非奇异码是分组码能够正确译码的必要条件，而不是充分条件。(3)、唯一可译码与非唯一可译码：定义任意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为唯一可译码。条件：①、此码本身是非奇异的；②、对于任意有限的整数其次扩展码均为非奇异的。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。()、即时码与非即时码：定义无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码。条件：①、此码是唯一可译码；②、不需要通过接收到后面的码字才能译出前面的码字，在收到一个完整的码字后即可以及时译出。一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。5.、3变长码及变长信源编码定理1 不等式 不等式：()、 不等式：设信源符号集为 … 码符号集为 … 对信源进行编码，得到的码为 … 码长分别为，，…即时码存在的充要条件是为丫匕€1这称为i,1不等式(其中是被编码的符号个数；是信源个数；是码的长度)。这也就意味着即时码存在于二叉树的叶子节点处。()、 不等式：判断唯一可译码的条件与即时码条件一致，都是为r匕€1，条件并不比即时i,1码判断条件宽松。2、唯一可译码的判别准则：定理一个码是唯一可译码的充要条件是 …的并集中没有中的码字。设为码字集合，我们要构造尾随后缀的集合，，…和。()、是中所有码字尾随后缀的集合：若中的码字W.是码字W的前缀，即WWA，则将尾随j i ij后缀列为中的元素，所有这样的尾随后缀构成了；()、考查和两个集合，若中任意码字是中元素的前缀，或者中任意元素是中码字的前缀,则将其相应的尾随后缀放入集合F.,；i„1

（3）、F€Uf（即为码的尾随后缀集合）；..（4）、若中出现了中的元素，则算法终止，判断不是唯一可译码；若出现F1为空集或F1中的元i+1 i+1素在中已经全部存在了，则算法终止，判断是唯一可译码。总而言之，判断一个码是唯一可译码的充要条件是中不含有中的码字。3、例:设消息集合共有个元素 他们分别被编码为，，， ， ，de，bbd判断是否为唯一可译码。变长码的编码方法、香农编码的方法：p(s)„p(s)„p(s)„-12计算各个信源符号的累加概率F(s[…p(s)iki€1,2,…,q；k€1i=i，2,•…，q计算第i个消息的码长1；i4)将累加概率FC.）变换成二进制小数得到其码字。将累加概率FC.）变换成二进制小数，取小数点4)ii后l.位数作为第i个信源符号的码字。i€[-logp(s刀二3€[-logp(s刀二34、二元霍夫曼编码的方法：（）、信源的个消息概率从大到小排序p(、二元霍夫曼编码的方法：（）、信源的个消息概率从大到小排序p(s)„p(s)„…„p()12（2）、0，只包括q1码分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到-个1符号的新信源。q香农编码信源符号$i概率pc)i累加概率Fc）i-logp(s)i码长l.i二元码源符号的二元码码长144，因此码长取（3）、将新信源仍按概率从大到小排序，再将最后两个概率最小的信源符号分别用0和1码符号表示，合并成一个新符号，这样形成了 个符号的新信源。（）、依次继续下去，直至信源最后只剩下两个信源符号为止。将这最后两个信源符号用和表示。

5）、从最后一级缩减信源开始，进行回溯，将每次标注的码符号连接起来就得到各信源符号所对应的码符号序列，即相应的码字。）、信源的个消息概率从大到小排序。即p）、信源的个消息概率从大到小排序。即p(s),、例5.：7以例5.为6例编制二元霍夫曼码。霍夫曼编码码字信源符号编码过程码长01费诺编码的过程：2）、将依次排列的信源符号以概率分为两组，使两组的概率和基本相等。并赋予符号0和1。（）、再分组，使划分后的两组的概率和基本相等，并赋予符号和1（）、重复，直至每组只剩下一个信源符号为止。（）、信源符号对应的码符号序列即为费诺码。、例：信源与例 和例 相同，请编制费诺码。费诺码信源符号概率第次分组第次分组第次分组第次分组二元码码长、总结：霍夫曼码是即时码，他的两个特点：（1）保证了概率大的信源符号对应的码长小，概率小的信源符号对应的码长大，充分利用了短码（）每次缩减信源的最长两个码字有相同的码长，最后一位码符号不同。（码长相差的小）编码最短，传输效率最高。8、习题5：：8下面是4种不同的编码：请计算：（）、此码的码长分布是否满足 不等式？（）、此码是否为即时码？如果不是，请说明。（3）、此码是否为唯一可译码？如果不是，请说明（可以画出树图说明）。实5用的无失真编码方法各种编码的应用（小题）：（）、游程编码（ ）应用于:（）、码应用于： I（）、算术编码应用于： ；

参考答案:①、I(a)，—log0.064，3.96bit2I(c)，—log0.022，5.51bit2、由于前后字母出现是互相独立的，“”出现的概率为 *所以I(ac)，—log(0.064*0.022)，—(log0.064„log0.022)，I(a)+I(c)=9.47bit222即两个相对独立的事件的自信息量满足可加性，也就是由两个相对独立的事件的积事件所提供的信息量应等于他们分别提供的信息量之和。例：H(XY)，bog丄+1log丄+丄】og丄，2log4+1log2，-x2+-x1例：H(XY)，bog丄+1log丄+丄】og丄，2log4+1log2，-x2+-x1，3比特/联合符号4 1/4 4 1/4 2 1/2 4 2 4 2 2由联合概率分布得的边缘概率分布：P{X=0}=2,p{X=1}=2和条件概率分布p(y.lxJ(如表 所示)，得到H(YIX，0)，1,H(YIX，1)，0和H(YIX)，-x1+-x0，-。注意到H(Y),°8113…2,H€y1x)。(a)(b)X01r01P(X)21Y)123333例2.1:5由(I)2 3H(X)=~log2—+—\ogi3=0.918=H(Y)(2)H(XIY)=^H(XIF=0)+W丹(XIr=1)=0.667=H(Y\X)(3)H(XX)=3X^log.3=1585比掬符号(4)H(Y)-H(Y\X)=0251比恸符号(5)/(X;Y)=H(Y)-H(FlX)=0251比特/符号1)、熵率：H^，H2，H€X2IX1)，0.870比特/符号；()、如果不考虑符号间的相关性，则信源熵为H(X)，-log4„4log9„11log36，1.542比特/符号4 9 436 11由此可见，H€x2|〜)<H€x)=H€x2)，这是由于X「X2之间存在统计依赖关系，在X1已知的情况下，X2的不确定性减少，即条件熵H€x2|X])小于无条件熵H€x)。因此在考虑序列符号之间相关性之后，序列的熵减小。如果信源输出的符号序列看成是分组发出的，每两个符号作为一组，这样可以把符号序列看成是由一个新信源发出的，新信源每次发出的是由两个符号构成的消息。新信源的数学模型是一个二维的随机变量，新信源的熵为H€X1X2)，H€X1\H(X2IX1)，1.542+0.870，2.412比特/两个符号，平均符号熵为-HX丿，1.206比特/符号，由此可见大小关系为HX1X’)