二元霍夫曼編碼-信息論與編碼實驗報告.doc

計算機與信息工程學(xué)院綜合性實驗報告專業(yè)：通信工程 年級/班級：2011級 20132014學(xué)年第一學(xué)期課程名稱信息論與編碼指導(dǎo)教師劉艷芳本組成員學(xué)號姓名實驗地點計科樓111實驗時間周五5-6節(jié)項目名稱二元霍夫曼編碼實驗類型綜合性一、 實驗?zāi)康母鶕?jù)霍夫曼編碼的原理，用MATLAB設(shè)計進行霍夫曼編碼的程序，并得出正確的結(jié)果。二、 實驗儀器或設(shè)備1、一臺計算機。2、MATLAB r2013a。三、 二元霍夫曼編碼原理1、將信源消息符號按其出現(xiàn)的概率大小依次排列，p1p2pq2、取兩個概率最小的字母分別配以0和1兩個碼元，并將這兩個概率相加作為一個新字母的概率，從而得到只包含q-1個符號的新信源S1。3、對重排后的縮減信源S1重新以遞減次序排序，兩個概率最小符號重復(fù)步驟(2)的過程。4、不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止。5、從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。四、 霍夫曼編碼實現(xiàn)程序function outnum=lml_huffman(a)%主程序，輸入一組概率，輸出此組概率的霍夫曼編碼%a：一組概率值，如a=0.2 0.3 0.1 0.4等%outnum：輸出的霍夫曼碼，以cell中的字符數(shù)組表示if sum(a)=1 warning(輸入概率之和不為“1”，但程序仍將繼續(xù)運行)endcho,sequ,i,l=probality(a);global lmlcode %用于輸出霍夫曼碼，定義為cell型global cellnum %用于編碼的累加計算cellnum=1;lmlcode=cell(l,1);j=1; %第一部分add_num=char;l_add=addnum(add_num,i,j,l);output,m=disgress(sequ,i,j,l,l_add);dealnum(output,m); %在全局變量中輸出霍夫曼碼j=2; %第二部分l_add=addnum(add_num,i,j,l);output,n=disgress(sequ,i,j,l,l_add);dealnum(output,n);outnum=comset(lmlcode,cho(1,:);%將概率和編碼進行關(guān)聯(lián)function output=addnum(input,i,j,l)%對概率矩陣中每一行最后兩個不為0的數(shù)進行編碼，即在某個編碼后添加0,1或空%輸出：% input：輸入的某個未完成的編碼% (i,j):當前檢索目標在sequ矩陣中的位置% l:sequ矩陣的列數(shù)%PS: sequ矩陣在此函數(shù)中未用到%PS：此函數(shù)為編碼第一步if j=(l-i) output=input 0;else if j=(l-i+1) output=input 1; else output=input; endendfunction ecode=comset(code,pro)%將概率和編碼進行關(guān)聯(lián)%code：已編成的霍夫曼碼%pro：輸入的一組概率%ecode：最終完成的碼l=length(code);ecode=cell(l,2);for i=1:l lang(i)=length(codei);enda,b=sort(lang);for i=1:l ecodei,1=codeb(i); ecodei,2=pro(i);endfunction final,a=dealnum(imput,m)%整理并在全局變量中輸出已完成的霍夫曼碼%輸入： imput：程序運算后的生成cell型矩陣% m：標識數(shù)%輸出： final：整理后的霍夫曼碼% a：標識數(shù)global lmlcodeglobal cellnumif m=1 lmlcodecellnum=imput; cellnum=cellnum+1; final=; a=;else if m=2 final1,a1=dealnum(imput1,1,imput1,2); final2,a2=dealnum(imput2,1,imput2,2); final3,a3=dealnum(final1,a1); final4,a4=dealnum(final2,a2); final=final3 final4; a=a3 a4; else final=imput; a=m; endendfunction outnum,p=findsumother(sequ,i,j,l,add_num)%當前檢索目標在sequ(i,j)處為非1時的處理程序，即跳轉(zhuǎn)到下一級進行整理%輸入： sequ:概率轉(zhuǎn)移矩陣% (i,j):當前檢索目標在sequ矩陣中的位置% l:sequ矩陣的列數(shù)% add_num：當前進行的編碼%輸出：（與disgress類同）% outnum：進行霍夫曼編碼，用cell型表示% p：標識數(shù)j=l-i+2-sequ(i,j);i=i-1;add_num1=addnum(add_num,i,j,l);outnum,p=disgress(sequ,i,j,l,add_num1);function outnum1,outnum2,p,q=findsumis1(sequ,i,j,l,add_num)%當前檢索目標在sequ(i,j)處為1時的處理程序，%即對下一級的最小兩概率進行求和移位編碼整理%輸入： sequ:概率轉(zhuǎn)移% (i,j):當前檢索目標在sequ矩陣中的位置% l:sequ矩陣的列數(shù)% add_num：當前進行的編碼%輸出：（與disgress類同）% outnum1&outnum2：進行霍夫曼編碼，用cell型表示% p&q：標識數(shù)i=i-1;j1=l-i;j2=l-i+1;add_num1=addnum(add_num,i,j1,l);outnum1,p=disgress(sequ,i,j1,l,add_num1);add_num2=addnum(add_num,i,j2,l);outnum2,q=disgress(sequ,i,j2,l,add_num2);function output,m=disgress(sequ,i,j,l,add_num)%當前檢索目標，累加數(shù)，輸出下一級霍夫曼碼及其個數(shù)，此函數(shù)被調(diào)用次數(shù)最多%輸入：sequ：概率轉(zhuǎn)移矩陣% (i,j)：當前檢索目標在sequ矩陣中的位置% l：sequ矩陣的列數(shù)% add_num：當前進行的編碼%輸出：output：進行霍夫曼編碼，用cell型表示% m：標識數(shù)%PS：此函數(shù)為編碼第二步if i=1 if sequ(i,j)=1 output1,output2,p,q=findsumis1(sequ,i,j,l,add_num); output=cell(2); output1,1=output1; output1,2=p; output2,1=output2; output2,2=q; m=2; else if sequ(i,j)=1 output1,p=findsumother(sequ,i,j,l,add_num); output=output1; m=p; end endelse output=add_num; m=1;end五、 實驗程序?qū)崿F(xiàn)方法演示若在command window中輸入的概率數(shù)組為p=0.1 0.15 0.20 0.25 0.30使用子函數(shù)output,sequ,i,j=probality(p)對此組概率進行預(yù)處理，處理結(jié)果如下圖所示： 0.3000 0.3000 0.4500 0.55000.2500 0.2500 0.3000 0.45000.2000 0.2500 0.2500 0.1500 0.2000 0.1000 output圖5.1 概率數(shù)據(jù)處理過程簡圖5 4 1 14 3 3 23 1 2 2 2 1 sequ圖5.2 對圖1中數(shù)據(jù)的轉(zhuǎn)移方式標示圖圖2標明了對圖1中各數(shù)據(jù)的位置轉(zhuǎn)移過程。圖1中每一列最后兩個數(shù)據(jù)標為1，其他數(shù)據(jù)從下到上依次標為2、3、4.如第一列最后兩個數(shù)據(jù)標為1，則其上依次為2、3、4。故在第二列中sequ(2,3)=1的含義是：output(2,3)=0.25為第一列中標為1的數(shù)據(jù)轉(zhuǎn)移而來；sequ(2,2)=3的含義是：output(2,2)=0.25為第一列中標為3的數(shù)據(jù)轉(zhuǎn)移而來；在第三列中sequ(2,3)=3的含義是：output(2,3)=0.3為第二列中標為3的數(shù)據(jù)轉(zhuǎn)移而來，等等。依據(jù)矩陣output及sequ可以得到霍夫曼編碼的碼樹圖如下：1111010100010000.550.30.250.30.250.30.250.450.450.10.20.250.20.15010010110011圖5.3 特定概率數(shù)組的編碼碼樹六、 結(jié)果分析與總結(jié)（1）實驗結(jié)果分析1、在command window中輸入:p=0.1 0.15 0.20 0.25 0.30,生成數(shù)組p2、之后在command window中輸入:a=lml_huffman(p),輸出結(jié)果為：a = 00 0.3000 01 0.2500 11 0.2000 100 0.1500 101 0.1000其中outnum為cell型，第一列為字符型，輸出的是霍夫曼碼，第二列為輸入的概率數(shù)組，與第一列中的霍夫曼碼相對應(yīng)。將以上輸出結(jié)果在下表中統(tǒng)計。表6.1 編碼分析表信源消息符號ai符號概率p(ai)累加概率Pi=-log p(ai)碼字長度li碼字a10.301.