霍夫曼編碼的matlab實(shí)現(xiàn)(信源編碼實(shí)驗(yàn))(共9頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上重慶交通大學(xué)信息科學(xué)與工程學(xué)院綜合性設(shè)計(jì)性實(shí)驗(yàn)報(bào)告專 業(yè) 班 級(jí)： 通信工程2012級(jí)1班 學(xué) 號(hào)： 8 姓 名： 王松 實(shí)驗(yàn)所屬課程： 信息論與編碼 實(shí)驗(yàn)室(中心)： 軟件與通信實(shí)驗(yàn)中心 指 導(dǎo) 教 師 ： 黃大榮 2015年4月教師評(píng)閱意見：簽名： 年 月 日實(shí)驗(yàn)成績(jī)：霍夫曼編碼的matlab實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康暮鸵?。利用哈夫曼編碼進(jìn)行通信可以大大提高信道的利用率，縮短信息傳輸?shù)臅r(shí)間，降低傳輸成本。本實(shí)驗(yàn)用Matlab語言編程實(shí)現(xiàn)霍夫曼（Huffman）編碼。二、實(shí)驗(yàn)原理?；舴蚵℉uffman）編碼算法是滿足前綴條件的平均二進(jìn)制碼長(zhǎng)最短的編-源輸出符號(hào)，而將較短的

2、編碼碼字分配給較大概率的信源輸出。算法是：在信源符號(hào)集合中，首先將兩個(gè)最小概率的信源輸出合并為新的輸出，其概率是兩個(gè)相應(yīng)輸出符號(hào)概率之和。這一過程重復(fù)下去，直到只剩下一個(gè)合并輸出為止，這個(gè)最后的合并輸出符號(hào)的概率為1。這樣就得到了一張樹圖，從樹根開始，將編碼符號(hào)1 和0 分配在同一節(jié)點(diǎn)的任意兩分支上，這一分配過程重復(fù)直到樹葉。從樹根到樹葉途經(jīng)支路上的編碼最后就構(gòu)成了一組異前置碼，就是霍夫曼編碼輸出。離散無記憶信源：例如 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=111W

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

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

5、性判斷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); %初始化Index for i=1:N-1 Q,L=sort(Q); Index(i,:)=L(1:N

6、-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-1 Char(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行即最后一行第一個(gè)元素賦為0，存到Char中N-1行的N列位置Char(N-1,2*N)='

7、;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' Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); %將G后一行中索引為

8、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 編碼輸出，通過Ind

9、ex中第一行索引將編碼對(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); end %打印編碼結(jié)果 String='信源概率及其對(duì)應(yīng)的Huffman編碼如下' disp(String);disp(P);disp(Result);五、對(duì)比分析，通過給給定不同的信源，對(duì)結(jié)果進(jìn)行分析對(duì)比驗(yàn)證，并得出相應(yīng)分分析報(bào)告。以0.1,0.2,0.3,0.2,0.1,0.1為例：運(yùn)行程序，結(jié)果如下以0.3 0.3 0.2 0.1 0.1為例：運(yùn)行程序，結(jié)果如下

10、分析：由上圖可知程序已完成了Huffman編碼的功能，但是霍夫曼編碼是不唯一的.因?yàn)椋盒旁捶?hào)合并中遇到最小概率相同的情況時(shí)可任意選擇來做合并；在碼樹分配編碼碼字的時(shí)候1 和0 的位置可以是任意的。六：提交實(shí)驗(yàn)報(bào)告。1、在該實(shí)驗(yàn)的過程中，利用一個(gè)矩陣記錄每次排序前概率的所在位置，是該實(shí)驗(yàn)的關(guān)鍵，在編碼的過程中利用該矩陣就能比較容易進(jìn)行huffman編碼。 2、通過這個(gè)實(shí)驗(yàn)，對(duì)huffman編碼的具體實(shí)現(xiàn)原理了解的更加深刻，在實(shí)驗(yàn)的過程中也遇到了一些問題，通過查找資料和相關(guān)書籍得到了解決，通過此次試驗(yàn)，了解了Huffman編碼的特點(diǎn)，能夠運(yùn)用Huffman編碼的基本原理及編碼算法的來設(shè)計(jì)與實(shí)現(xiàn)程序。收獲頗多，為以后更進(jìn)一步學(xué)習(xí)奠定了基礎(chǔ), 總的來說，在完成該實(shí)驗(yàn)的過程中，學(xué)到了比較多的知識(shí)，包括使對(duì)一些matlab語句的掌握的更加熟練，完成一個(gè)算法必須要有一個(gè)整體的把握等等。3、通過本次課程設(shè)計(jì)，我對(duì)二叉樹和huffman編碼樹有了更深的了解，在做課程設(shè)計(jì)