霍夫曼編碼的matlab實現(xiàn)(信源編碼實驗)

1、重慶交通大學信息科學與工程學院綜合性設計性實驗報告專 業(yè) 班 級： 通信工程2012級1班 學 號： 8 姓 名： 王松 實驗所屬課程： 信息論與編碼 實驗室(中心)： 軟件與通信實驗中心 指 導 教 師 ： 黃大榮 2015年4月教師評閱意見：簽名： 年 月 日實驗成績：霍夫曼編碼的matlab實現(xiàn)一、實驗目的和要求。利用哈夫曼編碼進行通信可以大大提高信道的利用率，縮短信息傳輸?shù)臅r間，降低傳輸成本。本實驗用Matlab語言編程實現(xiàn)霍夫曼（Huffman）編碼。二、實驗原理。霍夫曼（Huffman）編碼算法是滿足前綴條件的平均二進制碼長最短的編-源輸出符號，而將較短的編碼碼字分配給較大概率的信

2、源輸出。算法是：在信源符號集合中，首先將兩個最小概率的信源輸出合并為新的輸出，其概率是兩個相應輸出符號概率之和。這一過程重復下去，直到只剩下一個合并輸出為止，這個最后的合并輸出符號的概率為1。這樣就得到了一張樹圖，從樹根開始，將編碼符號1 和0 分配在同一節(jié)點的任意兩分支上，這一分配過程重復直到樹葉。從樹根到樹葉途經(jīng)支路上的編碼最后就構成了一組異前置碼，就是霍夫曼編碼輸出。離散無記憶信源：例如 U u1 u2 u3 u4 u5 P(U) = 0.4 0.2 0.2 0.1 0.1 碼字Wi信符si概率P(si)編碼過程第一次第二次第三次W1=0W2=10W3=111W4=1101W5=1100

3、S1S2S3S4S50.40.20.20.10.1 0.4 0.2 0.21 0.200.40.410.200.61 0.401 A(1) 0通過上表的對信源縮減合并過程，從而完成了對信源的霍夫曼編碼。三、實驗步驟分為兩步，首先是碼樹形成過程：對信源概率進行合并形成編碼碼樹。然后是碼樹回溯過程：在碼樹上分配編碼碼字并最終得到霍夫曼編碼。1、碼樹形成過程：將信源概率按照從小到大順序排序并建立相應的位置索引。然后按上述規(guī)則進行信源合并，再對信源進行排序并建立新的位置索引，直到合并結束。在這一過程中每一次都把排序后的信源概率存入矩陣G中，位置索引存入矩陣Index中。這樣，由排序之后的概率矩陣G以及

4、索引矩陣Index就可以恢復原概率矩陣P了，從而保證了回溯過程能夠進行下去。2、碼樹回溯過程：在碼樹上分配編碼碼字并最終得到Huffman 編碼。從索引矩陣M 的末行開始回溯。(1) 在Index 的末行2元素位置填入0和1。(2) 根據(jù)該行索引1 位置指示，將索引1 位置的編碼（1）填入上一行的第一、第二元素位置，并在它們之后分別添加0和1。(3) 將索引不為1的位置的編碼值（0）填入上一行的相應位置（第3 列）。(4) 以Index的倒數(shù)第二行開始向上，重復步驟(1) (3)，直到計算至Index的首行為止。四、程序代碼：%取得信源概率矩陣,并進行合法性判斷clear;P=input(請輸

5、入信源概率向量P=);N=length(P);for component=1:1:N if(P(component)0.0001) error(信源概率之和必須為1);end%建立各概率符號的位置索引矩陣Index,利于編碼后從樹根進行回溯,從而得出對應的編碼Q=PIndex=zeros(N-1,N); %初始化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中概率最小的兩個元素合并，元素不足的地方補1end%根據(jù)以上建立的Index矩陣，

6、進行回溯，獲取信源編碼for i=1:N-1 Char(i,:)=blanks(N*N);%初始化一個由空格符組成的字符矩陣N*N,用于存放編碼end%從碼樹的樹根向樹葉回溯，即從G矩陣的最后一行按與Index中的索引位置的對應關系向其第一行進行編碼Char(N-1,N)=0;%G中的N-1行即最后一行第一個元素賦為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(Ind

7、ex(N-i+1,:)=1) -(N-2):N*(find(Index(N-i+1,:)=1); %將Index后一行中索引為1的編碼碼字填入到當前行的第一個編碼位置 Char(N-i,N)=0; %然后在當前行的第一個編碼位置末尾填入0 Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); %將G后一行中索引為1的編碼碼字填入到當前行的第二個編碼位置 Char(N-i,2*N)=1; %然后在當前行的第二個編碼位置末尾填入1 for j=1:i-1 %內循環(huán)作用：將Index后一行中索引不為1處的編碼按照左右順序填入當前行的第3個位置開始的地方,最后計算到Index的首行

8、為止 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中第一行的編碼結果就是所需的Huffman 編碼輸出，通過Index中第一行索引將編碼對應到相應概率的信源符號上。 for i=1:N Result(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N); end %打印編碼結果 String=信源概率及其對應的Huffman編碼如下; disp

9、(String);disp(P);disp(Result);五、對比分析，通過給給定不同的信源，對結果進行分析對比驗證，并得出相應分分析報告。以0.1,0.2,0.3,0.2,0.1,0.1為例：運行程序，結果如下以0.3 0.3 0.2 0.1 0.1為例：運行程序，結果如下分析：由上圖可知程序已完成了Huffman編碼的功能，但是霍夫曼編碼是不唯一的.因為：信源符號合并中遇到最小概率相同的情況時可任意選擇來做合并；在碼樹分配編碼碼字的時候1和0的位置可以是任意的。六：提交實驗報告。1、在該實驗的過程中，利用一個矩陣記錄每次排序前概率的所在位置，是該實驗的關鍵，在編碼的過程中利用該矩陣就能比較容易進行huffman編碼。2、通過這個實驗，對huffman編碼的具體實現(xiàn)原理了解的更加深刻，在實驗的過程中也遇到了一些問題，通過查找資料和相關書籍得到了解決，通過此次試驗，了解了Huffman編碼的特點，能夠運用Huffman編碼的基本原理及編碼算法的來設計與實現(xiàn)程序。收獲頗多，為以后更進一步學習奠定了基礎,總的來說，在完成該實驗的過程中，學到了比較多的知識，包括使對一些matlab語句的掌握的更加熟練，完成一個算法必須要有一個整體的把握等等。3、通過本次課程設計，我對二叉樹和huffman編碼樹有了更深的了解，在做課程設計的