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

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

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

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

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

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

6、用循環(huán)程序編碼并調(diào)整輸出格式計(jì)算信源熵和編碼效率輸出信源熵、編碼效率和碼字結(jié)束四、 程序及結(jié)果1、 統(tǒng)計(jì)信源熵的Matlab程序function h=entropy(p)clcfid=fopen('shuju.txt','r');%打開(kāi)txt文件ex,num=fscanf(fid,'%c',inf)%讀取二進(jìn)制文件的數(shù)據(jù)，并將數(shù)據(jù)存入矩陣str1=lower(ex)%將字符串中的大寫(xiě)字母轉(zhuǎn)換成小寫(xiě)字母sort_str1=sort(str1);%按照字符的ASCII值對(duì)字符串排序j=1;for i=1:length(sort_str1)-1%計(jì)算出

7、字符串的種類(lèi) if strcmp(sort_str1(i),sort_str1(i+1)=1%比較兩個(gè)字符串是否完全相等，相等是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ù)獲取字符串長(zhǎng)度 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)%計(jì)算信源熵待讀取的英文：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.程序運(yùn)行結(jié)果：總共出現(xiàn)的字符種類(lèi)： ,.abcdefghijklmnoprstuvwxy每種字符對(duì)應(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);%碼長(zhǎng)計(jì)算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%交換回原來(lái)的順序c=fliplr(c);c(index)=c;fprintf('信源信息熵:n');H=sum(-p.*log2(p)%計(jì)算信源熵fprintf('平均碼長(zhǎng):n'

15、);K=sum(p.*k)%計(jì)算平均碼長(zhǎng)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);信源信息熵:H = 2.4232平均碼長(zhǎng):K = 2.7000編碼效率:w = 0.8975碼字:c = '01' '00' '100' '101' '1101' '11110'3、 費(fèi)諾編碼程序主程序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;%是否到達(dá)尾部的標(biāo)志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;%從分界點(diǎn)對(duì)兩邊的碼遞歸做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)%求平均碼長(zhǎng) count(i)=length(cell2mat(c(

18、i); endfprintf('信源信息熵:n');H=sum(-p.*log2(p)%計(jì)算信源熵fprintf('平均碼長(zhǎng):n')K=sum(count.*p)%計(jì)算平均碼長(zhǎng)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.0500c = '00' '01'

19、'10' '110' '1110' '1111'信源信息熵:H = 2.4232平均碼長(zhǎng):K = 2.4500編碼效率:w = 0.9891碼字:c = '00' '01' '10' '110' '1110' '1111'五、 心得體會(huì)做這次課程設(shè)計(jì)前前后后花了三天時(shí)間，之前并沒(méi)有用心想，只是看了看網(wǎng)上的資料，看人家都是用什么方法解決的。我看的有用C（包括C+和C#）語(yǔ)言的，有用Matlab的，還有用別的什么軟件的。由于我對(duì)Matlab

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

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

22、附錄1、統(tǒng)計(jì)信源熵的Matlab程序function h=entropy(p)clcfid=fopen('shuju.txt','r');%打開(kāi)txt文件ex,num=fscanf(fid,'%c',inf)%讀取二進(jìn)制文件的數(shù)據(jù)，并將數(shù)據(jù)存入矩陣str1=lower(ex)%將字符串中的大寫(xiě)字母轉(zhuǎn)換成小寫(xiě)字母sort_str1=sort(str1);%按照字符的ASCII值對(duì)字符串排序j=1;for i=1:length(sort_str1)-1%計(jì)算出字符串的種類(lèi) if strcmp(sort_str1(i),sort_str1(i+1)=1

23、%比較兩個(gè)字符串是否完全相等，相等是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ù)獲取字符串長(zhǎng)度 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)編碼程序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);%碼長(zhǎng)計(jì)算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%交換回原來(lái)的順序c=fliplr(c);c(index)=c;fprintf('信源信息熵:n');H=sum(-p.*log2(p)%計(jì)算信源熵fprintf('平均碼長(zhǎng):n');K=sum(p.*k)%計(jì)算平均碼長(zhǎng)fprintf('編碼效率:n');w=H./K%計(jì)算編碼效率fprintf('碼字:n