Matlab函數(shù)實(shí)現(xiàn)哈夫曼編碼算法

1、編寫Matlab函數(shù)實(shí)現(xiàn)哈夫曼編碼的算法一、 設(shè)計(jì)目的和意義在當(dāng)今信息化時(shí)代，數(shù)字信號充斥著各個(gè)角落。在數(shù)字信號的處理和傳輸中，信源編碼是首先遇到的問題，一個(gè)信源編碼的好壞優(yōu)劣直接影響到了后面的處理和傳輸。如何無失真地編碼，如何使編碼的效率最高，成為了大家研究的對象。哈夫曼編碼就是其中的一種，哈夫曼編碼是一種變長的編碼方案。它由最優(yōu)二叉樹既哈夫曼樹得到編碼，碼元內(nèi)容為到根結(jié)點(diǎn)的路徑中與父結(jié)點(diǎn)的左右子樹的標(biāo)識。所以哈夫曼在編碼在數(shù)字通信中有著重要的意義。可以根據(jù)信源符號的使用概率的高低來確定碼元的長度。既實(shí)現(xiàn)了信源的無失真地編碼，又使得編碼的效率最高。二、 設(shè)計(jì)原理哈夫曼編碼(Huffman C

2、oding)是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。uffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長 度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫作Huffman編碼。而哈夫曼編碼的第一步工作就是構(gòu)造哈夫曼樹。哈夫曼二叉樹的構(gòu)造方法原則如下，假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、wn，則哈夫曼樹的構(gòu)造規(guī)則為： (1) 將w1、w2、，wn看成是有n 棵樹的森林(每棵樹僅有一個(gè)結(jié)點(diǎn))； (2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)

3、點(diǎn)權(quán)值之和； (3)從森林中刪除選取的兩棵樹，并將新樹加入森林； (4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。具體過程如下圖1產(chǎn)所示：（例）圖1 哈夫曼樹構(gòu)建過程哈夫曼樹構(gòu)造成功后，就可以根據(jù)哈夫曼樹對信源符號進(jìn)行哈夫曼編碼。具體過程為先找到要編碼符號在哈夫曼樹中的位置，然后求該葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑，其中節(jié)點(diǎn)的左孩子路徑標(biāo)識為0，右孩子路徑標(biāo)識為1，最后的表示路徑的01編碼既為該符號的哈夫曼編碼?？梢灾?，一個(gè)符號在哈夫曼樹中的不同位置就有不同的編碼。而且，不同符號的編碼長度也可能不一樣，它由該結(jié)點(diǎn)到父結(jié)點(diǎn)的路徑長度決定，路徑越長編碼也就越長，這正是哈夫曼

4、編碼的優(yōu)勢和特點(diǎn)所在。它以各符號出現(xiàn)的概率大小將各符號的編碼區(qū)分開。例如對上例圖中“1”的編碼為“100”，“3”的編碼為“101”，“5”的編碼為“11”。對于一個(gè)信源消息的熵可以以下公式(1)求得：HX=-i=0nnp(xi)log2p(xi) (1)其中H(x)表示信源的總信息量，既為信源的熵。p(xi)為信源中一特定符號出現(xiàn)的概率。三、 詳細(xì)設(shè)計(jì)步驟1) 首先對設(shè)計(jì)題目進(jìn)行系統(tǒng)理論分析。由給定的8種可能符號的信源，各種符號發(fā)生的概率分別為：0.30、0.16、0.14、0.12、0.10、0.09、0.06、0.04。可以根據(jù)哈夫曼樹的構(gòu)造原理得出如下哈夫曼樹型結(jié)構(gòu)（圖2）:圖2 哈夫

5、曼樹其中每個(gè)結(jié)點(diǎn)中的上面的整數(shù)為結(jié)點(diǎn)有編號，下面的小數(shù)為該結(jié)點(diǎn)的權(quán)值，在這里指的各結(jié)點(diǎn)的概率。2) 由以是的哈夫曼樹圖，根據(jù)哈夫曼的編碼規(guī)則可求該8個(gè)輸出符號的順序?yàn)椋?.30,0.16,0.14,0.12,0.10,0.09,0.06,0.04對應(yīng)編碼輸出應(yīng)該為：1 0 1 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1，編碼長度為25。3) 由熵的計(jì)算公式可知：H(X)=-(0.3log20.3+0.16log20.16+0.14log20.14+0.12log20.12+0.1log20.1+0.09log20.09+0.06log20.06+0.

6、04log20.04)=2.78244) 哈夫曼樹在matlab中的構(gòu)造，在matlab中用tree(MN,s1,s2,s3)這個(gè)系統(tǒng)函數(shù)來構(gòu)造哈夫曼二叉樹。聲明一個(gè)tree(5,x)結(jié)構(gòu)的樹型結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)包括有5個(gè)變量存儲(chǔ)單元。其中tree(1,x)記錄該結(jié)點(diǎn)的編號；tree(2,x)記錄該結(jié)點(diǎn)的概率值；tree(3,x)記錄該結(jié)點(diǎn)的父結(jié)點(diǎn)編號；tree(4,x)記錄該結(jié)點(diǎn)是左結(jié)點(diǎn)還是右結(jié)點(diǎn)(其中左結(jié)點(diǎn)為“0”，右結(jié)點(diǎn)為“1”)；tree(5,x)記錄該結(jié)點(diǎn)是否為根結(jié)點(diǎn)標(biāo)志(該結(jié)點(diǎn)為根結(jié)點(diǎn)記為“1”，否則決為“0”)。由哈夫曼樹構(gòu)造原則，先選出所有結(jié)點(diǎn)中概率值最小的兩個(gè)結(jié)點(diǎn)，把這兩個(gè)結(jié)點(diǎn)組

7、合在一起形成一個(gè)新的二叉樹。新二叉樹的根結(jié)點(diǎn)為兩個(gè)子結(jié)點(diǎn)的概率這和，同時(shí)根據(jù)實(shí)際情況標(biāo)記結(jié)點(diǎn)的相關(guān)屬性(如左右子結(jié)點(diǎn)，是否為根結(jié)點(diǎn))，之后再將新的二叉樹跟剩下的結(jié)點(diǎn)集合在一起，再選出概率值最小的兩個(gè)結(jié)點(diǎn)，并重復(fù)以上的過程，直到把所有的結(jié)點(diǎn)都加到二叉樹中，開成一根哈夫曼二叉樹。在matlab編程實(shí)現(xiàn)中先編寫一個(gè)子函數(shù)用于找出所有結(jié)點(diǎn)中概率值最小的兩個(gè)結(jié)點(diǎn)，子函數(shù)如下：function l,r=findminval(tree)s=find(tree(5,:)=1);if size(s,2)<2 error('Error input!');endfirval=realmax;s

8、ecval=realmax;for i=s; if firval>tree(2,i) if secval>firval second=first;secval=firval; end first=i;firval=tree(2,i); elseif secval>tree(2,i) second=i;secval=tree(2,i); endendl=min(first,second);r=max(first,second);5) 然后再編寫代碼實(shí)現(xiàn)哈夫曼樹的構(gòu)建，通過循環(huán)調(diào)用tree()函數(shù)，并加以判斷完成哈夫曼樹的構(gòu)造，代碼如下：%哈夫曼樹結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)%pro為一概率向量

9、%tree(1,*)結(jié)點(diǎn)序號%tree(2,*)概率%tree(3,*)父結(jié)點(diǎn)序號%tree(4,*)左右標(biāo)志%tree(5,*)結(jié)點(diǎn)是否是根結(jié)點(diǎn)標(biāo)志%生成的哈夫曼樹n=size(pro,2);%得到字符個(gè)數(shù)tree=ones(5,2*n-1);%構(gòu)造樹數(shù)據(jù)結(jié)構(gòu)tree(1,:)=1:(2*n-1);%填充結(jié)點(diǎn)序號tree(5,(n+1):end)=0;%設(shè)置結(jié)點(diǎn)是否在集合tree(2,1:n)=pro;%設(shè)置概率for i=(n+1):(2*n-1);%循環(huán)控制 l,r=findminval(tree);%找到集合中兩個(gè)最小的值的序號 tree(2,i)=tree(2,l)+tree(2,r

10、);%得到父結(jié)點(diǎn)概率值 tree(5,i)=1;%設(shè)置新構(gòu)造結(jié)點(diǎn)在集合中 tree(3,l)=i;tree(3,r)=i;%設(shè)置父結(jié)點(diǎn)序號 tree(4,l)=0;tree(4,r)=1;%設(shè)置左右標(biāo)志 tree(5,l)=0;tree(5,r)=0;%設(shè)置不在集合中endHuffmanTree=tree;6) 調(diào)用循環(huán)計(jì)算信源的熵，代碼如下：Entropy=0;%初始化為0for j=1:n;%循環(huán)累加求信源的熵 Entropy=Entropy-pro(j)*log2(pro(j);end7) 由哈夫曼樹生成哈夫曼編碼，既哈夫曼樹的遍歷，同時(shí)統(tǒng)計(jì)編碼的長度，此處采用由下往上的遍歷方式，獲得路

11、徑編碼后再將編碼倒一次序，得到的編碼既為信源稱號的哈夫曼編碼，最后再將所有符號的編碼組合在一起，代碼如下：%由下至上完成哈夫曼編碼HuffmanCode=;%初始化定義Code=;SumCode=0;LastPoint=1;int z;for k=1:n;%循環(huán)完成n個(gè)符號的編碼 CodeNumber=1; m=k; while(tree(5,m)=1)%判斷是否已遍歷到根結(jié)點(diǎn) if tree(4,m)=0%判斷為左結(jié)點(diǎn)編碼為0 Code(CodeNumber)=0; CodeNumber=CodeNumber+1; elseif tree(4,m)=1%判斷為右結(jié)點(diǎn)編碼為1 Code(Cod

12、eNumber)=1; CodeNumber=CodeNumber+1; end m=tree(3,m);%指向父結(jié)點(diǎn) end CodeNumber=CodeNumber-1; SumCode=SumCode+CodeNumber;%累加計(jì)算編碼長度 for z=LastPoint:SumCode;%將n個(gè)符號的編碼組合到一起 HuffmanCode(z)=Code(CodeNumber); CodeNumber=CodeNumber-1; z=z+1; end LastPoint=z;end8) 最后將以上的代碼整合到一個(gè)子函數(shù)中，并設(shè)置函數(shù)的傳入?yún)?shù)為信源符號的概率向量，同時(shí)使函數(shù)返回哈夫

13、曼樹，哈夫曼編碼，編碼長度以及信源的熵，函數(shù)頭如下：function HuffmanTree,HuffmanCode,SumCode,Entropy = Huffman(pro)四、 設(shè)計(jì)結(jié)果及分析完成編寫設(shè)計(jì)后，在matlab中運(yùn)行并驗(yàn)證結(jié)果，首先輸入概率向量：>> pro=0.30,0.16,0.14,0.12,0.10,0.09,0.06,0.04;再調(diào)用編寫的Huffman函數(shù)：>> HuffmanTree,HuffmanCode,SumCode,Entropy = Huffman(pro)回車即可得到執(zhí)行的結(jié)果：（見附圖3）所得的結(jié)果與實(shí)際預(yù)測的理論結(jié)果一致無誤。五、 體會(huì)通過本次數(shù)字通信課程的設(shè)計(jì)，深刻體會(huì)了數(shù)字編碼的全過程。認(rèn)識到了無失真和高效率編碼在數(shù)字通信中的重