信息電子學院實驗指導(dǎo)書格式信息論

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

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

3、的，因而信道的傳遞概率決定了信道的信道容量給定了信道的傳遞概率，可以通過推導(dǎo)方法求得信道的信道容量，一般可以求出傳遞效率達到信道容量時候的輸入信號的分布，但是這種方法不方便計算機實現(xiàn)4迭代法，便于計算機實現(xiàn)：迭代法分成三個模塊，一個迭代計算反向?qū)嶒炐诺繮(x|y)，另一個迭代計算p(x)，第三個檢查一次迭代前后信道容量誤差的變化是否小于檢測值(可取0.0001),如果小于檢測值則停止計算，輸出結(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信道容量的迭代計算具體如下：求信道容量C就是在Pi的約束下，求l(X;Y)的極大值.為計算方便，重寫下l(X;Y)式，公式中的對數(shù)取自然數(shù).PjI(X,Y)八'PiPjlnijEPiPji首先引入反條件概率，即(1)Pxiy(a|bj)=qji(2l(X,Y)八'PiPjlnqijPi(3)迭代算法的要點是，當信道固定(即口固定)時，把l(X;Y)看成是Pi和qji的函數(shù)，用公式(3)進行信道容量計算的迭代每一次迭代有兩步組成：(a)將P(n)固定，在約束qji=1的條件下變動qji，得

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

6、(X;Y)小于門限值時，就結(jié)束迭代過程，此時I(X;Y)的值就是信道容量C.可以采用下述方法，避免計算反向條件概率，使算法簡化：將（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,且&為一個小的正數(shù).且初始概率分布為均勻分布，即設(shè)pi=1/r計算qjPiPij;'二Pijln(Pj/qj)計算

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

8、m>usingnamespacestd;#defineFLOAT_MINUS_PRECISION0.00001typedefvector<float*>VEC_PFLOAT;/迭代計算信道容量，參數(shù)值為信源，信宿符號個數(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;/迭代計算intj,k;float*pfSum=newfloatnSourc

10、eSymbol;dofor(i=0;i<nSourceSymbol;i+)for(j=0;j<nHostSymbol;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;/計算新一輪的容量floatfNewC=logf(fSumDeno);/計算精度fPrecision=fabs(fNewC-fCapacity)/fCapacity;fCapacity=fNewC;while(fPrecision-cfDelta>0.0f);/釋放臨時資源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<<"請輸入信源符號個數(shù):"cin>>nLine;cout<<"請輸入信宿符號個數(shù):"cin>>nCol;</pre></pre>cout<<"請依次輸入"<<<"行信道轉(zhuǎn)移概率矩陣

13、:(以空格隔開每個概率)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;八、實驗心得:1、由于長時間未編程了，對編程有

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

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