信息论与编码傅祖云讲义学习教案

1、会计学1信息论与编码信息论与编码(bin m)傅祖云讲义傅祖云讲义第一页，共64页。第1页/共63页第二页，共64页。n本章只限于研究一个输入端和一个输出端即单用户信道，以无记忆、无反馈、恒参离散信道为重点。第2页/共63页第三页，共64页。两端(lin dun)（单用户）信道多端（多用户）信道无反馈信道反馈信道固定参数信道时变参数信道离散信道连续信道半离散或半连续信道波形信道第3页/共63页第四页，共64页。信道XY),.,.,()(),.,.,(121NiNYYYYxyPXXXXraaX,.,:1sbbY,.,:1yxyP1)(图3.1 离散(lsn)信道数学模型 根据信道的统计特性即条件

2、概率 的不同，离散信道又可分成三种情况。)(xyP第4页/共63页第五页，共64页。种类型。信道输出不但与输入有关(yugun)，还与其它时刻的输入和输出有关(yugun)，这样的信道称为有记忆信道。)(0)(1)()(xfyxfyxyPxfyNiiiNNxyPxxxyyyPxyP12121)().()(第5页/共63页第六页，共64页。raaa,.,21sbbb,.,21)()()(ijijabPaxbyPxyPYbababaXsr.2211)(ijabP第6页/共63页第七页，共64页。a1=0a2=1b1=0b2=11-p1-pppXYppPabP1)00()(11ppPabP1) 11

3、 ()(22pPabP) 10()(21pPabP)01 ()(12pppp111010第7页/共63页第八页，共64页。qqpp1001101200101pq1-p1-q2第8页/共63页第九页，共64页。能性小得多，所以(suy)，假设n是较合理的。0110 20 210) 10()01(xypxyp第9页/共63页第十页，共64页。Pabpabpabpabpabpabpabpabpabpaaabbbrsrrssrs)()()()()()()()()(2121221221112121)()()()()(jijijijibapbpabpapbap第10页/共63页第十一页，共64页。n上式说

4、明，在信道输出端接收到任一符号n一定是输入符号 , 中的一个输入信道。)(ijabp)(jibap)(iap)(jibap1()() (/)rjijiiP bp a p ba()(/)()ijijjP abP abP b1(/)1rijiP abjb1ara第11页/共63页第十二页，共64页。到输出n符号后，关于输入符号的信息测度。XriiixpxpapapXH)(log)()(1log)()(1riXjjjijijbxpbxpbapbapbXH1)(1log)()(1log)()(jbjb第12页/共63页第十三页，共64页。n（噪声）引起的。risjYXjijisjsjrijijijjj

5、jyxpxyPbapbapbapbapbpbXHbpbXHEYXH11,111)(1log)()(1log)()(1log)()()()()()(第13页/共63页第十四页，共64页。0)(YXH)()(XHYXH第14页/共63页第十五页，共64页。ny获得关于某事件x的信息量。它可取正值，也可取负值。n是的统计平均,所以。)()();(YXHXHYXI);(YXI);(yxI);(yxI);(YXI0);(YXI第15页/共63页第十六页，共64页。H(X|Y)H(Y|X)I(X;Y)H(X)H(Y)H(XY)()()()()()()();(XYHYHXYHYHXHYXHXHYXI第16页

6、/共63页第十七页，共64页。性，又称噪声熵或散布度H(X|Y)H(Y|X)I(X;Y)H(X)H(Y)H(XY);()()(YXIXHYXH);()()(YXIYHXYH)(YXH)(XYH第17页/共63页第十八页，共64页。0)()(YXHXYH)()();(YHXHYXI)()(YHXYH)()(XHYXH0);(YXI第18页/共63页第十九页，共64页。有当信道是无损信道时，信道疑义度等于0，互信息等于信源的熵。0);(YXI)();(XHYXI第19页/共63页第二十页，共64页。分布p(x)的型凸函数。);();(XYIYXI);(YXI第20页/共63页第二十一页，共64页。

7、干扰（噪声）最大，而输出端获得的信息量最小Imin。);(YXI)(xyp第21页/共63页第二十二页，共64页。a1=0a2=1b1=0b2=11-p1-pppXY11, 0)(xPX)()(1log1log)(1log1log)()()(1log)()()()()();(pHYHppppYHppppxPYHxyPxyPxPYHXYHYHYXIXXY第22页/共63页第二十三页，共64页。riijijabPaPbP1)()()(ppppyP)1 ()0(ppppyP)1 () 1()()(1log1log1log)(1log)();(pHppHppppppppppppYXI第23页/共63页

8、第二十四页，共64页。)(ppH1 , 0);(YXI)()(1log1log1log)(1log)();(pHppHppppppppppppYXI10I(X;Y)1H(p)0.50.510pI(X;Y)H()0.51H()第24页/共63页第二十五页，共64页。)()()();(symbolbitYXHXHYXIR)()(1)(1);(1sbitYXHtXHtYXItRt第25页/共63页第二十六页，共64页。(xnx)量为n一般仍称为信道容量。);(max)(YXICxP符号比特符号奈特);(max1)(YXItCxPttC第26页/共63页第二十七页，共64页。因此，二元对称信道的信道容

9、量为与X概率分布无关。n计算信道容量就是求极大值问题。)()();(pHppHYXI211)21()(HppH)(1);(pHYXI)()(1symbolbitpHC);(YXI第27页/共63页第二十八页，共64页。n信道容量为a1a2a3b2b1b3111100010001P信道(xn do)矩阵0)(YXH0)(XYH)()();(YHXHYXIsrCloglog第28页/共63页第二十九页，共64页。nn信道容量b1a1a2a3b2b3b4b5b611/21/23/53/101/10信道(xn do)矩阵100000010/110/35/30000002/12/1P0)(XYH0)(Y

10、XHrXHYXIClog)();(max第29页/共63页第三十页，共64页。n定性因噪声熵等于零而没有增加。a1a2a3aiai+1arb1b2b3无噪：有损：一个(y )X对应一个(y )Y，前向概率 非0即1，0)(XYH)(xyP一个Y对应多个X，后向概率不等于0或1，)( yxP0)(YXHsYHYXIClog)();(max第30页/共63页第三十一页，共64页。I(X;Y)H(X)=I(X;Y)H(Y)H(Y|X)有噪无损信道I(X;Y)H(Y)=I(X;Y)H(X)H(X|Y)有损无噪信道rXHClog)(maxsYHClog)(max第31页/共63页第三十二页，共64页。n

11、21,sppp21,rqqq3131616161613131P216131312161613121P3161316161613131P7 . 01 . 02 . 01 . 02 . 07 . 0P不是(b shi)对称信道第32页/共63页第三十三页，共64页。prprprprprpprprprprppP1111111111 pp第33页/共63页第三十四页，共64页。输出符号集的个数s有关。)/(),(log),()(max2121symbolbitpppHspppHYHCss21,sppp第34页/共63页第三十五页，共64页。n bit,只有当输入符号等概分布时才达到这个最大值 。313

12、1616161613131P)/(0817. 061log61231log3122)61,61,31,31(4log),(log21symbolbitHpppHsCs第35页/共63页第三十六页，共64页。)() 1log(log1logloglog1log11log1loglog)1,1,(log),(log21pHrprrPppprrPrPrPrPpprrPrPPHrpppHrCs)/()(1symbolbitpHC第36页/共63页第三十七页，共64页。)/()(1symbolbitpHC第37页/共63页第三十八页，共64页。3161316161613131P可划分(hu fn)为31

13、616131313161617 . 01 . 02 . 02 . 01 . 07 . 0P可划分为7 . 02 . 02 . 07 . 01 . 01 . 0第38页/共63页第三十九页，共64页。nkkksMNpppHrC121log),(log),(21spppkNkQkMkQkYyikxyPN)(kXikYyxyPM)(第39页/共63页第四十页，共64页。n这时C就是所求的信道容量。)(xP);(YXI);(YXI0);()(0);()(iiiiiipxCYxIbpxCYxIa其对于所有其对于所有 ip第40页/共63页第四十一页，共64页。);(YxIiiax iax );(YxIi

14、ixCYxIi);(sjjijijibPabPabPYxI1)()(log)();(第41页/共63页第四十二页，共64页。n求该信道(xn do)的信道(xn do)容量。2 , 1 , 0 1 , 010212101P01201111/21/2第42页/共63页第四十三页，共64页。0) 1 (,21)2()0(PPPsjjijijibPabPabPYxI1)()(log)();(212log)()0(log)0(); 0(yiyPyPyPYxI2log); 2(YxIi210)() 1(log) 1(); 1(yiyPyPyPYxI第43页/共63页第四十四页，共64页。iiiiiixp

15、YxIxpYxI的所有的所有02log);(02log);()/(12logsymbolbitC0) 1 (,21)2()0(PPP第44页/共63页第四十五页，共64页。n解：设输入概率分布54321,aaaaa21,bb101021210101Pb1a1a2a3b2110.5a4a5110.50)()()(,21)()(43251aPaPaPaPaP第45页/共63页第四十六页，共64页。sjjijijibPabPabPYxI1)()(log)();(riijijabPaPbP1)()()(21)()(21bPbP0);(2log);();(2log);();(35421YaxIYaxIY

16、axIYaxIYaxI)/(12logsymbolbitC0)()()(,21)()(43251aPaPaPaPaP第46页/共63页第四十七页，共64页。(b shi)布是唯一的。0)(,41)()()()(35421aPaPaPaPaP21)()(21bPbP)(2log);(),(2log);(35421axYxIaaaaxYxIiiii0)(,41)()()()(35421aPaPaPaPaP第47页/共63页第四十八页，共64页。1)(, 2 , 1)()(log)(11riisjjijijapriCbpabpabpsjsjjijijijriCbpabpabpabp11, 2 , 1

17、)(log)()(log)(第48页/共63页第四十九页，共64页。sjsjijijjijriabpabpbpCabp11, 2 , 1)(log)()(log)()(logjjbpC sjsjijijjijriabpabpabp11, 2 , 1)(log)()(第49页/共63页第五十页，共64页。n再根据就可解出达到信道容量的最佳输入概率分布p(ai)。1)(1sjjbpsymbolbitCsjj12logsjbpCjj, 2 , 12)(riijijsjabpapbp1, 2 , 1),(log)()(第50页/共63页第五十一页，共64页。分布。分布。4321,aaaa4321,bb

18、bba11/21/2111/41/41/41/4a2a3a4b1b2b3b42141041010000104104121P第51页/共63页第五十二页，共64页。21log2141log4141log412141410041log4141log4121log2141412143132421204132第52页/共63页第五十三页，共64页。)(32. 115log)2222(log220022symbolbitC1012)()()15log2(412bpbp104)()(32bpbp304)()(41apap3011)()(32apap第53页/共63页第五十四页，共64页。第54页/共63页第五十五页，共64页。迭代算法求解。第55页/共63页第五十六页，共64页。n对于无损信道剩余度CYXICYXIC);(1);(rXHlog)(1第56页/共63页第五十七页，共64页。第57页/共63页第五十八页，共6