信息電子學(xué)院實(shí)驗(yàn)指導(dǎo)書格式信息論

1、一信息論基礎(chǔ)一實(shí)驗(yàn)指導(dǎo)書童基均編寫適用專業(yè)：通信工程浙江理工大學(xué)信息電子學(xué)院二OO八年三月信息論是現(xiàn)代通信與信息工程的理論基礎(chǔ)作為電子信息科學(xué)與技術(shù)專業(yè)本科生的學(xué)科基礎(chǔ)課，本課程主要講授：信息的定義和測度、信源和信息熵、連續(xù)熵和信息變差、信道和互信息、平均互信息和信道容量、數(shù)據(jù)處理和信息測量理論、無失真信源編碼理論和編碼方法等內(nèi)容.本課程按“單符號離散信息系統(tǒng)”、“多符號離散信息系統(tǒng)”、“連續(xù)信息系統(tǒng)”三個(gè)“系統(tǒng)”層面，逐步深入展開，以嚴(yán)密的數(shù)學(xué)分析貫串始終.通過教學(xué)，使學(xué)生掌握信息理論的基本概念和信息分析方法，為今后進(jìn)一步研究信息科學(xué)和信息技術(shù)打下堅(jiān)實(shí)的理論基礎(chǔ).實(shí)驗(yàn)一：離散信道容量的迭代計(jì)

2、算實(shí)驗(yàn)學(xué)時(shí)：3實(shí)驗(yàn)類型：（演示、驗(yàn)證、綜合、"設(shè)計(jì)、研究）實(shí)驗(yàn)要求：(V必修、選修)一、實(shí)驗(yàn)?zāi)康耐ㄟ^本實(shí)驗(yàn)的學(xué)習(xí)，理解和掌握信道容量的概念和物理意義；了解信道容量的計(jì)算方法尤其是迭代計(jì)法；采用計(jì)算機(jī)編程實(shí)現(xiàn)迭代算法二、實(shí)驗(yàn)內(nèi)容信道容量的概念和物理意義；信道容量的計(jì)算方法；采用計(jì)算機(jī)編程實(shí)現(xiàn)信道容量的計(jì)算三、實(shí)驗(yàn)原理、方法和手段1 離散信道的物理模型為：Xp(Y/X)|Y信道容量定義為平均互信息的最大值：C二maxI(X;Y).2 信道容量表征了一個(gè)信道傳送信息的最大能力，實(shí)際中傳送的信息量小于信道容量，否則傳送過程中出現(xiàn)錯(cuò)誤3由信道容量的定義可知，l(X,Y)的值由信道的傳送概率決定

3、的，因而信道的傳遞概率決定了信道的信道容量給定了信道的傳遞概率，可以通過推導(dǎo)方法求得信道的信道容量，一般可以求出傳遞效率達(dá)到信道容量時(shí)候的輸入信號的分布，但是這種方法不方便計(jì)算機(jī)實(shí)現(xiàn)4迭代法，便于計(jì)算機(jī)實(shí)現(xiàn)：迭代法分成三個(gè)模塊，一個(gè)迭代計(jì)算反向?qū)嶒?yàn)信道P(x|y)，另一個(gè)迭代計(jì)算p(x)，第三個(gè)檢查一次迭代前后信道容量誤差的變化是否小于檢測值(可取0.0001),如果小于檢測值則停止計(jì)算，輸出結(jié)果.二maxI(X，Y)二max、Px(x)PY|x(y|x)log良(x)R|x(y丨x)Px(x)'Px(x)R|x(y|x)X=m(ax送xyPx(x)PY|x(y|x)log&I

4、X(y1X)、Px(x)R|x(y|x)XTaxmax)yPx(x)PYix(y|x)log信道容量的迭代計(jì)算具體如下：求信道容量C就是在Pi的約束下，求l(X;Y)的極大值.為計(jì)算方便，重寫下l(X;Y)式，公式中的對數(shù)取自然數(shù).PjI(X,Y)八'PiPjlnijEPiPji首先引入反條件概率，即(1)Pxiy(a|bj)=qji(2l(X,Y)八'PiPjlnqijPi(3)迭代算法的要點(diǎn)是，當(dāng)信道固定(即口固定)時(shí)，把l(X;Y)看成是Pi和qji的函數(shù)，用公式(3)進(jìn)行信道容量計(jì)算的迭代每一次迭代有兩步組成：(a)將P(n)固定，在約束qji=1的條件下變動(dòng)qji，得

5、到I(X;Y)的極大值，記為iI(X,Y)二C(Pi(n);q(in)=C(n,n)；此時(shí)qf滿足(2)式，重寫為:i(4)(b)(b)將q(in)固定，在約束EPi=1的條件下變動(dòng)p，得到I(X;Y)的極大值，記為il(X,Y)=C(P(n4h);q律)=C(n+1,n)；此時(shí)p陽)滿足:(n1)Pi丿XPij|nq(in)ejZPjlnq(in)'eji(5)與(5)是迭代的基本公式先取一組p(n)(n=1)的初始值，通常選取均勻分布，由(4)計(jì)算q律，再將此值代入(5)計(jì)算p(n1)，依此反復(fù)計(jì)算下去每次迭代都要利用(3)計(jì)算I(X;Y)的值.可以設(shè)置門限值，當(dāng)相臨的兩次計(jì)算值I

6、(X;Y)小于門限值時(shí)，就結(jié)束迭代過程，此時(shí)I(X;Y)的值就是信道容量C.可以采用下述方法，避免計(jì)算反向條件概率，使算法簡化：將（4）代入（5）得其中其中將（6）p(n1)ZPijln(Pj/q(n)(n)jP；e瓦Pijln(Pij/q(n)rn)eji(n)qj八Pi(n)Piji（5）代入（3）,得(6)C(p(T；q(in)C(p(T；q(in).二Pjln(Pij/q(n)(n)jP()ej(8)現(xiàn)將算法歸納如下:設(shè)信道輸入輸出符號集的大小分別為r，s,且&為一個(gè)小的正數(shù).且初始概率分布為均勻分布，即設(shè)pi=1/r計(jì)算qjPiPij;'二Pijln(Pj/qj)計(jì)算

7、：j二ej,i=111,r；1) 計(jì)算U=Pri；i2) 計(jì)算L"og2(u),町=log2(m?x(：J)；若(IU-IL)<£,轉(zhuǎn)到6),否則Pi二p/uir;返回1)輸出信道容量的值C=Il(比特/符號)四、實(shí)驗(yàn)數(shù)據(jù)源P(a1)=p(a2)=0.5五、實(shí)驗(yàn)組織運(yùn)行要求以學(xué)生自主訓(xùn)練為主的開放模式組織教學(xué)六、實(shí)驗(yàn)條件（1）微機(jī)（2）MATLAB編程工具七、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)預(yù)習(xí)：離散信道容量的定義以及信道容量的迭代計(jì)算方法實(shí)驗(yàn)記錄：通過迭代算法計(jì)算能夠得到的信道容量的結(jié)果實(shí)驗(yàn)報(bào)告輸兀p(ai>?yp.iu$巒ACl輸出d/已*#inelude<iostrea

8、m>usingnamespacestd;#defineFLOAT_MINUS_PRECISION0.00001typedefvector<float*>VEC_PFLOAT;/迭代計(jì)算信道容量，參數(shù)值為信源，信宿符號個(gè)數(shù)和信道轉(zhuǎn)移概率矩陣，返回信道容量</pre>floatGetCapacity(intnSourceSymbol,intnHostSymbol,constVEC_PFLOAT&vTransMatrix)/信道容量初始化為最小值floatfCapacity=FLT_MIN;/信源概率分布float*pfSoureProb=float*pfSou

9、reProb=newfloatnSourceSymbol;/初始化信源分布為均勻分布inti;for(i=0;i<nSourceSymbol;i+)pfSoureProbi=1.0/nSourceSymbol;/初始化0函數(shù)VEC_PFLOATvPhi;for(i=0;i<nSourceSymbol;i+)float*pfTemp=newfloatnHostSymbol;vPhi.push_back(pfTemp);/設(shè)置精度;constfloatcfDelta=0.02f;floatfPrecision;/迭代計(jì)算intj,k;float*pfSum=newfloatnSourc

10、eSymbol;dofor(i=0;i<nSourceSymbol;i+)for(j=0;j<nHostSymbol;j+)/計(jì)算工Pi*PjifloatfSum=0.0f;for(k=0;k<nSourceSymbol;k+)fSum+=pfSoureProbi*vTransMatrixki;vPhiij=pfSoureProbi*vTransMatrixji/fSum;floatfSumDeno=O.Of;/分母求和for(i=0;i<nSourceSymbol;i+)floatfSum=0.0f;for(j=0;j<nHostSymbol;j+)fSum+=

11、vTransMatrixji*logf(vPhiij);pfSumi=expf(fSum);fSumDeno+=pfSumi;for(i=0;i<nSourceSymbol;i+)pfSoureProbi=pfSumi/fSumDeno;/計(jì)算新一輪的容量floatfNewC=logf(fSumDeno);/計(jì)算精度fPrecision=fabs(fNewC-fCapacity)/fCapacity;fCapacity=fNewC;while(fPrecision-cfDelta>0.0f);/釋放臨時(shí)資源deletepfSum;for(i=0;i<vPhi.size();i

12、+)float*pfTemp=vPhi.at(i);deletepfTemp;vPhi.clear();returnfCapacity;intmain()/轉(zhuǎn)移矩陣VEC_PFLOATvTransMatrix;intnCol,nLine;cout<<"請輸入信源符號個(gè)數(shù):"cin>>nLine;cout<<"請輸入信宿符號個(gè)數(shù):"cin>>nCol;</pre></pre>cout<<"請依次輸入"<<<"行信道轉(zhuǎn)移概率矩陣

13、:(以空格隔開每個(gè)概率)n"for(inti=0;i<nLine;i+)float*pfTemp=newfloatnCol;LabelfloatfSum=0.0f;cout<<"X"<<<":"for(intj=0;j<nCol-1;j+)cin>>pfTempj;fSum+=pfTempj;if(1.0f-fSum<0)cout<<"轉(zhuǎn)移概率和應(yīng)該為1,請重新輸入!n"gotoLabell;elsepfTemp|j=1.0f-fSum;cout<

14、<"信源符號X"<<<"的轉(zhuǎn)移概率分別為for(intk=0;k<nCol;k+)cout<cout<vTransMatrix.push_back(pfTemp);cout<<"信道容量為："<</pre>for(intk=0;k<vTransMatrix.size();k+)float*pfTemp=vTransMatrix.at(k);deletepfTemp;vTransMatrix.clear();return0;八、實(shí)驗(yàn)心得:1、由于長時(shí)間未編程了，對編程有

15、點(diǎn)生疏，通過在網(wǎng)上找了一些代碼，通過修改已有代碼來逐步學(xué)習(xí)離散信道容量的迭代計(jì)算.2、3、4、實(shí)驗(yàn)二：Huffman編碼的實(shí)現(xiàn)實(shí)驗(yàn)學(xué)時(shí)：3實(shí)驗(yàn)類型：(演示、驗(yàn)證、綜合、"設(shè)計(jì)、研究)實(shí)驗(yàn)要求：(V必修、選修)一、實(shí)驗(yàn)?zāi)康睦斫夂驼莆説uffman編碼的基本原理和方法，實(shí)現(xiàn)對信源符號的huffman編碼.二、實(shí)驗(yàn)內(nèi)容1. 理解和掌握huffman編碼的基本原理和方法2. 通過MATLAB編程實(shí)現(xiàn)對單信源符號的huffma編碼3. 計(jì)算信源的信息熵、平均碼長以及編碼效率三、實(shí)驗(yàn)原理1. Huffman編碼按信源符號出現(xiàn)的概率而編碼，其平均碼長最短，所以是最優(yōu)碼.2. 無失真信源編碼定理：對

16、于熵為H(X)的離散無記憶的平穩(wěn)信源，必存在一種無失真編碼，使每符號的平均碼長滿足不等式：巴包乞L：巴包1logrlogr3. 二元Huffman編碼：若將編碼設(shè)計(jì)為長度不等的二進(jìn)制編碼，即讓待傳字符串中出現(xiàn)概率大的字符采用盡可能短的碼字，而把長的碼字分配給概率小的信源符號構(gòu)造方法如下：(a) 將信源概率分布按大小以遞減次序排列；合并兩概率最小者，得到新信源；并分配0/1符號新信源若包含兩個(gè)以上符號返回(a)，否則到(c).(b) 從最后一級向前按順序?qū)懗雒啃旁捶査鶎?yīng)的碼字.4. Huffman編碼算法ProcedureHUFFMAN(si,pi)ifq=2thenreturns00,s11else降序排序pi縮減信源:創(chuàng)建一個(gè)符號S'以取代Sq-2,Sq-1，其概率為p'=Pq-2+Pq-1遞歸調(diào)用Huffman算法以得到S0，,Sq-3,s'的編碼:W0，,Wq-3,w'，相應(yīng)的概率分布為P0,