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

《霍夫曼編碼的matlab實(shí)現(xiàn)(信源編碼實(shí)驗(yàn))》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

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

3、0.410.200.610.401A(1)0W5=1100S50.10通過上表的對信源縮減合并過程，從而完成了對信源的霍夫曼編碼。三、實(shí)驗(yàn)步驟分為兩步，首先是碼樹形成過程：對信源概率進(jìn)行合并形成編碼碼樹。然后是碼樹回溯過程：在碼樹上分配編碼碼字并最終得到霍夫曼編碼。1、碼樹形成過程：將信源概率按照從小到大順序排序并建立相應(yīng)的位置索引。然后按上述規(guī)則進(jìn)行信源合并，再對信源進(jìn)行排序并建立新的位置索引，直到合并結(jié)束。在這一過程中每一次都把排序后的信源概率存入矩陣G中，位置索引存入矩陣Index中。這樣，由排序之后的概率矩陣?G以及索引矩陣Index就可以恢復(fù)原概率矩陣P了，從而保證了回溯過程能夠進(jìn)行

4、下去。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)，直到計算至Index的首行為止。四、程序代碼：%取得信源概率矩陣,并進(jìn)行合法性判斷clear;P=input('請輸入信源概率向量P=');N=length(P);forcompone

5、nt=1:1:Nif(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];%將Q中概率最小的兩個元素合并，元素不足的地方補(bǔ)1end%根據(jù)以上建立的In

6、dex矩陣，進(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*(fi

7、nd(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);%將G后一行中索引為1的編碼碼字填入到當(dāng)前行的第二個編碼位置Char