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

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

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

3、功能強(qiáng)大， 所以計(jì)算 信源熵很是簡單。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次擴(kuò)展信源無失真編碼器凡是能載荷一定的信息量， 且碼字的平均長度最短，可分離 的變長碼的碼字集合都可以稱為最佳碼。為此必須將概率大的信 息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字長度最短。能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）、費(fèi)諾（Fa no）、哈

4、夫曼（Huffman ）編碼等。香農(nóng)第一定理：離散無記憶信源為S SS2 SqP P（s）P（S2）.P（Sq）熵H（S）,其N次擴(kuò)展為snP1 2P( 1) P( 2)qP( q)熵為H(SN),碼符號集為X (Xi,X2,.,Xr)。先對信源SN進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使S中每個(gè)信源符號所需的平均碼長滿足H(S) 1 Ln log r N NH(S) log r且當(dāng)N時(shí)有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) 為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率為i 1PP(aQk 1(4) 將累加概率P變成二進(jìn)制數(shù)。(5) 取R二進(jìn)制數(shù)小數(shù)點(diǎn)后Ki位即為該消息符號的二進(jìn)制碼字3、費(fèi)諾編碼方法(1)將信源消息符號按其出現(xiàn)的概率大小依次排列:P1P2 .Pn(2) 將依次排列的信源符號按概率值分為兩大組，使兩個(gè)組的 概率之和近似相同，并對各組賦予一個(gè)二進(jìn)制碼元 “0”和“ 1(3) 將每一大組的信源符號再分為兩組，使劃分后的兩個(gè)組的概率之和近似相同，并對各組賦予一個(gè)二進(jìn)制符號 “0”和“ 1(4) 如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號為止。(5) 信源符號所對應(yīng)的碼

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

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

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);%碼長計(jì)算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) %計(jì)算信源熵 fprintf( 平均碼長 :n );K=sum(p.*k) %計(jì)算平均碼長 fprintf( 編碼效率 :n ); w=H./K %計(jì)算編碼效率 fprintf( 碼字 :n );c程序運(yùn)行結(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、費(fèi)諾編碼程序主程序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; %是否到達(dá)尾部的標(biāo)志 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; %從分界點(diǎn)對兩邊的碼遞歸做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) %計(jì)算信源熵fprintf( 平均碼長 :n )K=sum(count.*p) %計(jì)算平均碼長fprintf( 編碼效率 :n )w=H./K%計(jì)算編碼效率fprintf( 碼字 :n)c程序運(yùn)行結(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è)計(jì)前前后后花了三天時(shí)間，之前并沒有用心 想，只是看了看網(wǎng)上的資料，看人家都是用什么方法解決的。我 看的有用C (包括C+和C#)語言的，有用 Matlab的，還有用 別的什么軟件的。由于我對 Matlab 編程還比較熟悉一點(diǎn)，最后 我還是選擇用 Matlab 來做。一開始編程，我甚至連一些常用的 Matlab 函數(shù)都忘了，沒什么想法后我在網(wǎng)上看了一些人用

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

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

22、=fopen( shuju.txt , r ); %打開 txt 文件ex,num=fscanf(fid, %c ,inf) %讀取二進(jìn)制文件的數(shù)據(jù)，并將數(shù)據(jù)存入矩陣 str1=lower(ex)%將字符串中的大寫字母轉(zhuǎn)換成小寫字母sort_str1=sort(str1);%按照字符的 ASCII 值對字符串排序j=1;for i=1:length(sort_str1)-1%計(jì)算出字符串的種類if strcmp(sort_str1(i),sort_str1(i+1)=1%比較兩個(gè)字符串是否完全相等，相等是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)%計(jì)算信源熵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);%碼長計(jì)算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) %計(jì)算信源熵 fprintf( 平均碼長 :n );K=sum(p.*k) %計(jì)算平均碼長 fprintf( 編碼效率 :n );