信息論與編碼 (2)

1、一 設(shè)計(jì)目的 信息論與編碼是我們電子信息工程的一門重要的專業(yè)課，通過(guò)對(duì)本次課程設(shè)計(jì)，學(xué)習(xí)將學(xué)到的理論知識(shí)用于實(shí)踐，同時(shí)也學(xué)習(xí)了用軟件編寫程序，進(jìn)一步對(duì)本課程知識(shí)的鞏固和理解。學(xué)習(xí)分析問(wèn)題，解決問(wèn)題的方法和途徑，提高對(duì)本專業(yè)的學(xué)習(xí)興趣。二 設(shè)計(jì)任務(wù)與要求（1）統(tǒng)計(jì)信源熵要求：統(tǒng)計(jì)任意文本文件中各字符（不區(qū)分大小寫）數(shù)量，計(jì)算字符概率，并計(jì)算信源熵。（2）哈夫曼編碼要求：任意輸入消息概率，利用哈夫曼編碼方法進(jìn)行編碼，并計(jì)算信源熵和編碼效率。三 理論簡(jiǎ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、正是信息論的研究對(duì)象，可以通過(guò)各種編碼處理來(lái)使通信系統(tǒng)的性能最優(yōu)化。根據(jù)信息論的各種編碼定理和上述通信系統(tǒng)的指標(biāo)，編碼問(wèn)題可以分為3類：信源編碼、信道編碼和加密編碼。3.1.1 信源編碼由于信源符號(hào)之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余度，提高編碼效率。信源編碼的基礎(chǔ)是信息論中的兩個(gè)編碼定理：無(wú)失真編碼定理和限失真編碼定理。前者適用于離散信源或數(shù)字信號(hào)；后者主要用于連續(xù)信源或模擬信號(hào)。本次課程設(shè)計(jì)就是利用的無(wú)失真信源編碼。3.1.2 信道編碼信源編碼器的作用：把信源發(fā)出的消息變換成由二進(jìn)制碼元(或多進(jìn)制碼元)組成的代碼組，這種代碼組就是基帶信號(hào)。同時(shí)通過(guò)

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

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

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

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

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

8、 六 程序運(yùn)行及結(jié)果6.1統(tǒng)計(jì)信源熵程序運(yùn)行結(jié)果測(cè)試輸入: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.測(cè)試目的：檢驗(yàn)程序是否正確。檢驗(yàn)方法：用驗(yàn)證法來(lái)檢驗(yàn)；看中概率是否為一，并檢測(cè)信源熵是否正確。檢驗(yàn)結(jié)果：程序運(yùn)行結(jié)果正確。如下截屏所示6.2哈弗曼編碼程序運(yùn)行結(jié)果測(cè)試輸入：0.2 0.19 0.18 0.17 0.15 0.10 0.01測(cè)試目的：測(cè)試經(jīng)常出現(xiàn)的信源符號(hào)是否對(duì)應(yīng)較短的碼長(zhǎng)，檢測(cè)程序運(yùn)行結(jié)果是否正確。正確輸出：01 00 111 110 101 1001 1000 信源熵為2.6087 bit/符號(hào) 平均碼長(zhǎng)為2.7 碼元/符號(hào) 傳送速率為0.9591

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

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

12、#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#define N 1000 /出錯(cuò)地方：字符總數(shù)不對(duì)，求字符串長(zhǎng)度有問(wèn)題。似乎跟N有關(guān)。int main(void) /沒有輸出字符個(gè)數(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; /*以下是打開一個(gè)指定文件的過(guò)程*/ 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返回讀取的字符個(gè)數(shù) temp為內(nèi)存區(qū)域首地址 1為每次讀入字節(jié)數(shù) 486讀入次數(shù) f指針 fclose(f); /關(guān)閉文件 templen = '0' /方便統(tǒng)計(jì)字符總數(shù) memcpy(s, tem

14、p, sizeof(temp); /從temp中拷貝sizeof個(gè)字節(jié)到目標(biāo)s中 /*統(tǒng)計(jì)26個(gè)字母及空格出現(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("文檔中各個(gè)字母出現(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)計(jì)26個(gè)字母或者空格出現(xiàn)概率*/ printf("n文檔中各個(gè)字母出現(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");/*計(jì)算信源熵*/ for(i=0; i<27; i+) if (pi!=0) result=result+pi*log(pi)*1.433; result=-result; printf("信源熵為:%f",result); printf(" n文章總字符長(zhǎng)度:%d",strlen(temp); printf("n"); return 0;二哈夫

17、曼編碼%要求：任意輸入消息概率，利用上述編碼方法進(jìn)行編碼，并計(jì)算信源熵和編碼效率。>> clear;P=input('請(qǐng)輸入信源概率向量P=');N=length(P);for component=1:1:N if(P(component)<0) error('信源概率不能小于0'); endendif(sum(P)-1)>0.0001) error('信源概率之和必須為1');end%建立各概率符號(hào)的位置索引矩陣Index,利于編碼后從樹根進(jìn)行回溯,從而得出對(duì)應(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中概率最小的兩個(gè)元素合并，元素不足的地方補(bǔ)1end %根據(jù)以上建立的Index矩陣，進(jìn)行回溯，獲取信源編碼for i=1:N-1Char(i,:)=blanks(N*N);%初始化一個(gè)由空格符組成的字符矩陣N*N,用于存放編碼end %從碼樹的樹根向樹葉回溯，即從G矩陣的最后一行按與Index中的索引位置的對(duì)應(yīng)關(guān)系向其第一行進(jìn)行編碼Char(N-1,N)='0' %G中的N-1

19、行即最后一行第一個(gè)元素賦為0，存到Char中N-1行的N列位置Char(N-1,2*N)='1'%G中的N-1行即最后一行第二個(gè)元素賦為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)前行的第一個(gè)編碼位置 Char(N-i,N)='0' %然后在當(dāng)前行的第一個(gè)編碼位置末尾填入'0

20、9; Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); %將G后一行中索引為1的編碼碼字填入到當(dāng)前行的第二個(gè)編碼位置 Char(N-i,2*N)='1' %然后在當(dāng)前行的第二個(gè)編碼位置末尾填入'1' for j=1:i-1 %內(nèi)循環(huán)作用：將Index后一行中索引不為1處的編碼按照左右順序填入當(dāng)前行的第3個(gè)位置開始的地方,最后計(jì)算到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 編碼輸出，通過(guò)Index中第一行索引將編碼對(duì)應(yīng)到相應(yīng)概率的信源符號(hào)上。 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)