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

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

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

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

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

5、存在的后綴，并加入到b4040中，通過(guò)一個(gè)循環(huán)，找到a4040中所有尾隨后綴；即 for(i=0;iQ;i+) k1=strlen(bi); for(j=0;jn;j+) if(k1Lj;通過(guò)循環(huán)調(diào)用即可找到b4040中的所有尾隨后綴，最后再將他們分別存放在b4040中；即通過(guò) 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ù)中所需要注意的問(wèn)題就是一個(gè)比較的問(wèn)題，也就是實(shí)現(xiàn)6）中所提到的。五測(cè)試結(jié)果5.1、測(cè)試數(shù)據(jù)

6、為0 10 1100 1110 1011 11015.2、測(cè)試數(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(請(qǐng)輸入碼字個(gè)數(shù)：); scanf(%d,&n); printf(請(qǐng)分別輸入碼字: ); 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、描述在這個(gè)信息量爆炸的時(shí)代，凡是能載荷一定信息量，且碼字的平均長(zhǎng)度最短，可分離的變長(zhǎng)碼的碼字集合稱(chēng)為最佳變長(zhǎng)碼。為此，必須將概率大的信息符號(hào)編以短的碼字，概率小的符號(hào)編以長(zhǎng)的碼字，使得平均碼字最短。能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）、費(fèi)諾（Fano）、哈夫曼（Huffman）編碼等。哈夫曼(Huffman)編碼是一種常用的壓縮編碼方法，是Huffman于1952年為壓縮文本文件建立的。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長(zhǎng)的代碼代替，每個(gè)數(shù)據(jù)的代碼各不相同。哈夫曼壓縮是個(gè)無(wú)損的壓縮算法，一般用來(lái)壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長(zhǎng)度算法一族

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

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

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

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

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

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

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

17、上面說(shuō)到Developer Studio沒(méi)有編譯程序的功能，那么這項(xiàng)工作是由誰(shuí)來(lái)完成的呢？是CL，是NMAKE，和其他許許多多命令行程序，這些我們看不到的程序才是構(gòu)成Visual Studio的基石。3.2設(shè)計(jì)內(nèi)容例：對(duì)如下單符號(hào)離散無(wú)記憶信源編三進(jìn)制哈夫曼碼。這里：m=3，n=8令k=3，m+k(m1)=9，則 s=9n=98=1所以第一次取ms=2個(gè)符號(hào)進(jìn)行編碼。由計(jì)算可得：平均碼長(zhǎng)為： （3.1）信息率為：（3.2）編碼效率為：（3.3）可見(jiàn)：哈夫曼的編碼效率相當(dāng)高，對(duì)編碼器的要求也簡(jiǎn)單得多。編碼過(guò)程如下：表1 哈夫曼編碼信源符號(hào)概率縮減信源碼字碼長(zhǎng)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(請(qǐng)輸入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開(kāi)始*/ 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開(kāi)始*/ 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)造哈夫曼樹(shù)子程序*/ 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樹(shù)*/ 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;/*組合樹(shù)根節(jié)點(diǎn)權(quán)重為左右子之和*/ hti.lchild=s1; hti.rchild=s2; /*組合樹(shù)左右子分別為s1,s2*/ hts1.parent=hts2.parent=i; /*新樹(shù)加入數(shù)組*/ int main() int i,j,n; double average_length,sum=0; HTNode htMaxNo; HCode hcdMaxNo; float D100; /*各概率的對(duì)數(shù) */ float H=0.00; float h100; /*存放信息熵*/ float R; /*編碼效率*/cout姓名：時(shí)旭東 學(xué)號(hào)：311

23、008002320endl; cout請(qǐng)輸入信源符號(hào)個(gè)數(shù)：endl; while(scanf(%d,&n) cout請(qǐng)輸入各個(gè)信源符號(hào)及其概率，比如：A 0.12 ：endl; for(i=0;i1) /*避免總概率大于1*/ cout概率大于1，請(qǐng)重新輸入endl; for(i=0;in;i+) Di=3.322*(-log10(hti.weight); hi=hti.weight*Di; /*各信源的熵*/ H=H+hi; CreateHT(ht,n); /*生成哈夫曼樹(shù)*/ 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ì)算該碼的平均碼長(zhǎng)、編碼效率：endl; average_length=0; for(i=0;in;i+) average_length+=hti.weight*(n-hcdi.start+1); /*計(jì)算該信源的平均碼長(zhǎng)*/ cout平均編碼長(zhǎng)度: K=average_lengthendl; R=H/average_length; /*編碼效率*/ cout編碼效率: R=Rendl; return

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