信息論與編碼 (2)

1、一 設(shè)計目的 信息論與編碼是我們電子信息工程的一門重要的專業(yè)課，通過對本次課程設(shè)計，學(xué)習(xí)將學(xué)到的理論知識用于實踐，同時也學(xué)習(xí)了用軟件編寫程序，進(jìn)一步對本課程知識的鞏固和理解。學(xué)習(xí)分析問題，解決問題的方法和途徑，提高對本專業(yè)的學(xué)習(xí)興趣。二 設(shè)計任務(wù)與要求（1）統(tǒng)計信源熵要求：統(tǒng)計任意文本文件中各字符（不區(qū)分大小寫）數(shù)量，計算字符概率，并計算信源熵。（2）哈夫曼編碼要求：任意輸入消息概率，利用哈夫曼編碼方法進(jìn)行編碼，并計算信源熵和編碼效率。三 理論簡介3.1通信系統(tǒng)的模型 通信系統(tǒng)的模型通信系統(tǒng)的性能指標(biāo)主要是有效性、可靠性、安全性和經(jīng)濟(jì)性，通信系統(tǒng)優(yōu)化就是使這些指標(biāo)達(dá)到最佳，除了經(jīng)濟(jì)性，這些指標(biāo)

2、正是信息論的研究對象，可以通過各種編碼處理來使通信系統(tǒng)的性能最優(yōu)化。根據(jù)信息論的各種編碼定理和上述通信系統(tǒng)的指標(biāo)，編碼問題可以分為3類：信源編碼、信道編碼和加密編碼。3.1.1 信源編碼由于信源符號之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余度，提高編碼效率。信源編碼的基礎(chǔ)是信息論中的兩個編碼定理：無失真編碼定理和限失真編碼定理。前者適用于離散信源或數(shù)字信號；后者主要用于連續(xù)信源或模擬信號。本次課程設(shè)計就是利用的無失真信源編碼。3.1.2 信道編碼信源編碼器的作用：把信源發(fā)出的消息變換成由二進(jìn)制碼元(或多進(jìn)制碼元)組成的代碼組，這種代碼組就是基帶信號。同時通過

3、信源編碼可以壓縮信源的冗余度，以提高通信系統(tǒng)傳輸消息的效率。信源譯碼器的作用：把信道譯碼器輸出的代碼組變換成信宿所需要的消息形式，它的作用相當(dāng)于信源編碼器的逆過程。3.1.3 加密編碼 加密編碼是研究如何隱蔽消息中的信息內(nèi)容，以便在傳輸過程中不被竊聽，提高通信系統(tǒng)的安全性。3.2 信源熵3.2.1 信源的描述和分類& 按信源在時間和幅度上的分布情況 離散信源：文字、數(shù)據(jù)、電報 連續(xù)信源：語音、圖像& 按發(fā)出符號的數(shù)量 單個符號信源：指信源每次只發(fā)出一個符號代表一個消息 符號序列信源：指信源每次發(fā)出一組含二個以上符號的符號序列代表一個消息& 按符號間的關(guān)系 無記憶信源 有

4、記憶信源3.2.2 離散信源熵& 自信息量：隨機(jī)事件的自信息量定義為其概率對數(shù)的負(fù)值，即 在信息論中常用的對數(shù)底是2，信息量的單位為比特(bit)；& 聯(lián)合自信息量兩個消息xi，yj同時出現(xiàn)的聯(lián)合自信息量： & 條件自信息量 在事件yj出現(xiàn)的條件下，隨機(jī)事件xi發(fā)生的條件概率為p(xi / yj) ，則它的條件自信息量定義為條件概率對數(shù)的負(fù)值： & 離散信源熵為信源中各個符號不確定度的數(shù)學(xué)期望，即 單位為：比特/符號 或者 比特/符號序列。 信息熵H(X)表示信源輸出后，每個消息(或符號)所提供的平均信息量。四設(shè)計思路4.1 編碼效率編碼效率計算公式如下： 其中

5、H（X）為信源熵，K表示平均碼長。4.2 變長碼的編碼方法 能獲得最佳碼的編碼方法主要有： 香農(nóng)（Shannon） 費諾（Fano） 霍夫曼（Huffman4.2.1 香農(nóng)編碼將信源消息符號按其概率從大到小排列確定滿足下列不等式的整數(shù)碼長Ki令P1=0，計算第i個消息的累加概率將累加概率Pi變換成二進(jìn)制數(shù)，取小數(shù)點后Ki位為該消息的碼字4.2.2 費諾編碼 費諾編碼屬于概率匹配編碼，不是最佳的編碼方法。編碼過程如下： （1）將信源消息符號按其出現(xiàn)的概率依次排列p(x1) p(x2) p(xn) （2）按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等，并為每一組分配一位碼元。如編二進(jìn)制碼就分成

6、兩組，編m進(jìn)制碼就分成m組。 （3）將每一分組再按同樣原則劃分，重復(fù)步驟2，直至概率不再可分為止。 （4）信源符號所對應(yīng)的碼字即為費諾碼。4.2.3 哈夫曼編碼 （1）將信源消息符號按其出現(xiàn)的概率大小依次排列 p(x1)p(x2) p(xn) （2）取兩個概率最小的符號分別配以0和1，并將這兩個概率相加作為一個新符號的概率，與未分配碼元的符號重新排隊。 （3）對重排后的兩個概率最小符號重復(fù)步驟2的過程。 （4）繼續(xù)上述過程，直到最后兩個符號配以0和1為止。 （5）從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。4.3 設(shè)計思路4.3.1 統(tǒng)計信源熵的設(shè)計思路在VC+環(huán)境

7、中進(jìn)行編程 （1）打開一篇文章，將26個英文字母及空格作為信源。 （2）計算每個字母出現(xiàn)的次數(shù)（不區(qū)分大小寫），再通過計算信源總大小來計算在本篇文章中每個字母出現(xiàn)的概率。 （3）通過信源熵計算公式來計算信源熵。4.3.2 哈弗曼編碼的設(shè)計思路 在matlab中進(jìn)行編碼（1） 輸入概率矩陣，并檢驗是否正確，即各概率不能小于零，總概率之和等于一。（2） 建立各概率符號的位置索引矩陣Index,利于編碼后從樹根進(jìn)行回溯,從而得出對應(yīng)的編碼（3） 輸出所需的哈弗曼編碼。（4） 計算信源熵，并計算平均碼長，算出編碼效率。（5） 輸出結(jié)果。五 設(shè)計流程圖5.1統(tǒng)計信源熵的設(shè)計思路 5.2哈弗曼編碼設(shè)計思路

8、 六 程序運(yùn)行及結(jié)果6.1統(tǒng)計信源熵程序運(yùn)行結(jié)果測試輸入:text.txt There is no hate without fear. Hate is crystallized fear, fears dividend, fear objectivized. We hate what we fear and so where hate is, fear is lurking. Thus we hate what threatens our person, our vanity and our dreams and plans for ourselves. If we can isolate

9、this element in what we hate we may be able to cease from hating.測試目的：檢驗程序是否正確。檢驗方法：用驗證法來檢驗；看中概率是否為一，并檢測信源熵是否正確。檢驗結(jié)果：程序運(yùn)行結(jié)果正確。如下截屏所示6.2哈弗曼編碼程序運(yùn)行結(jié)果測試輸入：0.2 0.19 0.18 0.17 0.15 0.10 0.01測試目的：測試經(jīng)常出現(xiàn)的信源符號是否對應(yīng)較短的碼長，檢測程序運(yùn)行結(jié)果是否正確。正確輸出：01 00 111 110 101 1001 1000 信源熵為2.6087 bit/符號 平均碼長為2.7 碼元/符號 傳送速率為0.9591

10、 bit/碼元實際輸出：與爭取而輸出一樣檢測結(jié)果：程序無錯誤以下為截屏八 心得體會 課程設(shè)計是非常鍛煉我們能力的一種方法，在準(zhǔn)備課程設(shè)計的過程中，各方面都有所提高。首先，再一次對課本知識進(jìn)行學(xué)習(xí)，將所有設(shè)計到的知識重新溫習(xí)一遍，并且針對設(shè)計，還要看些其它相關(guān)書籍，對知識進(jìn)行升華，其次，針對課程設(shè)計，必須針對其要求進(jìn)一步提取有效內(nèi)容，鍛煉分析問題，解決問題的能力，盡管本次課程設(shè)計相對簡單些，我們還是需要從各方面進(jìn)行準(zhǔn)備，另外就是編寫程序，這是本次課程設(shè)計的關(guān)鍵，編寫程序，從不懂到會，這無疑又是一種極大的提高，還有在編程時遇見了不少問題，各種函數(shù)的應(yīng)用都在考驗著我們，然后便是我們小組的合作精神，隨

11、著學(xué)習(xí)的深入和實踐的鍛煉，我們越來越覺得團(tuán)隊合作對于我們的重要性，在現(xiàn)在的社會，幾乎沒有人可以脫離團(tuán)體單獨工作，科技的發(fā)展，人類的進(jìn)步，我們社會工作狀態(tài)都呈現(xiàn)了一種個人分工，集體作戰(zhàn)的策略，因此，在我們未正式進(jìn)入社會之前，能夠鍛煉自己的團(tuán)隊精神，這是相當(dāng)好的。 參考文獻(xiàn)1 曹雪虹、張宗橙編著信息論與編碼.清華大學(xué)出版社，2009年第2版2 賈宗璞、許合利編著C語言程序設(shè)計.人民郵電出版社，2010年第1版3 嚴(yán)蔚敏、吳偉民編著數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社，1997年第1版附錄源程序清單一統(tǒng)計信源熵 /要求：統(tǒng)計任意文本文件中各字符（不區(qū)分大小寫）數(shù)量，計算字母及空格概率，并計算信源熵。

12、#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#define N 1000 /出錯地方：字符總數(shù)不對，求字符串長度有問題。似乎跟N有關(guān)。int main(void) /沒有輸出字符個數(shù)。 char sN,MN; int i = 0,j=0,n=0,L=0; int len, num27 = 0; double result=0,p27= 0; FILE *f; char tempN; /*以下是打開一個指定文件的過程*/ if(!(f = fope

13、n("C:test2.txt","rb") printf("文件打開失??！n");return 0; while(!feof(f) /feof輸入輸出函數(shù)，檢查文件是否結(jié)束，如結(jié)束，則返回非零值，否則返回0 .函數(shù)原型為：int feof(FILE *fp) len = fread(temp,1,486,f); /fread返回讀取的字符個數(shù) temp為內(nèi)存區(qū)域首地址 1為每次讀入字節(jié)數(shù) 486讀入次數(shù) f指針 fclose(f); /關(guān)閉文件 templen = '0' /方便統(tǒng)計字符總數(shù) memcpy(s, tem

14、p, sizeof(temp); /從temp中拷貝sizeof個字節(jié)到目標(biāo)s中 /*統(tǒng)計26個字母及空格出現(xiàn)次數(shù)*/ for(i=0; i<strlen(s); i+) if(si=' ') num26+; else if(si>='a'&&si<='z') numsi-97+; else if(si>='A'&&si<='Z') numsi-65+; printf("文檔中各個字母出現(xiàn)的次數(shù):n"); for(j=0; j<

15、26; j+)Mj=numj; printf("%3c:%dt",j+65,Mj);L+; if(L=3) printf("n"); L=0; printf("空格:%dt",num26); /*統(tǒng)計26個字母或者空格出現(xiàn)概率*/ printf("n文檔中各個字母出現(xiàn)的概率:n"); for(i=0; i<26; i+) pi=(double)numi/strlen(s); printf("%3c:%ft",i+65,pi); n+; if(n=3) printf("n"

16、;); n=0; p26=(double)num26/strlen(s); printf("空格:%ft",p26); printf("n");/*計算信源熵*/ for(i=0; i<27; i+) if (pi!=0) result=result+pi*log(pi)*1.433; result=-result; printf("信源熵為:%f",result); printf(" n文章總字符長度:%d",strlen(temp); printf("n"); return 0;二哈夫

17、曼編碼%要求：任意輸入消息概率，利用上述編碼方法進(jìn)行編碼，并計算信源熵和編碼效率。>> clear;P=input('請輸入信源概率向量P=');N=length(P);for component=1:1:N if(P(component)<0) error('信源概率不能小于0'); endendif(sum(P)-1)>0.0001) error('信源概率之和必須為1');end%建立各概率符號的位置索引矩陣Index,利于編碼后從樹根進(jìn)行回溯,從而得出對應(yīng)的編碼Q=PIndex=zeros(N-1,N); %初始化

18、Index for i=1:N-1 Q,L=sort(Q); Index(i,:)=L(1:N-i+1),zeros(1,i-1); G(i,:)=Q; Q=Q(1)+Q(2),Q(3:N),1; %將Q中概率最小的兩個元素合并，元素不足的地方補(bǔ)1end %根據(jù)以上建立的Index矩陣，進(jìn)行回溯，獲取信源編碼for i=1:N-1Char(i,:)=blanks(N*N);%初始化一個由空格符組成的字符矩陣N*N,用于存放編碼end %從碼樹的樹根向樹葉回溯，即從G矩陣的最后一行按與Index中的索引位置的對應(yīng)關(guān)系向其第一行進(jìn)行編碼Char(N-1,N)='0' %G中的N-1

19、行即最后一行第一個元素賦為0，存到Char中N-1行的N列位置Char(N-1,2*N)='1'%G中的N-1行即最后一行第二個元素賦為1，存到Char中N-1行的2*N列位置 %以下從G的倒數(shù)第二行開始向前編碼for i=2:N-1 Char(N-i,1:N-1)=Char(N-i+1,N*(find(Index(N-i+1,:)=1) -(N-2):N*(find(Index(N-i+1,:)=1); %將Index后一行中索引為1的編碼碼字填入到當(dāng)前行的第一個編碼位置 Char(N-i,N)='0' %然后在當(dāng)前行的第一個編碼位置末尾填入'0

20、9; Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); %將G后一行中索引為1的編碼碼字填入到當(dāng)前行的第二個編碼位置 Char(N-i,2*N)='1' %然后在當(dāng)前行的第二個編碼位置末尾填入'1' for j=1:i-1 %內(nèi)循環(huán)作用：將Index后一行中索引不為1處的編碼按照左右順序填入當(dāng)前行的第3個位置開始的地方,最后計算到Index的首行為止. Char(N-i,(j+1)*N+1:(j+2)*N)=Char(N-i+1,N*(find(Index(N-i+1,:)=j+1)-1)+1:N*find(Index(N-i+1,:)=j+1); end end %Char中第一行的編碼結(jié)果就是所需的Huffman 編碼輸出，通過Index中第一行索引將編碼對應(yīng)到相應(yīng)概率的信源符號上。 for i=1:N Result(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N); h(i)=length(find(abs(Result(i,:)=32)