信息論與編碼課程設(shè)計(jì)報1

1、信息論與編碼課程設(shè)計(jì)報告姓名：時旭東專業(yè):電科10-01學(xué)號：311008002320指導(dǎo)老師：成凌飛完成日期：2013.03.20目錄一課程描術(shù)。1二設(shè)計(jì)原理。2三設(shè)計(jì)內(nèi)容。3四總結(jié)。22五參考文獻(xiàn)。23一課程設(shè)計(jì)教學(xué)目的通過本次課程設(shè)計(jì)的練習(xí)，使學(xué)生進(jìn)一步鞏固信源熵、信源編碼的基本原理，掌握具體的編碼方法，熟悉編程軟件的使用，培養(yǎng)學(xué)生自主設(shè)計(jì)、編程調(diào)試的開發(fā)能力，同時提高學(xué)生的實(shí)踐創(chuàng)新能力。二題目一：判斷唯一可譯碼一設(shè)計(jì)要求：利用尾隨后綴法判斷任意輸入的碼是否為唯一可譯碼。二題目分析： 設(shè)計(jì)一個程序?qū)崿F(xiàn)判斷輸入碼組是否為唯一可譯碼這一功能。在我們學(xué)習(xí)使用了克勞夫特不等式之后，知道唯一可譯碼

2、必須滿足克勞夫特不等式。但是克勞夫特不等式僅僅是存在性的判定定理，即該定理不能作為判斷一種碼是否為唯一可譯碼的依據(jù)。也就是說當(dāng)碼字長度和碼符號數(shù)滿足克勞夫特不等式時，則必可以構(gòu)造出唯一可譯碼，否則不能構(gòu)造出唯一可譯碼。因此我們必須找到一種能夠判斷一種碼是否為唯一可譯碼的方法尾隨后綴法。三算法分析：尾隨后綴法算法描述： 設(shè)C為碼字集合，按以下步驟構(gòu)造此碼的尾隨后綴集合F： (1) 考查C中所有的碼字，若Wi是Wj的前綴，則將相應(yīng)的后綴作為一個尾隨后綴放入集合F0中； (2) 考查C和Fi兩個集合，若WjC是WiFi的前綴或WiFi 是WjC的前綴，則將相應(yīng)的后綴作為尾隨后綴碼放入集合Fi+1中；

3、 (3)F=Fi即為碼C的尾隨后綴集合； (4) 若F中出現(xiàn)了C中的元素，則算法終止，返回假(C不是唯一可譯碼)；否則若F中沒有出現(xiàn)新的元素，則返回真。在我們設(shè)計(jì)的算法中，需要注意的是我們需要的是先輸出所有尾隨后綴的集合，然后再判斷該碼是否是唯一可譯碼，即如F中出現(xiàn)了C中的元素，則C不是唯一可譯碼，否則若F中沒有出現(xiàn)新的元素，則C為唯一可譯碼。而不是F中出現(xiàn)C中的元素就終止，這也是在本題的要求中需要注意的問題。簡明流程圖開始輸入碼字個數(shù)和碼字進(jìn)行尾隨后綴編碼判斷是否為唯一碼調(diào)用main（）函數(shù)結(jié)束四概要設(shè)計(jì)：由于需要判斷尾隨后綴，所以我們需要反復(fù)的比較C和F中的碼字。1） 首先我們用一個b40

4、40的數(shù)組來存放所有的尾隨后綴的集合；用Q記錄所有尾隨后綴的個數(shù)；2） 用數(shù)組a4040來存放輸入的碼字，L50來存放碼字的長度；通過一個雙重循環(huán)并調(diào)用Hz（ai,aj,Li,Lj）函數(shù)來找到a4040中的為隨后綴，即：for(i=0;in-1;i+) for(j=0;jn;j+) if(i!=j&LiLj) Hz(ai,aj,Li,Lj); 3） 通過判斷Q是否大于0，如果不大于0，即b4040中沒有碼字，也就是不存在尾隨后綴，那么可判斷a4040是唯一可譯碼，否則進(jìn)行如下操作；4） 計(jì)算b4040中尾隨后綴的長度，用k1表示；并調(diào)用Hz(bi,aj,k1,Lj)其中k1Lj來a4040中所

5、存在的后綴，并加入到b4040中，通過一個循環(huán)，找到a4040中所有尾隨后綴；即 for(i=0;iQ;i+) k1=strlen(bi); for(j=0;jn;j+) if(k1Lj;通過循環(huán)調(diào)用即可找到b4040中的所有尾隨后綴，最后再將他們分別存放在b4040中；即通過 for(i=0;in;i+) for(j=0;jLi) Hz(ai,bj,Li,k2); 6） 在反復(fù)調(diào)用Hz(ai,aj,Li,Lj)函數(shù)中如果b4040中有重復(fù)出現(xiàn)的，即尾隨后綴相同的不用再次放入b4040中。7） 在調(diào)用函數(shù)中所需要注意的問題就是一個比較的問題，也就是實(shí)現(xiàn)6）中所提到的。五測試結(jié)果5.1、測試數(shù)據(jù)

6、為0 10 1100 1110 1011 11015.2、測試數(shù)據(jù)為110 11 100 00 10五、源代碼#include#includechar b4040;int Q;void Hz(char c,char d,int L1,int L2) int i,j,temp=0; char m50; for(i=0;iL1;i+) if(ci=di)continue;else break; if(i=L1) for(j=0;jL2-L1;j+) mj=dL1+j; mj=0; for(i=0;iQ;i+) if(strcmp(bi,m)=0) temp=1; break; if(temp!=1

7、) strcpy(bQ,m);Q+; void main()int i,j,k,k1,k2,n;char a4040; int L50; int temp=1;int f=0;printf(請輸入碼字個數(shù)：); scanf(%d,&n); printf(請分別輸入碼字: ); for(i=0;in;i+) scanf(%s,&ai); Li=strlen(ai); for(i=0;in-1;i+) for(j=0;jn;j+) if(i!=j&Li0) for(i=0;iQ;i+) k1=strlen(bi); for(j=0;jn;j+) if(k1Lj) Hz(bi,aj,k1,Lj);

8、for(k=0;kn;k+) for(j=0;jLk) Hz(ak,bj,Lk,k2); printf(尾隨后綴集合為:); for(i=0;iQ;i+) printf(%s ,bi); for(i=0;in&temp!=0;i+) for(j=0;jQ;j+) if(strcmp(ai,bj)=0) temp=0; break; else continue; printf(n); if(temp=0)printf(該碼不是唯一可譯碼!n); else printf(該碼是唯一可譯碼!n); else printf(該碼組是唯一可譯碼!); f+; printf(n);題目二：哈夫曼編碼1課題

9、描述在這個信息量爆炸的時代，凡是能載荷一定信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱為最佳變長碼。為此，必須將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字最短。能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）、費(fèi)諾（Fano）、哈夫曼（Huffman）編碼等。哈夫曼(Huffman)編碼是一種常用的壓縮編碼方法，是Huffman于1952年為壓縮文本文件建立的。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長的代碼代替，每個數(shù)據(jù)的代碼各不相同。哈夫曼壓縮是個無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族

10、。意思是個體符號用一個特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。哈夫曼編碼是哈夫曼樹的一個應(yīng)用，是一種最優(yōu)的前綴技術(shù)，然而其存在的不足卻制約了它的直接應(yīng)用。首先，其解碼時間為O(lavg)，其中l(wèi)avg為碼字的平均長度；其次，更為重要的是，解碼器需要知道哈夫曼編碼樹的結(jié)構(gòu)，因而編碼器必須為解碼器保存或傳輸哈夫曼編碼樹。對于小量數(shù)據(jù)的壓縮而言，這是很大的開銷。因而，應(yīng)用哈夫曼編碼的關(guān)鍵是如何降低哈夫曼編碼樹的存儲空間。目前流行的很多壓縮方法都是用了該技術(shù)，如GZIB、ZLIB、PNC等。2設(shè)計(jì)原理對于多進(jìn)制哈夫曼編碼，為了提高編

11、碼效率，就要是長碼的符號數(shù)量盡量少、概率盡量小，所以信源符號數(shù)量最好滿足n=(m-1)*k+r,其中m為進(jìn)制數(shù)，k為縮減的次數(shù)。設(shè)計(jì)步驟如下：1將信源符號按概率從大到小的順序排列，令p(x1) p(x2) p(xn)2給兩個概率最小的信源符號p(xn-1)和p(xn)各分配一個碼位“0”和“1”，將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，或者在新添加一個信源符號，令其概率為0，則個分配一個碼位“0”、“1”和“2”，將其合并，結(jié)果得到一個只包含(n1)個信源符號的新信源。稱為信源的第一次縮減信源，用S1表示。3將縮減信源S1的符號仍按概率從大到小順序排列，此后

12、每次合并3個信源符號，得到只含(n3)個符號的縮減信源S2。4重復(fù)上述步驟，直至最后，此時所剩符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。3 設(shè)計(jì)過程3.1軟件介紹3.1.1 Visual C+ 6.0簡介Visual C+ 6.0，簡稱VC或者VC6.0，是微軟推出的一款C+編譯器，將“高級語言”翻譯為“機(jī)器語言（低級語言）”的程序。Visual C+是一個功能強(qiáng)大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出Visual C+1.0后，隨著其新版本的不斷問世，Visual C+已成為專業(yè)程序員進(jìn)行軟件開發(fā)的首選工具。Vi

13、sual C+6.0由Microsoft開發(fā), 它不僅是一個C+ 編譯器，而且是一個基于Windows操作系統(tǒng)的可視化集成開發(fā)環(huán)境（integrated development environment，IDE）。Visual C+6.0由許多組件組成，包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lass Wizard等開發(fā)工具。 這些組件通過一個名為Developer Studio的組件集成為和諧的開發(fā)環(huán)境。Microsoft的主力軟件產(chǎn)品。Visual C+是一個功能強(qiáng)大的可視化軟件開發(fā)工具。Visual C+6.0以擁有“語法高亮”，自動編譯功能以及高級除錯功能而著稱。比如，

14、它允許用戶進(jìn)行遠(yuǎn)程調(diào)試，單步執(zhí)行等。還有允許用戶在調(diào)試期間重新編譯被修改的代碼，而不必重新啟動正在調(diào)試的程序。其編譯及創(chuàng)建預(yù)編譯頭文件(stdafx.h)、最小重建功能及累加連結(jié)(link)著稱。這些特征明顯縮短程序編輯、編譯及連結(jié)的時間花費(fèi)，在大型軟件計(jì)劃上尤其顯著。3.1.2主要部分1Developer Studio 圖1 Developer Studio環(huán)境這是一個集成開發(fā)環(huán)境，我們?nèi)粘９ぷ鞯?9%都是在它上面完成的，再加上它的標(biāo)題赫然寫著“Microsoft Visual C+”，所以很多人理所當(dāng)然的認(rèn)為，那就是Visual C+了。其實(shí)不然，雖然Developer Studio提供了

15、一個很好的編輯器和很多Wizard，但實(shí)際上它沒有任何編譯和鏈接程序的功能，真正完成這些工作的幕后英雄后面會介紹。我們也知道，Developer Studio并不是專門用于VC的，它也同樣用于VB，VJ，VID等Visual Studio家族的其他同胞兄弟。所以不要把Developer Studio當(dāng)成Visual C+， 它充其量只是Visual C+的一個殼子而已。這一點(diǎn)請切記！ 2MFC從理論上來講，MFC也不是專用于Visual C+，Borland C+，C+Builder和Symantec C+同樣可以處理MFC。同時，用Visual C+編寫代碼也并不意味著一定要用MFC，只要愿

16、意，用Visual C+來編寫SDK程序，或者使用STL，ATL，一樣沒有限制。不過，Visual C+本來就是為MFC打造的，Visual C+中的許多特征和語言擴(kuò)展也是為MFC而設(shè)計(jì)的，所以用Visual C+而不用MFC就等于拋棄了Visual C+中很大的一部分功能。但是，Visual C+也不等于MFC。 3Platform SDK這才是Visual C+和整個Visual Studio的精華和靈魂，雖然我們很少能直接接觸到它。大致說來，Platform SDK是以Microsoft C/C+編譯器為核心（不是Visual C+，看清楚了），配合MASM，輔以其他一些工具和文檔資料。

17、上面說到Developer Studio沒有編譯程序的功能，那么這項(xiàng)工作是由誰來完成的呢？是CL，是NMAKE，和其他許許多多命令行程序，這些我們看不到的程序才是構(gòu)成Visual Studio的基石。3.2設(shè)計(jì)內(nèi)容例：對如下單符號離散無記憶信源編三進(jìn)制哈夫曼碼。這里：m=3，n=8令k=3，m+k(m1)=9，則 s=9n=98=1所以第一次取ms=2個符號進(jìn)行編碼。由計(jì)算可得：平均碼長為： （3.1）信息率為：（3.2）編碼效率為：（3.3）可見：哈夫曼的編碼效率相當(dāng)高，對編碼器的要求也簡單得多。編碼過程如下：表1 哈夫曼編碼信源符號概率縮減信源碼字碼長0.40.090100.2220121

18、0 1.012010.181020.11120.11220.072120.062220.0520030.042013001212102圖2 哈夫曼編碼4編碼程序及其分析/*哈夫曼編碼*#include stdio.h #includeiostream.h #include math.h #define MaxNo 100 typedef char ElemType; typedef struct ElemType dataMaxNo; double weight; /*信源概率*/ int parent,lchild,rchild; /*父親和左右孩子節(jié)點(diǎn)*/ HTNode; typedef

19、struct char cdMaxNo; /*存放編碼用*/ int start; HCode; void CreateHCode(HTNode ht,HCode hcd,int n) /*哈夫曼編碼子程序*/ int i,f,c; int choose; HCode hc;printf(請輸入0或1進(jìn)行編碼方式選擇：); /*方式選擇*/ scanf(%d,&choose); for(i=0;in;i+) hc.start=n;c=i; f=hti.parent; if(choose=0) /*若選擇0，則哈夫曼編碼以先標(biāo)0開始*/ while(f!=-1) if(htf.lchild=c)

20、 hc.cdhc.start-=0; else hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; hcdi=hc; else /*反之以先標(biāo)1開始*/ while(f!=-1) if(htf.lchild=c) hc.cdhc.start-=1; else hc.cdhc.start-=0; c=f;f=htf.parent; hc.start+; hcdi=hc; void CreateHT(HTNode ht,int n) /*構(gòu)造哈夫曼樹子程序*/ int i,j,k; int s1,s2; /*節(jié)點(diǎn)*/ double min1,min2; f

21、or(i=0;i2*n-1;i+) /*進(jìn)行2*n-1次合并*/ hti.parent=hti.lchild=hti.rchild=-1; for(i=n;i2*n-1;i+) min1=min2=32767; s1=s2=-1; for(k=0;k=i-1;k+) /*不斷循環(huán)組合最終生成Huffman樹*/ if(htk.parent=-1) if(htk.weightmin1) min2=min1; s2=s1; min1=htk.weight; s1=k; else if(htk.weightmin2) min2=htk.weight; s2=k; hti.weight=hts1.we

22、ight+hts2.weight;/*組合樹根節(jié)點(diǎn)權(quán)重為左右子之和*/ hti.lchild=s1; hti.rchild=s2; /*組合樹左右子分別為s1,s2*/ hts1.parent=hts2.parent=i; /*新樹加入數(shù)組*/ int main() int i,j,n; double average_length,sum=0; HTNode htMaxNo; HCode hcdMaxNo; float D100; /*各概率的對數(shù) */ float H=0.00; float h100; /*存放信息熵*/ float R; /*編碼效率*/cout姓名：時旭東 學(xué)號：311

23、008002320endl; cout請輸入信源符號個數(shù)：endl; while(scanf(%d,&n) cout請輸入各個信源符號及其概率，比如：A 0.12 ：endl; for(i=0;i1) /*避免總概率大于1*/ cout概率大于1，請重新輸入endl; for(i=0;in;i+) Di=3.322*(-log10(hti.weight); hi=hti.weight*Di; /*各信源的熵*/ H=H+hi; CreateHT(ht,n); /*生成哈夫曼樹*/ CreateHCode(ht,hcd,n); /*生成哈夫曼編碼*/ cout哈夫曼編碼如下：endl; for(

24、i=0;in;i+) printf(%s: ,hti.data); for(j=hcdi.start;j=n;j+) printf(%c,hcdi.cdj); printf(n); cout下面將計(jì)算該碼的平均碼長、編碼效率：endl; average_length=0; for(i=0;in;i+) average_length+=hti.weight*(n-hcdi.start+1); /*計(jì)算該信源的平均碼長*/ cout平均編碼長度: K=average_lengthendl; R=H/average_length; /*編碼效率*/ cout編碼效率: R=Rendl; return

25、 0; 2 截圖圖3 程序運(yùn)行結(jié)果總 結(jié)在這次課程設(shè)計(jì)中，通過對程序的編寫，調(diào)試和運(yùn)行，使我更好的掌握了Huffman樹等數(shù)據(jù)結(jié)構(gòu)方面的基本知識和各類基本程序問題的解決方法，熟悉了各種調(diào)用的數(shù)據(jù)類型，在調(diào)試和運(yùn)行過程中，加深我對程序運(yùn)行的環(huán)境了解和熟悉的程度，同時也提高了我對程序調(diào)試分析的能力和對錯誤糾正的能力。這次信息論與編碼的程序設(shè)計(jì)，對于我來說是一個挑戰(zhàn)。我對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)在程序的設(shè)計(jì)中也有所體現(xiàn)。課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識，發(fā)現(xiàn)問題、提出問題、分析問題和解決問題的過程，鍛煉學(xué)生的邏輯思維能力和實(shí)踐能力，是對學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過程。在整個課程程序中，我們充分應(yīng)用和調(diào)用各個程序模塊，從而部分實(shí)現(xiàn)了此次程序設(shè)計(jì)的所應(yīng)該有的功能。就是我在課程設(shè)計(jì)是比較成功的方面，而在這個過程中，讓我感覺收獲最大的就是我們都能利用這次課程設(shè)計(jì)學(xué)到很多我們在課本上沒有的知識，充分的發(fā)揮了我們的主動性，使我們學(xué)會了自主學(xué)習(xí)，和獨(dú)立解決問題的能力。很多程序在結(jié)構(gòu)上是獨(dú)立的，但是本此設(shè)計(jì)的程序功能不是零散的，它有一個連接是的程序是一個整體，達(dá)到這種統(tǒng)一