二元霍夫曼編碼-信息論與編碼實(shí)驗(yàn)報(bào)告.doc

計(jì)算機(jī)與信息工程學(xué)院綜合性實(shí)驗(yàn)報(bào)告專業(yè)：通信工程 年級(jí)/班級(jí)：2011級(jí) 20132014學(xué)年第一學(xué)期課程名稱信息論與編碼指導(dǎo)教師劉艷芳本組成員學(xué)號(hào)姓名實(shí)驗(yàn)地點(diǎn)計(jì)科樓111實(shí)驗(yàn)時(shí)間周五5-6節(jié)項(xiàng)目名稱二元霍夫曼編碼實(shí)驗(yàn)類型綜合性一、 實(shí)驗(yàn)?zāi)康母鶕?jù)霍夫曼編碼的原理，用MATLAB設(shè)計(jì)進(jìn)行霍夫曼編碼的程序，并得出正確的結(jié)果。二、 實(shí)驗(yàn)儀器或設(shè)備1、一臺(tái)計(jì)算機(jī)。2、MATLAB r2013a。三、 二元霍夫曼編碼原理1、將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列，p1p2pq2、取兩個(gè)概率最小的字母分別配以0和1兩個(gè)碼元，并將這兩個(gè)概率相加作為一個(gè)新字母的概率，從而得到只包含q-1個(gè)符號(hào)的新信源S1。3、對(duì)重排后的縮減信源S1重新以遞減次序排序，兩個(gè)概率最小符號(hào)重復(fù)步驟(2)的過(guò)程。4、不斷繼續(xù)上述過(guò)程，直到最后兩個(gè)符號(hào)配以0和1為止。5、從最后一級(jí)開(kāi)始，向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列，即相應(yīng)的碼字。四、 霍夫曼編碼實(shí)現(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ù)運(yùn)行)endcho,sequ,i,l=probality(a);global lmlcode %用于輸出霍夫曼碼，定義為cell型global cellnum %用于編碼的累加計(jì)算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,:);%將概率和編碼進(jìn)行關(guān)聯(lián)function output=addnum(input,i,j,l)%對(duì)概率矩陣中每一行最后兩個(gè)不為0的數(shù)進(jìn)行編碼，即在某個(gè)編碼后添加0,1或空%輸出：% input：輸入的某個(gè)未完成的編碼% (i,j):當(dāng)前檢索目標(biāo)在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)%將概率和編碼進(jìn)行關(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：程序運(yùn)算后的生成cell型矩陣% m：標(biāo)識(shí)數(shù)%輸出： final：整理后的霍夫曼碼% a：標(biāo)識(shí)數(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)%當(dāng)前檢索目標(biāo)在sequ(i,j)處為非1時(shí)的處理程序，即跳轉(zhuǎn)到下一級(jí)進(jìn)行整理%輸入： sequ:概率轉(zhuǎn)移矩陣% (i,j):當(dāng)前檢索目標(biāo)在sequ矩陣中的位置% l:sequ矩陣的列數(shù)% add_num：當(dāng)前進(jìn)行的編碼%輸出：（與disgress類同）% outnum：進(jìn)行霍夫曼編碼，用cell型表示% p：標(biāo)識(shí)數(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)%當(dāng)前檢索目標(biāo)在sequ(i,j)處為1時(shí)的處理程序，%即對(duì)下一級(jí)的最小兩概率進(jìn)行求和移位編碼整理%輸入： sequ:概率轉(zhuǎn)移% (i,j):當(dāng)前檢索目標(biāo)在sequ矩陣中的位置% l:sequ矩陣的列數(shù)% add_num：當(dāng)前進(jìn)行的編碼%輸出：（與disgress類同）% outnum1&outnum2：進(jìn)行霍夫曼編碼，用cell型表示% p&q：標(biāo)識(shí)數(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)%當(dāng)前檢索目標(biāo)，累加數(shù)，輸出下一級(jí)霍夫曼碼及其個(gè)數(shù)，此函數(shù)被調(diào)用次數(shù)最多%輸入：sequ：概率轉(zhuǎn)移矩陣% (i,j)：當(dāng)前檢索目標(biāo)在sequ矩陣中的位置% l：sequ矩陣的列數(shù)% add_num：當(dāng)前進(jìn)行的編碼%輸出：output：進(jìn)行霍夫曼編碼，用cell型表示% m：標(biāo)識(shí)數(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五、 實(shí)驗(yàn)程序?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)對(duì)此組概率進(jìn)行預(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ù)處理過(guò)程簡(jiǎn)圖5 4 1 14 3 3 23 1 2 2 2 1 sequ圖5.2 對(duì)圖1中數(shù)據(jù)的轉(zhuǎn)移方式標(biāo)示圖圖2標(biāo)明了對(duì)圖1中各數(shù)據(jù)的位置轉(zhuǎn)移過(guò)程。圖1中每一列最后兩個(gè)數(shù)據(jù)標(biāo)為1，其他數(shù)據(jù)從下到上依次標(biāo)為2、3、4.如第一列最后兩個(gè)數(shù)據(jù)標(biāo)為1，則其上依次為2、3、4。故在第二列中sequ(2,3)=1的含義是：output(2,3)=0.25為第一列中標(biāo)為1的數(shù)據(jù)轉(zhuǎn)移而來(lái)；sequ(2,2)=3的含義是：output(2,2)=0.25為第一列中標(biāo)為3的數(shù)據(jù)轉(zhuǎn)移而來(lái)；在第三列中sequ(2,3)=3的含義是：output(2,3)=0.3為第二列中標(biāo)為3的數(shù)據(jù)轉(zhuǎn)移而來(lái)，等等。依據(jù)矩陣output及sequ可以得到霍夫曼編碼的碼樹(shù)圖如下：1111010100010000.550.30.250.30.250.30.250.450.450.10.20.250.20.15010010110011圖5.3 特定概率數(shù)組的編碼碼樹(shù)六、 結(jié)果分析與總結(jié)（1）實(shí)驗(yàn)結(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ù)組，與第一列中的霍夫曼碼相對(duì)應(yīng)。將以上輸出結(jié)果在下表中統(tǒng)計(jì)。表6.1 編碼分析表信源消息符號(hào)ai符號(hào)概率p(ai)累加概率Pi=-log p(ai)碼字長(zhǎng)度li碼字a10.301.