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

1、河南理工大學(xué)課程設(shè)計報告書信息論與編碼課程設(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)編碼方法進行編碼，并計算信源熵和編碼效率。

2、3.費諾編碼要求：任意輸入消息概率，利用費諾編碼方法進行編碼，并計算信源熵和編碼效率。二、 設(shè)計思路1、統(tǒng)計信源熵：統(tǒng)計信源熵就是對一篇英文文章中的種字符（包括標點符號及空格，英文字母不區(qū)分大小寫）統(tǒng)計其出現(xiàn)的次數(shù)，然后計算其出現(xiàn)的概率，最后由信源熵計算公式： 算出信源熵。所以整體步驟就是先統(tǒng)計出文章中總的字符數(shù)，然后統(tǒng)計每種字符的數(shù)目，直到算出所有種類的字符的個數(shù)，進而算出每種字符的概率，再由信源熵計算公式計算出信源熵。在這里我選擇用Matlab來計算信源熵，因為Matlab中系統(tǒng)自帶了許多文件操作和字符串操作函數(shù)，其計算功能強大，所以計算信源熵很是簡單。2、香農(nóng)編碼信源編碼模型：信源編碼就

3、是從信源符號到碼符號的一種映射，它把信源輸出的符號變換成碼元序列。 信源編碼器 信源 碼元 碼符號次擴展信源無失真編碼器凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合都可以稱為最佳碼。為此必須將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字長度最短。能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）、費諾（Fano）、哈夫曼（Huffman）編碼等。香農(nóng)第一定理：離散無記憶信源為熵,其次擴展為熵為,碼符號集為。先對信源進行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使中每個信源符號所需的平均碼長滿足且當(dāng)時有 ，是平均碼長，是對應(yīng)的碼字長度。香農(nóng)

4、編碼方法：（1） 將信源消息符號按其出現(xiàn)的概率大小依次排列: （2）確定滿足下列不等式整數(shù)碼長為（3）為了編成唯一可譯碼，計算第個消息的累加概率為（4）將累加概率變成二進制數(shù)。 （5）取二進制數(shù)小數(shù)點后位即為該消息符號的二進制碼字。 3、費諾編碼方法 （1）將信源消息符號按其出現(xiàn)的概率大小依次排列：（2）將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近似相同，并對各組賦予一個二進制碼元“0”和“1”。（3）將每一大組的信源符號再分為兩組，使劃分后的兩個組的概率之和近似相同，并對各組賦予一個二進制符號“0”和“1”。 （4）如此重復(fù)，直至每個組只剩下一個信源符號為

5、止。 （5）信源符號所對應(yīng)的碼字即為費諾碼。三、 設(shè)計流程圖1、 統(tǒng)計信源熵用Matlab讀入一段英文 計算這段文字的字符總數(shù)unm 統(tǒng)計每種字符的個數(shù)n(i) 算出每種字符的概率p(i) 由信源熵計算公式計算出信源熵 2、 香農(nóng)編碼開始輸入概率矩陣將概率由大到小排列計算累加概率和概率的個數(shù)根據(jù)公式調(diào)用函數(shù)計算碼長用循環(huán)程序編碼并調(diào)整輸出格式 計算信源熵和編碼效率輸出信源熵、編碼效率和碼字結(jié)束3、 費諾編碼開始輸入概率矩陣將概率由大到小排列計算累加概率和概率的個數(shù)在兩組概率之和近似相等的條件下將概率分為兩組，各賦予0，1兩個碼元將每一大組的的概率重復(fù)上一步操作，直到每組只剩一個概率

6、用循環(huán)程序編碼并調(diào)整輸出格式計算信源熵和編碼效率輸出信源熵、編碼效率和碼字結(jié)束四、 程序及結(jié)果1、 統(tǒng)計信源熵的Matlab程序function h=entropy(p)clcfid=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%計算出

7、字符串的種類 if strcmp(sort_str1(i),sort_str1(i+1)=1%比較兩個字符串是否完全相等，相等是1，否則0 j=j+1; str2(j)=sort_str1(i); end str2(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的位置 count1(i) = length(str_num);endstr2count=count1(3:end)p=cou

8、nt./sum(count)sum(-p.*log2(p)%計算信源熵待讀取的英文：The Pressure of Graduate StudentsNow 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

9、 are so heavy, the competition is so fierce that many students cant get the ideal jobs. They should adjust their strategies.The pressure of graduate students is so heavy. On the one hand, they dont have experience, so they dont know how to get the job interview and miss many chances. On the other ha

10、nd, there are more and more students have high education, some have received higher education, some have studies abroad which make their resumes stand out. Those average students dont have advantages over the above mentioned ones.Average students need to make their resumes specially, so they can hav

11、e the chance. They can describe their characteristic to fit the job, the employers 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 stude

12、nts take the wise strategy, they can have more chances to get the job.程序運行結(jié)果：總共出現(xiàn)的字符種類： ,.abcdefghijklmnoprstuvwxy每種字符對應(yīng)出現(xiàn)的次數(shù)： 206 16 11 78 10 33 42 161 10 20 65 53 8 5 16 21 58 64 16 55 80 113 36 20 8 3 20 4每種字符出現(xiàn)的概率： 0.1672 0.0130 0.0089 0.0633 0.0081 0.0268 0.0341 0.1307 0.0081 0.0162 0.0528 0.04

13、30 0.0065 0.0041 0.0130 0.0170 0.0471 0.0519 0.0130 0.0446 0.0649 0.0917 0.0292 0.0162 0.0065 0.0024 0.0162 0.0032信源熵：4.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:n pa(i)=pa(i-1)+p(i-1); endk=ceil(-lo

14、g2(p);%碼長計算c=cell(1,n);%生成元胞數(shù)組，存碼字，是cell，跟上一行不一樣for i=1:n ci= '' tmp=pa(i); for j=1:k(i) tmp=tmp * 2; if tmp>=1 tmp=tmp - 1; ci(j)= '1' else ci(j)= '0' end endend%p%pa%交換回原來的順序c=fliplr(c);c(index)=c;fprintf('信源信息熵:n');H=sum(-p.*log2(p)%計算信源熵fprintf('平均碼長:n'

15、);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);信源信息熵:H = 2.4232平均碼長:K = 2.7000編碼效率:w = 0.8975碼字:c = '01' '00' '100' '101' '1101' '11110'3、 費諾編碼程序主程序function c=fano1

16、(p)% p=0.25 0.25 0.20 0.15 0.10 0.05% c=fano1(p)n=size(p,2);if n=1 c=cell(1,1); c1='' returnendp,index=sort(p);%按概率排序p=fliplr(p);total=sum(p);%總概率acc=0;%累積概率flag=0;%是否到達尾部的標志for i=1:n-1 newacc=acc+p(i); if abs(total-2 * newacc)>=abs(total - 2*acc) flag=1; break; end acc=newacc;endif flag

17、i=n;endsplit=i;%從分界點對兩邊的碼遞歸做fanoc1=fano1(p(1:split-1);c2=fano1(p(split:n);c=cell(1,n);%添加前綴0，1for i=1:split-1 ci=strcat('0',c1i);endfor i = split:n ci=strcat('1',c2i-split+1 );end%將順序調(diào)整回去c=fliplr(c);c(index)=c;子程序function =fano2(c,p)for i=1:length(c)%求平均碼長 count(i)=length(cell2mat(c(

18、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.0500c = '00' '01'

19、'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

20、編程還比較熟悉一點，最后我還是選擇用Matlab來做。一開始編程，我甚至連一些常用的Matlab函數(shù)都忘了，沒什么想法后我在網(wǎng)上看了一些人用Matlab編的程序，拿來仔細研究后也慢慢著編出了自己的程序。在編程過程中，遇到了各種問題問題，有時由于一個小問題不通，我要反復(fù)琢磨半天，最后發(fā)現(xiàn)是在一個小地方上出錯了，真是備受煎熬，但這也是編程的樂趣所在，在這個過程中自己也學(xué)到了許多編程知識和技巧。在編程過程中，我體會到了Matlab功能的強大，我需要好好學(xué)習(xí)一下，這對我以后在信號處理與仿真計算上有很大幫助。通過這次課程設(shè)計，我對信息論與編碼技術(shù)中的一些基礎(chǔ)知識，如信源熵、通信系統(tǒng)模型、信道與信源編碼等

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

22、附錄1、統(tǒng)計信源熵的Matlab程序function h=entropy(p)clcfid=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

23、%比較兩個字符串是否完全相等，相等是1，否則0 j=j+1; str2(j)=sort_str1(i); end str2(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的位置 count1(i) = length(str_num);endstr2count=count1(3:end)p=count./sum(count)sum(-p.*log2(p)%計算信源熵2、香農(nóng)編碼程序fun

24、ction 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:n pa(i)=pa(i-1)+p(i-1); endk=ceil(-log2(p);%碼長計算c=cell(1,n);%生成元胞數(shù)組，存碼字，是cell，跟上一行不一樣for i=1:n ci= '' tmp=pa(i); for j=1:k(i) tmp=tmp * 2; if tmp>=1 tmp=tmp - 1; ci(j)= '1' else ci(j)= '0' end endend%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