信息论基础复习提纲

1、WOR格式哈尔滨医科大学生物信息科学与技术学院第一章 绪论1、什么是信息？香农对于信息是如何定义的。答：信息是事物运动状态或存在方式的不确定性的描述（Information isameasureofone'sfreedomofchoicewhenoneselectsamessage）。编码器U -2 二， FF IL-IU E信崔|倍号+干扰消息干扰噪声源2、简述通信系统模型的组成及各部分的含义。答：（1）、信源：信源是产生消息-的源。信源产生信息的速率 -熵率。（2）、编码器： 编码器是将消息变成适合于信道传送的信号的设备。包括信源编码器（提高传输效率）、信道编码器（提高传输可靠性）

2、调制器。（3）、信道：信道是信息传输和存储的媒介。（4）、译码器：译码是编码的逆变换，分为信道译码和信源译码。（5）、信宿：信宿是消息的接收者（人或机器）。3、简述香农信息论的核心及其特点答：（1）、香农信息论的核心：在通信系统中米用适当的编码后能够实现咼效率和咼可靠性的信息传输，并得出了信源编码定理和信道编码定理（2）、特点：、以概率论、随机过程为基本研究工具。 、研究的是通信系统的整个过程，而不是单个环节，并以编、译码器为重点 、关心的是最优系统的性能和怎样达到这个性能（并不具体设计系统） 、要求信源为随机过程，不研究信宿。第二章信息的度量(帀 (1logpxilogpxi2.1自信息和互

3、信息1、自信息（量）：Ixi（1）、定义：一个事件（消息）本身所包含的信 息量，它是由事件的不确定性决定的。某个消息xi出现的不确定性的大小定义为自信息，用这个消息出现的概率的对数的负值来表示:专业资料整理WOR格式信息论基础第-1- 页共11页专业资料整理WOR格式(2)、性质：、I哈尔滨医科大学生物信息科学与技术学院xi(是)幽 的严格递减函数。当px1 px2时Ix1 Ix2概率越小，事件发生的不确定性越大，事件发生以后所包含的自信息量越大。、极限情况下，当畀 法pxi星号:J石0时Ixi ;当pxi 一 1 时Txi 戶 0。、两个相对独立的不同的消息所提供的信息量应等于它们分别提供的

4、信息量之和，即自信息论满足可加性。§ 戸pfx2 ) £) (p*lx卅¥仪)lx2。(3)、例 2.1 :、英文字母中“ 计算他们的自信息量a”出现的概率为0.064，“ c”出现的概率为0.022，分别、假定前后字母出现是互相独立的，计算ac ”的自信息。、假定前后字母出现不是互相独立的，当 算“a”出现以后，“a”出现以后，“ c”出现的概率为0.04，计c ”出现的自信息量。2、互信息：ij一个事 件- i -yj所给出关于另一个 事件-jpx|yijxi的信息定义为互信息， 用I()一( j jixi;y j表示:Ix;yIIx|ylogIy Iy|xp

5、xi丿py( |x)j log pyjpxyi ilogpxipyj2.2平均自信息1、定义：随机变量X的每一个可能取值的自信息IxiH(X)qEI(x i)i1p(x i)log 2p(x i)的统计平均值定义为随机变量X的平均自信息量2、熵函数的性质:(1)、对称性：(2)、确定性：(3)、非负性：4)、 扩展性：(5)、连续性：(6)、递推性：(7)、极值性：H(p1,P2,Pq)H(P2,P1,Pq) -H(Pq,p1,Pq1)H(1,0)H(1,0，0)-H(1,0, - 0)=0H(P)H(P 1,P 2,P q)0Gbl -& *1.H W arh-WirilimH(p,

6、p,_p；r -9一) 一Hp,p,p)0 q112q - 12 qlimH(p 1,p 2,Pq1,pq) H(P1，P2,Pq)0TH(p1,p2,pn1,q1,q2qm)H(p1,p2,pn)pnH(q1,q2,qm一 PnPnPnH(P1,P2,Pn)pH (1 11) log 2nnnnfx 1(1 )x 2f(x 1)(1)f(x2)( 8)、上凸性：二崔3、联合熵：联合自信息的H(XY)n mp(XiyJI(x iyj)p(Xiyj)log 2p(XiyJ专业资料整理WOR格式数学期望。它是二维随机i1 j1i1 j1变量XY的不确定性的度曰.量。由于不同的4、条件熵：就得出给定

7、，是变化的，对的所有可能值进行统计平均，xH(Y/x i)X时，丫的条件熵H(Y/Xi)H(Y/X)P(XiyJlog 2p(yj/Xi)H(X/Y)p(Xiyj)log 2p(Xi/yj)i j信息论基础第-2-页共11页i j专业资料整理WOR格式哈尔滨医科大学生物信息科学与技术学院5、各类熵之间的关 系：(1)、联合熵与信息熵、条件熵之间 的关系:='T'H(XY) H(X) H(Y/X)推广：HX1X2 XN - HX1 HX 2/X 1HXN/X1X2XN1当二维随机X,Y相互独立时，联合熵一变量等于X,Y各自熵之和。H(XY) H(X) H(Y)(2) 、条件熵与信

8、息熵的关:-系：H(x/Y) H(X); H(Y/X) H(Y)。蕴：営H(Y)当X、丫相互独立时等号成(3) 、联合熵与信息熵的关系：H(XY)H(X) 立。推广到N个随机变量:j )兰HX1X2 XNHX1 HX2HXN2.1所示，求联合熵HXY和条件熵HY|X的联合概率吃y表 2.1X,丫 分布PXY -()X0 11/pxip )41/41/1/26、例2.5 :随机变量X，丫的联合概率分 布如表120T/2表 2 2 条件概率分布 PYIXIX丫X0 11/ 1/3/41/41pyj022110I )2.3平均互信息1、定义：从整体上表示从一个随机 在XY的联合空间中的统计平均值为

9、随机变一乙IX;Ympx;y*.)Ix;y i-Y所给出关于另一个随机变量X和丫间的平均互信(息° ()n mI xi;yji1mj1i1j1px；y j log pxi|yjipxpx;yilog 1ii1j1px( 徉Y后，对随机变条件熵H X|Y表示给定随机变量量信息是收丫前后关于X的不确定度减少的量，也到就是从X仍然存在的不确定度。所丫关于X的平均以互丫获得的关于X的平均信息量1pxi;yjlogH XH X|Yi1 j1pxi |yj2、平均互信息的性质:专业资料整理WOR格式(1 )、非负性:IX;丫 0信息论基础第-3-页共11页专业资料整理WOR格式哈尔滨医科大学生物

10、信息科学与技术学院（2）、互易性（对称性）：I _X;丫 IY;X ；FTTHXY-)*r（3）、平均互信息与各类熵之间的关系：IX；YHX _HX/Y HY _ HY/X 一 HX;当X,Y统计独立时，IX;丫- 0。（请补充完善右图）(4(5）、极值性：IX;Y）、凸函数性:、当条件概率分布、对于固定的输入 分布-H X,IX;YHY ；给定时，平均互py|x 信息j iIX;Y是输入分布 pxi的上凸函数。X;Y是条件概率分 pxi，平均互信息量I 布pyj|xi的下凸函数。3、例2.15 :给定X,Y的联合概率分布，如表所示。求:、H(X),H(Y) ； (2)、H(X|Y),H(Y|

11、X)(4)、H(Y)-H(Y|X)；、l（X；Y）；Lxd1 |0 11/31-t1/3第二章信源及信源熵3.1信源的分类（弄清楚以下信源分类的标准）r离散无记忆信源记忆长度无限II记忆长度有限马尔科夫信源1IJ离散平稳信源平稳信源离散有记忆信源随机过程：波形信源富|I斗连续平稳信源非平稳信源3.3离散多符号信源1、离散平稳信源的特(戶一 cHX1HXX2xr称为平均)NX称为熵率，或称为极限熵，记为征：统计特性不随时间推移而变化2、 熵率：随机变量序列中，对前N个随机变量的联合熵 求平均：符号熵。如果当 N时上式极限存在，则limHN NHlimHNXoN3、离散平稳信源的几点结论 （小题）

12、专业资料整理WOR格式信息论基础第-4-页共11页专业资料整理WOR格式哈尔滨医科大学生物信息科学与技术学院(1) 、条件熵HXN IX1X2XN1随N的增加是递减的(即已知条件越多，不确定性越少)、N给定时平均符号熵大于等于条件熵nxhXNNXix2(3)、平均符号熵HNX随N的增加是递减的；Xni；存在，并且I d 'lXN1;(4) 、如果 Hx )v觸，贝y HlimH nX9PQXn|X 1X2NHlimN4、马尔科夫信源：信源在某一时刻发出某一符号的概率除与该符只与此前发出的有限个号有关外，1xl符号有关。M阶马尔可夫信源只与前面发出xl1192!90的m个符号有关，1阶马

13、尔可夫1/&信源只与前面一个符号有关。x302/119/115、例题3.3 :信源X的信源模型为Int x1 x2 x3 Xb1411P(X)4936输出符号序列中，只有前后两个符号有记忆，条件概率PX2|X1给出，求熵率，并比较HX|X1、11HX22和HX 的大小第五章无失真信源编码5.1信源编码的相关概念1、各种码的分类：(1)、分组码和非分 组码：、分组码：将信源符号集中的每个信 源符旦非分组码奇异码si固定地射 成一个码字wi。(一个信源符号一个码字)、非分组码：又称树码，编码器输出的码符号通常与 编码v%分组码非奇异 码非唯一可译码及时码唯一可译码非及时码器的所有信源符号都

14、有 关。(2) 、奇异码与非奇异码：定义若一种分组码中的所有码字都不相同异码。非奇异码是分组码能够正确译码的必要条件，而不是充分条件。(3) 、唯一可译码与非唯一可译码：,则称此分组码为非奇异码，否则称为奇专业资料整理WOR格式唯一可译码。N,其N次扩展码均为非定义任意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为 条件：、此码本身是非奇异的；、对于任意有限的整数奇异的。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。信息论基础第-5- 页共11页专业资料整理WOR格式哈尔滨医科大学生物信息科学与技术学院（4）、即时码与非即时码:定义无需考虑后续的码符号就可以从码符号序列中

15、译出码字，这样的唯一可译码称为即 时码。条件：、此码是唯一可译码；、不需要通过接收到后面的码字才能译出前面 的码字，在收到一个完整的码字后即可以及时译出。一个唯一可译码成为即时码的充要 条件是其中任何一个码字都不是其他码字的前缀。5.3、变长码及变长信源编码定理1、Kraft不等式McMillan不等 式：(1 )、Kraft不等式：设信源付S-s1,s2, ?sq,码符号集为对信源进行编号集为X-x1,x2,?xr,码，得q到的码为C-w1,w2, ?wq，码长分l1 ,即时码存在的充要条件别为l2?lq.是r l i 1这称为Kraft不等式（其中疋被编码的付号个q是信源个数；li是码的长

16、度）11。这也就意味着即时码存在r数；于二叉树的叶子节点处。q(2)、不等式：判断唯可译码的条件与即时码条件 致，1,条件并不比即McMillan都是r l i时i 1码判断条件宽松。2、唯一可译码的判别准则：定理一个码是唯一可译码的充要条件是F1,F2, ?的并集中没有 C中的码字。设C为码字集合，我们要构造尾随后缀的集合F1，F2，?和F。（1 ）、F1是C中所有码字尾随后缀的集 合：若C中的码字W是码字w的前缀，即w=wA则将尾随C中码字的前缀，素在F中已经全部存在了，则算法终止， 判断总而言之，判断一个码是唯一可译码的充 要条件是3、例5.4 :设消息集合共有7个元素s1,s2,s3,

17、s4,s5,s6,s7,deb， bbcde，判断是否为唯一可译码。5.4后缀A列为F1中的元素，所有这样的尾随后缀构成了F1 ；（2）、考查C和Fi两个集合，若C中任意码字是Fi中元素的前缀，或者 Fi 中任意元素是则将其相应的尾随后缀放入集合Fii ；（3） 、FFi （即F为码C的尾随后缀集合）；i（4）、若F中出现了C中的元素，则算法终C不是唯一可译码；若一止，判断出现Fii为空集或Fii中的元C是唯一可译码。F中不含有C中的码字。他们分别被编码为a，c，ad，abb， bad，!（；徉（:證z 3 f >变长码的编码方法1、香农编码的方法:专业资料整理WOR格式(1)、信源的q

18、个消息概率从大到小排序，psips2 psq；信息论基础第-6- 页共11页专业资料整理WOR格式哈尔滨医科大学生物信息科学与技术学院i1（2） .计算各个信源符号的累加概率Fs 一pski1,2,q；k1一亠1 -（3）.按公式ii log （i1,q 计算第i个消息的码长l i ；psi（4） .将累加概率（变换成二进制小数得到其码字。将累加概率（）变换成二进制小数，取FSi Fsi小数点'后l i位数作为第i个信源符号的码字7个信源符号的信源进行编码4时，先求第四个信S70.013、二元霍夫曼编码的方法：6.66宀 2 I :2、列5.6 :参照下表按以上步骤对一个有 例如当i果

19、符号的二元码码长丨4：丨4logps 43，因此码长取3.()香农编码-()信源符号si概率psi累加概率Fsilogps i码长1 i二元码S10.2002.343000S20.190.202.413001S30.180.392.483011S40.170.572.563100S5S60.150.100.742.743434101W00.9971111110（1）、信源的q个消息概率从大到小排序PS1PS2psq（2）、0，1码分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包括 q-1个符号的新信源。（）、将新信源仍按概率从大到小排序，再将最后两个概率最小

20、的信源符0和1码符号表3号分别用示，合并成一个新符号，这样形成了q-2个符号的新信源。（）、依次继续下去，直至信源最后只剩下两个信源符号为止。将这最后0和1表4两个信源符号用示。5）、从最后一级缩减信源开始，进行回溯，将每次标注的码符号连接起来就得 到各信源符号所对应的码符号序列，即相应的码字。4、例5.7 :以例5.6为例编制二元霍夫曼码。丨码字信源符号、X编码过程寸码长10S10.200.200.26 f9350.390.61 0211s20.190.190.20/0.260.3500.3912000s30.180.180.190.200 0.2613专业资料整理WOR格式信息论基础第-7

21、- 页共11页专业资料整理WOR格式哈尔滨医科大学生物信息科学与技术学院001s40.170.170.180 0.193010s50.150.15 0 0.17 130110s60.10 丽1 140111s70.01 15、费诺编码的过程:0和1。1 ）、信源的q个消息概率从大到小排序。即PS1PS2psq。（）、将依次排列的信源符号以概率分为两组，使两组的概率和基本相2等。并赋予符号（）、再分组，使划分后的两组的概率和基本相等，并3赋予符号0和1。（4）、重复，直至每组只剩下一个信源符号为止。（5）、信源符号对应的码符号序列即为费诺码。6、例5.9 :信源与 5.6和例5.7相冋，请编制费

22、诺 厉Im费诺码第1次分组X,/八 / tta、丄八 /1tZr*A-*-“ x / AZ X 厶信源符号概率第2次分组-第3次分组第4次分组一兀码码长S10.200002S20.191010010 3S30.1810113S40.1/0102S50.15101103S60.10110TTT04S70.011111147、总结：霍夫曼码是即时码，他的两个特点：（1）保证了概率大的信源符号对应的码长小，概率小的信源符号对应的码长大，充分利用了短码；（2 ）每次缩减信源的最长两个码字有相同的码长，最后一位码符号不同。（码长相差的小）编码最短，传输效率最咼。&习题5.8 :下面是4种不同的编

23、码：000,10,00,11 ; 100,101,0,11 ；01,100,011,00,111,1010,1011,1101 ; 01,111,011,00,010,110请计算：（1）、此码的码长分布是否满足Kraft-McMillan不等式？（2）、此码是否为即时码？如果不是，请说明。（3）、此码是否为唯可译码？如果不是，请说明（可以画出树图说明）。5.5实用的无失真编码方法各种编码的应用（小题）：（1）、游程编码（REL,REC 应用于：BMPTIFAVI;(2)、LZW码应用于：GIFZIPARC;(3)、算术编码应用于:JPEG200Q参考答案专业资料整理WOR格式信息论基础第-8

24、- 页共11页专业资料整理WOR格式哈尔滨医科大学生物信息科学与技术学院log 20.0643.96bitl(a)例2.1 :、l(c) log 20.02 25.51bit、由于前后字母出现是互相独立 的，“ac”出现的概率为0.064*0.022(log 20.064log 20.022),所以l(a)+l(c)=9.47bitl(ac) ' log 2(0.064*0.022)即两个相对独立的事件的自信息量满足可加性，也就是由两个相对独立的事件的积事件所提供的 信息量应等于他们分别提供的信息量之和。l( c )log 20.044.64bit、 变小。“ a”出现的条件下，出现的频率变大，它的不确定性例 2.5 :(>- HXY1log4 由联合概率分 布得11log11/441/4 2X的边缘概率分 布：1log11/22log44 k1log22 二表2.2所示)，得到 HY|XA I-=注意到HYH1PX)-10 1,HY|XA T 二01,PX12 -0.81131 HY|X22 112和条件概率分 12 JJ魏1禾口0 和 HY|X3比特/联合符耳2pyj|xi (如10。2例2.15 :由 X,Y(1) W( X) = &