信息论基础第24次课_总复习

信息论基础——总复习第2章信源熵自信息量：I(ai)=-logp(ai)信源熵：信源的平均信息量条件熵：2211()[()][log]()log()()niiiiiHXEIaEpapapa11()[()]()log()mnijijijjiHXYEIabpabpab11()[()]()log()nmjiijjiijHYXEIbapabpba损失熵噪声熵联合熵：平均互信息：11()()log()nmijijijHXYpabpab11()(;)()log()nmijijijipabIXYpabpa11()(;)()log()nmjiijijjpbaIYXpabpb第2章信源熵最大离散熵定理：若信源中包含n个不同离散消息，则当信源等概率时信源熵H(X)取得最大值log2n平均互信息I(X;Y)是输入信源概率分布的上凸函数是信道转移概率分布的下凸函数。{(),1,2,,;1,2,,}jipbainjm第2章信源熵多符号离散平稳无记忆信源亦称为单符号离散平稳无记忆信源的扩展信源。N维离散平稳信源()()NHXNHX121321112121()()()()()()NNNNHXHXXXXXXXHXHHHXXXXXX平均符号熵：)(1)21NNXXXHNXH（第2章信源熵马尔可夫信源：m阶马尔可夫信源：001001110.80.20.50.50.50.20.50.8111()mmmHHXXX第2章信源熵各态历经定理由状态转移图可求状态极限概率11()()()1,2,,()0,()1mmnmjijiiniiipspspssjnpsps马尔可夫信源的状态极限概率是方程组满足条件的唯一解1.定长编码定理定长编码定理：一个熵为H(X)的离散无记忆信源X1X2…Xl…XL，若对信源长为L的符号序列进行定长编码，设码字是从m个字母的码符号集合中，选取K个码元组成Y1Y2…Yk…YK。对于任意ε0，δ0只要满足则当L足够大时，必可使译码差错小于δ，即译码错误概率能为任意小。反之，若则译码差错一定是有限值，而当L足够大时，译码几乎肯定出错（译码错误概率近似等于1）。2log()KRmHXL2log()2KRmHXL22()()1loglogHXHXKmm对离散无记忆信源，符号熵为H(X)，对信源进行m元变长编码，一定存在无失真的信源编码方法，满足：其码字平均长度K)()(XHRXH(2.4.5)(2.4.6)变长编码定理其码字平均信息率R满足：本章考点1.各种熵的计算。如：P69.2.11;2.一阶马尔可夫信源的状态极限概率及极限熵。如：P69.2.16,2.173.各种熵的性质：信源熵：非负性、最大离散熵定理、上凸性、确定性。平均互信息：非负性、极值性、凸函数性、数据处理定理、各种熵之间的关系（和差关系、大小关系）连续信源熵：可为负、平均互信息非负。4.P68.2.8、2.14.5.离散无失真信源编码定理。第3章信道容量当信道特性p(bj/ai)固定后，I(X;Y)随信源概率分布p(ai)的变化而变化。调整p(ai)，在接收端就能获得不同的信息量。由平均互信息的性质已知，I(X;Y)是p(ai)的上凸函数，因此总能找到一种概率分布p(ai)（即某一种信源），使信道所能传送的信息率为最大。信道容量C：在信道中最大的信息传输速率，单位是比特/信道符号。()()maxmax(;)iipapaCRIXY具有扩展功能的有噪无损信道具有归并性能的有损无噪信道38372625241312110000000000000000ababababababababppppppp2()()max(;)max()logiipapaCIXYHXn100010010001001第3章信道容量2()()max(;)max()logiipapaCIXYHYm如果一个信道矩阵具有可排列性，则它所表示的信道称为对称信道若信道矩阵P的行是可排列的，但列不可排列，如果把列分成若干个不相交的子集，且由n行和各子集的诸列构成的各个子矩阵都是可排列的，则称相应的信道为准对称信道。第3章信道容量11113366111166331111336611113636例：信道输入符号集X={x1,x2}，输出符号集Y={y1,y2,y3,y4}，给定信道转移概率矩阵，求该信道的信道容量C。解：这是一个准对称信道，当X等概分布，即p(x1)=p(x2)=1/2时，达到信道容量1111428811118248P12()()1/2(;)pxpxCIXY(;)()(/)IXYHYHYX12()()1/231311111(;),,,,,,16216842881.7806-1.75=0.0306(/)pxpxCIXYHHbitsymbol故而此时，信宿端概率为111142880.50.53/161/23/161/811118248连续信道的信道容量C：信源X等于某一概率密度函数p0(x)时，信道平均互信息的最大值，即对于高斯加性信道第3章信道容量);(max)(YXICxpC1log(1)2xNPCPNxPP信噪功率比香农公式设信道的频带限于(0,W)；根据采样定理，如果每秒传送2W个采样点，在接收端可无失真地恢复出原始信号；香农公式：把信道的一次传输看成是一次采样，由于信道每秒传输2W个样点，所以单位时间的信道容量为)1log(NxtPPWC(bit/s)信道编码定理信道编码定理：若一离散平稳无记忆信道，其容量为C，输入序列长度为L，只要待传送的信息率RC，总能找到一种编码。当L足够长时，译码差错概率ep为任意正数，反之，当RC,任何编码的ep必大于0，当1ep,L本章考点1.几种特殊信道的信道容量。2.准对称离散信道的信道容量。P99.3.7(4)3.高斯加性信道的信道容量，香农公式。4.信道编码定理。第4章信息率失真函数信道的传递概率矩阵失真矩阵121111222212,,,,,,,,,mmmnnnbbbaaabbbaaabbbaaappppppppp111212122212(,)(,)...(,)(,)(,)...(,)............(,)(,)...(,)mmnnnmdabdabdabdabdabdabDdabdabdab01110111011[(,)]()(/)(,)nmijiiiijijDEdabpapbadab第4章信息率失真函数汉明失真：平均失真度（2）信息率失真函数R(D)在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。从接收端来看，就是在满足保真度准则的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的最小值。当p(ai)一定时，互信息I是关于p(bj/ai)的下凸函数，存在极小值。因而在上述允许信道PD中，可以寻找一种信道，使给定的信源经过此信道传输后，互信息I(X；Y)达到最小。该最小的互信息就称为信息率失真函数R(D)，即(/)()min(;)min(;)jiDpbaPDDRDIXYIXYDD率失真函数的定义域信源最小平均失真度Dmin：对于每一个ai，找出一个bj与之对应，使d(ai,bj)最小，这相当于在失真矩阵的每一行找出一个最小的d(ai,bj)。只有当失真矩阵的每一行至少有一个0元素时，信源的平均失真度才能达到下限值0。0()()DRDHXmin1()min(,)niijjiDpadab计算Dmax的值令试验信道特性p(bj/ai)=p(bj)(i=1,2,…,n)这时X和Y相互独立，等效于通信中断，因此I(X;Y)=0，即R(D)=0。满足上式的试验信道有许多，相应地可求出许多平均失真值，这类平均失真值的下界，就是Dmax。max()11()()111min()()(,)min()()(,)min()minjjjnmijijpbijmnmjiijjjjpbpbjjijDpapbdabpbpadabpbDD1()(,)niijjipadabD这里令当R(D)等于0时，对应的平均失真最大，也就是函数R(D)定义域的上界值Dmax。当DDmax时，从数学意义上讲，因为R(D)是非负函数，所以它仍只能等于0。max()0DDRD率失真函数的性质连续性下凸性非负性单调递减本章考点1.信息率失真函数的含义。2.信息率失真函数的定义域。对应到最大失真度和最小失真度的信道矩阵。P129.4.1、4.2、4.103.信息率失真函数的性质：下凸性、连续性、非负性、单调递减。4.保真度准则下的信源编码定理。第5章信源编码异前置码的充要条件：Craft不等式在Huffman编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使码方差最小。11inkim位置123456789字符ABBABABAC步骤位置输出码字词典初1A始2B化3C输入数据流：编码过程：114A1225B2336B2447A4568A7693(最后字符C)BBABABACLZW算法举例A律特性11ln1ln110ln1)(xAAxAAxAxAxfA式中：x为归一化信号值，当x≥0时函数取正，否则取负，一般取A=87.6。为实现方便，大多采用13折线来逼近A律特性。非均匀量化1f(x)7/86/85/84/83/82/81/8011/21/41/8xx划分为8个不均匀的段落：其中第8段占量化范围的1/2，除第1段外，其余各段的宽度均按1/2倍率减小，即第7段占1/4，第6段占1/8，…，第2段占1/128；第1段也占1/128。0~1量化范围的13折线A律特性：这样，0~1量化范围内共划分出了8*16个不均匀的量化间隔；如果将最小的量化间隔记为Δ，则Δ=1/(128*16)，相应最大的量化间隔为64Δ=1/32。13折线A律非均匀量化编码也采用定长折叠二进制码，并将码长确定为8位；其8位码元安排如下：最高位C7为极性码，用以表示信号极性，其准则与均匀量化相同；以下三位C6C5C4为段落码，用以表示|x|落在正方向的第几个段落；最后四位C3C2C1C0为段内码，用以表示|x|在段内落在第几个量化间隔。每段再均匀地分为16份，每一份作为一个量化间隔。采用13折线A律非均匀量化编码，设最小量化间隔为Δ，已知某采样时刻的信号值为x=635Δ，试求其非均匀量化编码c，并求量化噪声e。解：①635Δ0，故极性码为1。②因为512Δ≤635Δ≤1024，所以635Δ在第7个段落，段落码为110；③由于(1024-512)/16=32，所以该段落内每个量化间隔为32Δ，635Δ512Δ=123Δ最接近32Δ的4倍，所以段内码为0100。故13折线A律非均匀量化编码为c=11100100。量化噪声为e=|123Δ128Δ|=5Δ一、增量调制增量调制是预测编码中最简单的一种，增量调制原理如下，其中(a)为发送端，(b)为接收端。1比特量化+nx~nxqnd-niiqnd1编码ncnd++qndnxniinx1nx~nc译码(a)(b)【例5.3.1】已知某归一化信号序列，设初始量化dq0=0，量化增量Δ=0.125，求其增量调制编码和量化值。2.0,23.0,15.0,05.0,