霍夫曼編碼的matlab實(shí)現(xiàn)

重慶交通大學(xué)信息科學(xué)與工程學(xué)院

綜合性設(shè)計(jì)性實(shí)驗(yàn)報(bào)告專業(yè)班級：通信工程2012級1班學(xué)號：名：實(shí)驗(yàn)所屬課程：信息論與編碼實(shí)驗(yàn)室（中心）：軟件與通信實(shí)驗(yàn)中心2015年4月

教師評閱意見:簽名:實(shí)驗(yàn)成績:教師評閱意見:簽名:實(shí)驗(yàn)成績:霍夫曼編碼的matlab實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康暮鸵?。利用哈夫曼編碼進(jìn)行通信可以大大提高信道的利用率，縮短信息傳輸?shù)臅r間，降低傳輸成本。本實(shí)驗(yàn)用Matlab語言編程實(shí)現(xiàn)霍夫曼（Huffman）編碼。二、實(shí)驗(yàn)原理?；舴蚵℉uffman）編碼算法是滿足前綴條件的平均二進(jìn)制碼長最短的編-源輸出符號，而將較短的編碼碼字分配給較大概率的信源輸出。算法是：在信源符號集合中，首先將兩個最小概率的信源輸出合并為新的輸出，其概率是兩個相應(yīng)輸出符號概率之和。這一過程重復(fù)下去，直到只剩下一個合并輸出為止，這個最后的合并輸出符號的概率為1。這樣就得到了一張樹圖，從樹根開始，將編碼符號1和0分配在同一節(jié)點(diǎn)的任意兩分支上，這一分配過程重復(fù)直到樹葉。從樹根到樹葉途經(jīng)支路上的編碼最后就構(gòu)成了一組異前置碼，就是霍夫曼編碼輸出。離散無記憶信源：例如uuu0.40.20.20.40.20.20.10.1信符si概率編碼過程P(s)i碼字Wi第一次第二次第三次W=01信符si概率編碼過程P(s)i碼字WiW=01W=102W=1113W=11014W=11005S1S2S3S4S50.40.20.20.1—*10.1—口00.40.40.20.40.2—10.2土234一書0.6—?0.401一A⑴?0if(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);%初始化Indexfori=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];%將。中概率最小的兩個元素合并，元素不足的地方補(bǔ)1end%根據(jù)以上建立的Index矩陣，進(jìn)行回溯，獲取信源編碼fori=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行即最后一行第一個元素賦為0，存到Char中N-1行的N列位置Char(N-1,2*N)='1';%G中的N-1行即最后一行第二個元素賦為1，存到Char中N-1行的2*N列位置%以下從G的倒數(shù)第二行開始向前編碼fori=2:N-1Char(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'Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1);%將6后一行中索引為1的編碼碼字填入到當(dāng)前行的第二個編碼位置Char(N-i,2*N)='1';%然后在當(dāng)前行的第二個編碼位置末尾填入’1'forj=1:i-1%內(nèi)循環(huán)作用：將Index后一行中索引不為1處的編碼按照左右順序填入當(dāng)前行的第3個位置開始的地方，最后計(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));endend%Char中第一行的編碼結(jié)果就是所需的Huffman編碼輸出，通過Index中第一行索引將編碼對應(yīng)到相應(yīng)概率的信源符號上。fori=1:NResult(i,1:N)二Char(1,N*(find(Index(1,:)==i)-1)+1:find(Index(1,:)==i)*N);end%打印編碼結(jié)果String='信源概率及其對應(yīng)的Huffman編碼如下’；disp(String);disp(P);disp(Result);五、對比分析，通過給給定不同的信源，對結(jié)果進(jìn)行分析對比驗(yàn)證，并得出相應(yīng)分分析報(bào)告。以［0.1,0.2,0.3,0.2,0.1,0.1］為例：運(yùn)行程序，結(jié)果如下?UiititledL請輸入信源信源向1,0.2,0.3,0.2,0.1,0.1：Q=0.10000.20000.30000.20000.10000.1000信源概率預(yù)其對應(yīng)的Huffman漏碼如下0.10000.20000.30000.20000.10000.1000LL1Q001001LL11L10|A?l以［0.30.30.20.10.1］為例:運(yùn)行程序，結(jié)果如下CommandWindow'①Newto-MATLAB?Watchthissee□己rnci*orreadGetting?UntLtledl倍輸入信源概率向iP=rO.30.30.30.10.L：Q=0.30000.30000.20000.10000.1000信源概率及其對應(yīng)的Huffman^碼如下0.30000.30000.20000.10000.100010LL01000001分析：由上圖可知程序已完成了Huffman編碼的功能，但是霍夫曼編碼是不唯一的.因?yàn)椋盒旁捶柡喜⒅杏龅阶钚「怕氏嗤那闆r時可任意選擇來做合并;在碼樹分配編碼碼字的時候1和0的位置可以是任意的。六：提交實(shí)驗(yàn)報(bào)告。1、在該實(shí)驗(yàn)的過程中，利用一個矩陣記錄每次排序前概率的所在位置，是該實(shí)驗(yàn)的關(guān)鍵，在編碼的過程中利用該矩陣就能比較容易進(jìn)行huffman編碼。2、通過這個實(shí)驗(yàn)，對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é)到了比較多的知識，包括使對一些matlab語句的掌握的更加熟練，完成一個算法必須要有一個整體的把握等等。3、通過本次課程設(shè)計(jì)，我對二叉樹和huffman編碼樹有了更深的了解，在做課程設(shè)計(jì)的過程中我掌握了二元huffman編碼樹的構(gòu)造方法，哈夫曼編碼是一種變長的編碼方案。它由最優(yōu)二叉樹既哈夫曼樹得到編碼，碼元內(nèi)容為到根結(jié)點(diǎn)的路徑中與父結(jié)點(diǎn)的左右子樹的標(biāo)識。所以哈夫曼在編碼在數(shù)字通信中有著重要的意義?？梢愿鶕?jù)信源符號的使用概率的高低來確定碼元的長度。既實(shí)現(xiàn)了信源的無失真地編碼，又使得編碼的效率最高。通過上表的對信源縮減合并過程，從而完成了對信源的霍夫曼編碼。三、實(shí)驗(yàn)步驟分為兩步，首先是碼樹形成過程：對信源概率進(jìn)行合并形成編碼碼樹。然后是碼樹回溯過程：在碼樹上分配編碼碼字并最終得到霍夫曼編碼。1、碼樹形成過程：將信源概率按照從小到大順序排序并建立相應(yīng)的位置索引。然后按上述規(guī)則進(jìn)行信源合并，再對信源進(jìn)行排序并建立新的位置索引，直到合并結(jié)束。在這一過程中每一次都把排序后的信源概率存入矩陣G中，位置索引存入矩陣Index中。這樣，由排序之后的概率矩陣G以及索引矩陣Index就可以恢復(fù)原概率矩陣？了，從而保證了回溯過程能夠進(jìn)行下去。2、碼樹回溯過程：在碼樹上分配編碼碼字并最終得到Huffman編碼。從索引矩陣M的末行開始回溯。(1)在Index的末行2元素位置填入0和1。(2)根據(jù)該行索引1位置指示，將索引1位置的編碼(‘1’)填入上一行的第一、第二元素位置，并在它們之后分別添加‘0’和‘