信息論與編碼課程設(shè)計報告書

1、信息論與編碼課程設(shè)計報告設(shè)計題目：統(tǒng)計信源熵、香農(nóng)編碼與費諾編碼專業(yè)班級：XXXXXXXXXXXX姓名:XXXXXXXXXXXX學(xué)號:XXXXXXXXXXXX指導(dǎo)老師：XXXXXXXXXXXX成 績:時間：2015年3月31日目錄一、設(shè)計任務(wù)與要求 2二、設(shè)計思路 2三、設(shè)計流程圖 5四、程序及結(jié)果 7五、心得體會 11六、參考文獻 12附錄 13設(shè)計任務(wù)與要求1. 統(tǒng)計信源熵 要求：統(tǒng)計任意文本文件中各字符(不區(qū)分大小寫)數(shù)量，計算 字符概率，并計算信源熵。2. 香農(nóng)編碼 要求：任意輸入消息概率，利用香農(nóng)編碼方法進行編碼，并計算 信源熵和編碼效率。3. 費諾編碼 要求：任意輸入消息概率，利用

2、費諾編碼方法進行編碼，并計算 信源熵和編碼效率。二、設(shè)計思路1、統(tǒng)計信源熵：統(tǒng)計信源熵就是對一篇英文文章中的 i 種字符(包括標點符號及空格，英文字母不區(qū)分大小寫)統(tǒng)計其出現(xiàn)的次數(shù)coun(t )i ，然后計算其出現(xiàn)的概率p(i)，最后由信源熵計算公式：nH(x)p(xi)log p(xi)n1算出信源熵 H (x) 。所以整體步驟就是先統(tǒng)計出文章中總的字符 數(shù)，然后統(tǒng)計每種字符的數(shù)目， 直到算出所有種類的字符的個數(shù)， 進而算出每種字符的概率，再由信源熵計算公式計算出信源熵。 在這里我選擇用 Matlab 來計算信源熵， 因為 Matlab 中系統(tǒng)自帶 了許多文件操作和字符串操作函數(shù)， 其計算

3、功能強大， 所以計算 信源熵很是簡單。2、香農(nóng)編碼信源編碼模型:信源編碼就是從信源符號到碼符號的一種映射f，它把信源輸出的符號ai變換成碼元序列人f: aixi,i 1,2,.,qNS: s ai,., aq 信源信源編碼器AXi以1必2.入 碼元Sai ,., aqi 1,2,.,NX : x Xi,.,Xr碼符號N次擴展信源無失真編碼器凡是能載荷一定的信息量， 且碼字的平均長度最短，可分離 的變長碼的碼字集合都可以稱為最佳碼。為此必須將概率大的信 息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字長度最短。能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）、費諾（Fa no）、哈

4、夫曼（Huffman ）編碼等。香農(nóng)第一定理：離散無記憶信源為S SS2 SqP P（s）P（S2）.P（Sq）熵H（S）,其N次擴展為snP1 2P( 1) P( 2)qP( q)熵為H(SN),碼符號集為X (Xi,X2,.,Xr)。先對信源SN進行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使S中每個信源符號所需的平均碼長滿足H(S) 1 Ln log r N NH(S) log r且當N時有l(wèi)Nm N第Hr(S)qNL是平均碼長Lp( i) i，i 1i是i對應(yīng)的碼字長度香農(nóng)編碼方法：(1)將信源消息符號按其出現(xiàn)的概率大小依次排列：PlP2Pn(2) 確定滿足下列不等式整數(shù)碼長Ki為

5、lb(Pi) Kilb(Pi) 1(3) 為了編成唯一可譯碼，計算第i個消息的累加概率為i 1PP(aQk 1(4) 將累加概率P變成二進制數(shù)。(5) 取R二進制數(shù)小數(shù)點后Ki位即為該消息符號的二進制碼字3、費諾編碼方法(1)將信源消息符號按其出現(xiàn)的概率大小依次排列:P1P2 .Pn(2) 將依次排列的信源符號按概率值分為兩大組，使兩個組的 概率之和近似相同，并對各組賦予一個二進制碼元 “0”和“ 1(3) 將每一大組的信源符號再分為兩組，使劃分后的兩個組的概率之和近似相同，并對各組賦予一個二進制符號 “0”和“ 1(4) 如此重復(fù)，直至每個組只剩下一個信源符號為止。(5) 信源符號所對應(yīng)的碼

6、字即為費諾碼。三、設(shè)計流程圖1、統(tǒng)計信源熵 由信源熵計算公式H(x) P(xjlog p(xj計算出信源熵 n 12、香農(nóng)編碼開始輸入概率矩陣將概率由大到小排列計算累加概率和概率的個數(shù)根據(jù)公式調(diào)用函數(shù)計算碼長用循環(huán)程序編碼并調(diào)整輸出格式計算信源熵和編碼效率輸出信源熵、編碼效率和碼字（ 結(jié)束 ）3、費諾編碼開始輸入概率矩陣將概率由大到小排列計算累加概率和概率的個數(shù)在兩組概率之和近似相等的條件下將概率分為兩組，各賦予0，1兩個碼元將每一大組的的概率重復(fù)上一步操作，直到每組只剩一個概率用循環(huán)程序編碼并調(diào)整輸出格式*計算信源熵和編碼效率輸出信源熵、編碼效率和碼字/(結(jié)束J四、程序及結(jié)果1、統(tǒng)計信源熵的

7、Matlab程序fun cti onh=e ntropy(p)clcfid=fopen( shuju.txt ，廣);%打開 txt 文件ex,num=fscanf(fid,%c ,inf)滋取二進制文件的數(shù)據(jù)，并將數(shù)據(jù)存入矩陣str1=lower(ex)%各字符串中的大寫字母轉(zhuǎn)換成小寫字母sort_str1=sort(str1); %按照字符的ASCII值對字符串排序j=1;for i=1:length(sort_str1)-1%計算岀字符串的種類if strcmp(sort_str1(i),sort_str1(i+1)=1%比較兩個字符串是否完全相等，相等是1,否則0j=j+1；str2(

8、j)=sort_str1(i);endstr2(j+1)=sort_str1(i+1);endfor i = 1:length(str2)%length函數(shù)獲取字符串長度str_num=strfind(sort_str1,str2(i);%strfind(S1,S2):尋找 S2 是否匹配 S1,并返回 S2的位置cou nt1(i) = len gth(str_ num);endstr2cou nt=cou nt1(3:e nd)p=cou nt./sum(cou nt)sum(-p.*log2(p)冊算信源熵待讀取的英文：The Pressure of Graduate StudentsN

9、ow I am a post graduate student, I will graduate next year, so I start to find jobs recently, I feel so much pressure, though I have good education, I still get rejection from the companies. The pressure of graduate students are so heavy, the competition is so fierce that many students cant get the

10、ideal jobs. They should adjust theirstrategies.The pressure of graduate students is so heavy. On the one hand, they don t have experience, so they don t know how to get the job interview and miss many chances. On the other hand, there are more and more students have high education, some have receive

11、d higher education, some have studies abroad which make their resumes stand out. Those average students don t have advantages over the above mentioned ones.Average students need to make their resumes specially, so they can have the chance. They can describe their characteristic to fit the job, the e

12、mployers will see this and give you the chance. Students can also make their internship experience stand out, because the employers pay special attention to it.The job pressure is heavy for every graduate student, if the students take the wise strategy, they can have more chances to get the job.程序運行

13、結(jié)果： 總共出現(xiàn)的字符種類： ,.abcdefghijklmnoprstuvwxy 每種字符對應(yīng)出現(xiàn)的次數(shù)： 206 16 11 78 10 33 42 161 10 20 65 5385162158 64 1655 80 113 36 2083204每種字符出現(xiàn)的概率： 0.1672 0.0130 0.0089 0.0633 0.00810.02680.03410.13070.00810.01620.05280.04300.00650.00410.01300.01700.04710.05190.01300.04460.06490.09170.02920.01620.00650.00240.0

14、1620.0032信源熵：Hx4.12502、香農(nóng)編碼程序function c=shannon(p)% p=0.25 0.25 0.20 0.15 0.10 0.05;% shannon(p);p,index=sort(p);p=fliplr(p);%從大到小n=length(p);pa=0; %累加概率for i=2:npa(i)=pa(i-1)+p(i-1);endk=ceil(-log2(p);%碼長計算c=cell(1,n); %生成元胞數(shù)組，存碼字，是 for i=1:nci= ;tmp=pa(i);for j=1:k(i)tmp=tmp * 2;if tmp=1tmp=tmp -

15、1;ci(j)=1 ;elseci(j)=0 ;endendend%p%pa%交換回原來的順序 c=fliplr(c);c(index)=c;fprintf( 信源信息熵 :n );H=sum(-p.*log2(p) %計算信源熵 fprintf( 平均碼長 :n );K=sum(p.*k) %計算平均碼長 fprintf( 編碼效率 :n ); w=H./K %計算編碼效率 fprintf( 碼字 :n );c程序運行結(jié)果：p=0.25 0.25 0.20 0.15 0.10 0.05; shannon(p);信源信息熵 :cell ，跟上一行不一樣11110H = 2.4232 平均碼長

16、: K = 2.7000 編碼效率 : w = 0.8975 碼字: c = 01 00 100 101 11013、費諾編碼程序主程序function c=fano1(p)% p=0.25 0.25 0.20 0.15 0.10 0.05% c=fano1(p) n=size(p,2);if n=1c=cell(1,1);c1= ;returnendp,index=sort(p);%按概率排序p=fliplr(p);total=sum(p); %總概率 acc=0; %累積概率 flag=0; %是否到達尾部的標志 for i=1:n-1newacc=acc+p(i);if abs(tota

17、l-2 * newacc)=abs(total - 2*acc) flag=1;break ; end acc=newacc;end if flagi=n;endsplit=i; %從分界點對兩邊的碼遞歸做fanoc1=fano1(p(1:split-1);c2=fano1(p(split:n);c=cell(1,n); %添加前綴 0， 1 for i=1:split-1ci=strcat( 0 ,c1i);endfor i = split:nci=strcat( 1 ,c2i-split+1 ); end %將順序調(diào)整回去 c=fliplr(c);c(index)=c;子程序functio

18、n =fano2(c,p)for i=1:length(c) %求平均碼長count(i)=length(cell2mat(c(i);endfprintf( 信源信息熵 :n );H=sum(-p.*log2(p) %計算信源熵fprintf( 平均碼長 :n )K=sum(count.*p) %計算平均碼長fprintf( 編碼效率 :n )w=H./K%計算編碼效率fprintf( 碼字 :n)c程序運行結(jié)果：p=0.25 0.25 0.20 0.15 0.10 0.05c=fano1(p)fano2(c,p)p = 0.2500 0.2500 0.2000 0.1500 0.1000 0

19、.0500c = 00 01 10 110 1110 1111信源信息熵 :H = 2.4232平均碼長 :K = 2.4500編碼效率 :w = 0.9891碼字:c = 00 01 10 110 1110 1111五、心得體會 做這次課程設(shè)計前前后后花了三天時間，之前并沒有用心 想，只是看了看網(wǎng)上的資料，看人家都是用什么方法解決的。我 看的有用C (包括C+和C#)語言的，有用 Matlab的，還有用 別的什么軟件的。由于我對 Matlab 編程還比較熟悉一點，最后 我還是選擇用 Matlab 來做。一開始編程，我甚至連一些常用的 Matlab 函數(shù)都忘了，沒什么想法后我在網(wǎng)上看了一些人用

20、 Matlab 編的程序，拿來仔細研究后也慢慢著編出了自己的程序。 在編程過程中， 遇到了各種問題問題， 有時由于一個小問題不通， 我要反復(fù)琢磨半天， 最后發(fā)現(xiàn)是在一個小地方上出錯了， 真是備 受煎熬， 但這也是編程的樂趣所在， 在這個過程中自己也學(xué)到了 許多編程知識和技巧。在編程過程中，我體會到了 Matlab 功能的強大，我需要好 好學(xué)習一下，這對我以后在信號處理與仿真計算上有很大幫助。通過這次課程設(shè)計， 我對信息論與編碼技術(shù)中的一些基礎(chǔ)知 識，如信源熵、通信系統(tǒng)模型、信道與信源編碼等知識又重新學(xué) 習了一下， 感覺雖是學(xué)過的知識， 但隔一段時間不看合上書自己 竟然什么也想不起來。 學(xué)過的知

21、識， 覺得自己早就已經(jīng)理解了的， 在實際用來解決問題時又是無從下手， 需多看人家的例子， 在此 基礎(chǔ)上才能用來解決自己的問題。 我之所以自己一組， 是想真學(xué) 到點東西，這過程中很累人， 但這是因為自己當初沒有提早準備， 還有就是自己知識也學(xué)的不扎實造成的， 于是感悟到做什么事情 都要有計劃地提早準備，不然會坐失良機，最后只能悔不當初。 六、 參考文獻1 曹雪虹，宗橙 . 信息論與編碼(第二版) . 北京：清華大學(xué)， 2009.22 王薇,鑫鋒.從零開始學(xué) MATLAB .北京： 電子工業(yè)，2012.9附錄1、統(tǒng)計信源熵的 Matlab 程序function h=entropy(p)clcfid

22、=fopen( shuju.txt , r ); %打開 txt 文件ex,num=fscanf(fid, %c ,inf) %讀取二進制文件的數(shù)據(jù)，并將數(shù)據(jù)存入矩陣 str1=lower(ex)%將字符串中的大寫字母轉(zhuǎn)換成小寫字母sort_str1=sort(str1);%按照字符的 ASCII 值對字符串排序j=1;for i=1:length(sort_str1)-1%計算出字符串的種類if strcmp(sort_str1(i),sort_str1(i+1)=1%比較兩個字符串是否完全相等，相等是1，否則 0j=j+1;str2(j)=sort_str1(i);endstr2(j+1)

23、=sort_str1(i+1);endfor i = 1:length(str2) %length 函數(shù)獲取字符串長度str_num=strfind(sort_str1,str2(i);%strfind(S1,S2):尋找 S2 是否匹配 S1,并返回 S2的位置count1(i) = length(str_num);endstr2count=count1(3:end)p=count./sum(count)sum(-p.*log2(p)%計算信源熵2、香農(nóng)編碼程序function c=shannon(p)% p=0.25 0.25 0.20 0.15 0.10 0.05;% shannon(p

24、);p,index=sort(p);p=fliplr(p);%從大到小n=length(p);pa=0; %累加概率for i=2:npa(i)=pa(i-1)+p(i-1);endk=ceil(-log2(p);%碼長計算c=cell(1,n);%生成元胞數(shù)組，存碼字，是cell ，跟上一行不一樣for i=1:nci= ;tmp=pa(i);for j=1:k(i)tmp=tmp * 2;if tmp=1tmp=tmp - 1;ci(j)=1 ;else ci(j)= 0 ;endendend %p %pa %交換回原來的順序 c=fliplr(c);c(index)=c; fprintf( 信源信息熵 :n ); H=sum(-p.*log2(p) %計算信源熵 fprintf( 平均碼長 :n );K=sum(p.*k) %計算平均碼長 fprintf( 編碼效率 :n );