信息論綜合性實(shí)驗(yàn)報(bào)告 Huffman編碼及譯碼 代碼

Xx大學(xué)yy學(xué)院

綜合性設(shè)計(jì)性實(shí)驗(yàn)報(bào)告專業(yè)班級(jí)：學(xué)號(hào)：姓名：實(shí)驗(yàn)所屬課程：信息論與編碼技術(shù)實(shí)驗(yàn)室（中心）:信息科學(xué)與工程學(xué)院軟件中心指導(dǎo)教師：實(shí)驗(yàn)完成時(shí)間：2012年12月9日一、設(shè)計(jì)題目：Huffman編碼及譯碼二、實(shí)驗(yàn)內(nèi)容及要求：＜一＞實(shí)驗(yàn)內(nèi)容：對(duì)所給的字符串進(jìn)行huffman的編譯碼；譯碼對(duì)應(yīng)原始序列，在將編碼進(jìn)行移位操作時(shí)，再進(jìn)行譯碼輸出，得出誤碼率。＜二＞實(shí)驗(yàn)要求：自己設(shè)計(jì)一段信源序列，利用Huffman編碼對(duì)其進(jìn)行編碼，然后利用相應(yīng)的譯方法進(jìn)行譯碼，同時(shí)考察譯碼錯(cuò)誤對(duì)后續(xù)序列帶來的影響。三、實(shí)驗(yàn)過程（詳細(xì)設(shè)計(jì)）：＜一＞huffman編碼原理：Huffman編碼是一種緊致編碼，但編碼序列的碼并非是唯一的。它是根據(jù)源數(shù)據(jù)各信號(hào)發(fā)生的概率進(jìn)行編碼，在源數(shù)據(jù)中出現(xiàn)的概率越大的信號(hào)，分配的碼字越短；出現(xiàn)概率越小的信號(hào)，其碼字越長(zhǎng)，從而達(dá)到用盡可能少的碼字表示源數(shù)據(jù)的目的。Huffman編碼的步驟如下：設(shè)信源X有m個(gè)符號(hào)（消息），信源概率分布如下：X』氣,七，…,門〔P12，…,P〕（1）把信源X中的消息按概率從大到小的”順序排列；（2）把最后兩個(gè)出現(xiàn)概率最小的消息合并成一個(gè)消息，從而使信源的消息數(shù)減少，并同時(shí)再按信源符號(hào)（消息）出現(xiàn)的概率從大到小排列；（3）重復(fù)上述2個(gè)步驟，直到信源最后為一個(gè)序列只有一個(gè)1；（4）將被整合的消息分別賦予1和0,并對(duì)最后的兩個(gè)消息也相應(yīng)地賦予1和0._（5）通過以上步驟即可完成編碼操作。＜一＞huffman譯碼原理：通過在剛開始生成的隨機(jī)編碼序列，得到列出的01序列與源字符串一一對(duì)應(yīng)，就完成了譯碼。而對(duì)錯(cuò)位后的編碼序列，我只是只錯(cuò)位了前兩個(gè)進(jìn)行譯碼，效果不是很明虹＜三＞算法設(shè)計(jì)：1、編碼部分：(1)主函數(shù)主要用于調(diào)用前面所編寫的各個(gè)函數(shù)模塊，按照主函數(shù)(主函數(shù)代碼如下)所列出來的調(diào)用順序，進(jìn)行一一敘述。function[]=huffmanmain()disp('請(qǐng)輸入待編碼序列');s=input('','s');%調(diào)用概率統(tǒng)計(jì)函數(shù)，輸出各碼元的概率分布矩陣；pro=getpro(s);%調(diào)用生成huffmantree函數(shù)，輸出基本樹，及完整huffmantree；[HuffmanTree,pro2]=huffmantree(pro);%調(diào)用編碼函數(shù)，輸出碼表，編碼序歹。平均碼長(zhǎng)，信息熵，編碼效率；[Codenumber,huffmantable,Code2]=huffmanencode221(HuffmanTree,pro2,s);%調(diào)用譯碼函數(shù)，輸出譯碼序列以及誤碼率；decodenumber=huffmandecode221(Codenumber,huffmantable,Code2,pro2,s);%調(diào)用函數(shù)，使編碼序列中的01錯(cuò)位Codenumber1=yiweicodenumber(Codenumber);%調(diào)用譯碼函數(shù)，對(duì)錯(cuò)位后的編碼序列進(jìn)行譯碼decodenumber=huffmandecode(Codenumber1,huffmantable,Code2,pro2,s);(2)通過編寫函數(shù)pro=getpro(s)函數(shù)來完成對(duì)字符串中的各字符的統(tǒng)計(jì)，并列出其概率分布矩陣，返回pro矩陣，其主要代碼如下：foi=1:b%進(jìn)行概率計(jì)算；forj=1:aifS(i)==s(j)c(i)=c(i)+1;elsecontinue;end;end;en;dpro=c./a;(3)由Huffman編碼要求，得到的概率分布矩陣要按照從大到小得順序來排列，所以需要編寫函數(shù)來得到順序排列的概率分布矩陣。我們需要從pro(1,:)中找到兩個(gè)最小的概率值，所以需要編寫找出兩個(gè)最小值的函數(shù)[min1,min2]=getmin(tree),其中tree是在進(jìn)行Huffman編碼過程中產(chǎn)生的Huffman樹(包含pro信息，具體下面介紹)，并且在min1與min2中若兩者值相等，則在pro中概率序號(hào)在前的概率值賦予min1，概率序號(hào)在后的概率值賦予min2,詳細(xì)說明見其下面的代碼注釋；此部分函數(shù)代碼主要如下：LL=length(pro1);構(gòu)建基礎(chǔ)二叉樹[p1,p2]=sort(pro1,'descend');pro2=zeros(2,LL);pro2(1,:)=p1;pro2(2,:)=p2;n0=size(pro2,2);n1=ceil(log2(n0));%二叉樹的深度；n=LL;tree=ones(6,2*n-1);%建立其6*2*n-1的單位1矩陣，用以存儲(chǔ)二叉樹中各個(gè)結(jié)點(diǎn)，父節(jié)點(diǎn)，以及各個(gè)結(jié)點(diǎn)的編號(hào)；tree(1,:)=1:(2*n-1);%用以編號(hào)并存儲(chǔ)二叉樹中的結(jié)點(diǎn)；tree(5,(n+1):end)=0;%用以存放其根結(jié)點(diǎn)；tree(2,1:n)=pro2(1,:);%用以存放概率分布;tree(6,1:n)=pro2(2,:);%用以存放每個(gè)概率對(duì)應(yīng)的符號(hào)的下標(biāo)；tree(6,n+1:end)=0;disp('基本樹形式：')；disp(tree);%顯示構(gòu)建其的基本樹形式；%對(duì)概率分布矩陣進(jìn)行運(yùn)算，每次進(jìn)行最小兩個(gè)值相加，其和賦予其中一個(gè)，另外一個(gè)置1，重復(fù)操作，%將其每一次輸出的結(jié)果存于s1矩陣中，至最后兩個(gè)概率和為1結(jié)束；s1=ones(n-1,2*n-1);s1(1,:)=sort(tree(2,:));fori=2:ns1(i,:)=[s1(i-1,1)+s1(i-1,2),1,s1(iT,3:2*nT)];s1(i,:)=sort(s1(i,:));end;%對(duì)基礎(chǔ)二叉樹進(jìn)行操作，完整構(gòu)造；m1=0;m2=0;s2=tree(2,:);%將tree(2,:)中的概率分布賦予s2矩陣中，在不改變tree(2,:)中概率分布，方便對(duì)其操作；fori=(n+1):(2*n-1);min1=find(s2==s1(i-n,1));%從tree(2，：)中找對(duì)應(yīng)于$1矩陣中每一行的最小的兩個(gè)概率值的下標(biāo);%為避免tree(2,:)中出現(xiàn)兩個(gè)相同的最小值，將進(jìn)行如下判斷并操作；iflength(min1)==1m1=min1;min2=find(tree(2,:)==s1(i-n,2));m2=min2(1);elsem1=min1(1,1);m2=min1(1,2);end;(4)在以上的代碼中，主要用到了二叉樹的構(gòu)建，其詳細(xì)說明如下：通過tree=ones(6,2*n-1)語句來構(gòu)造二叉樹。聲明一個(gè)tree(6,x)結(jié)構(gòu)的樹型結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)包括有6個(gè)變量存儲(chǔ)單元。其中tree(1,x)記錄該結(jié)點(diǎn)的編號(hào)；tree(2,x)記錄該結(jié)點(diǎn)的概率值；tree(3,x)記錄該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)；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”)；tree(6,x)記錄該結(jié)點(diǎn)的字符，x為pro中源字符經(jīng)過篩選后的下標(biāo)數(shù)，其余值賦為零。如上代碼所示，基本樹的構(gòu)建以及另建立一個(gè)與之大小相同的矩陣，存儲(chǔ)每一次運(yùn)算后的所找出的最小的兩個(gè)概率值。然后對(duì)建立好的huffman樹進(jìn)行遍歷，遍歷的時(shí)候從tree(6，：)中第一值開始，逐一的把tree(2,:)中的概率值所對(duì)應(yīng)的編碼一一找出來，賦予huffmantable矩陣中然后逐一輸出；以下是主要代碼部分：%遍歷二叉樹，生成碼表huffmantable;fori=1:len1;%循環(huán)完成len1個(gè)符號(hào)的編碼；k=pro(2,i);key=1;m=find(HuffmanTree(6,1:len1)==k);while(HuffmanTree(5,m)~=1)%判斷是否遍歷至U根結(jié)點(diǎn)；Code(key)=HuffmanTree(4,m);key=key+1;m=HuffmanTree(3,m);%指向父節(jié)點(diǎn)；endlc=length(Code);huffmantable(i,1:lc)=fliplr(Code);%將Code矩陣中的編碼左右翻轉(zhuǎn)，完成倒序排列；Code2=[Code2,lc];%將各個(gè)碼元的編碼長(zhǎng)度賦予矩陣Code2;enddisp('碼表如下：');%顯示碼表，即只輸出矩陣huffmantable中非-1的部分；Code4=[];fori=1:len1%顯示其碼表；disp(a1(pro(2,i)));flag=1;while(huffmantable(i,flag)~=-1)Code4(flag)=huffmantable(i,flag);flag=flag+1;end;Code4,disp'碼長(zhǎng)='),Code2(i)end;(5)通過以上生成的碼表，然后遍歷源字符串與unique之后的字符串，找出其下標(biāo)并對(duì)應(yīng)輸出碼表中對(duì)應(yīng)的編碼序列，這樣源字符串的編碼就完成了，以下是編碼部分的主要代碼：%%通過碼元與待編碼的序列一一比較，輸出huffmantable中對(duì)應(yīng)的編碼；Codenumber=[];fori=1:len2forj=1:len1ifa1(j)==a2(i)v=find(HuffmanTree(6,:)==j);flag=1;while(huffmantable(v,flag)~=-1)Code1(flag)=huffmantable(v,flag);flag=flag+1;Sumnumber=Sumnumber+1;end;Codenumber(Sumnumber-flag+2:Sumnumber)=[Code1(1:flag-1)];end;2、譯碼部分：對(duì)于譯碼部分所用到的部分主要是編碼時(shí)生成的碼表以及huffmantree，在進(jìn)行編碼的時(shí)候，通過篩選后的源字符串的字符序列的下標(biāo)，與碼表中的每

行相對(duì)應(yīng)的原則，遍歷編碼序列；在遍歷的時(shí)候，通過碼表中各行的碼長(zhǎng)，控制遍歷的長(zhǎng)度，與每行中的碼表進(jìn)行比較，輸出相對(duì)應(yīng)的字符，即完成了譯碼。以下是主要代碼部分：while(flag~=-1)fori=1:lxk=Code2(i);while(ZF(1:k)==huffmantable(i,1:k))decodenumber=[decodenumber,mm(i)];ZF=ZF(k+1:end);endendflag=ZF(1);end3、錯(cuò)位后重新譯碼：通過函數(shù)調(diào)用，改變編碼序列中的前兩個(gè)值，即是0的變?yōu)?，是1的變?yōu)?，然后再進(jìn)行重新譯碼輸出，觀察其變化。其主要代碼如下：fori=1:2ifCodenumber(i)==0Codenm=1;elseCodenumber(i)=0;end;end;Codenumber1=Codenumber;disp('錯(cuò)位后的編碼序列：')；Codenumber1四、測(cè)試及設(shè)計(jì)分析：＜一＞實(shí)驗(yàn)測(cè)試結(jié)果：實(shí)驗(yàn)的測(cè)試結(jié)果如下圖所示，在CommandWindow中輸入調(diào)用后王函數(shù)huffmanmain()，在提示說明下輸入字符串：CommandWindow-+■□*「NewtoMATLAB?WatchthisWideesee口號(hào)mo%orreadGetting請(qǐng)輸入待編碼序列skdshsfhsdjdsjksdfhjks0.18750.06250.12500.12500.12500.3750基本樹形式：Columns1through71.00002.GOOD3.00004.00005.00006.00007.00000.37500.18750.12500.12500.12500.06251.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00001.00000

CommandWindow-+■,'.i'1NewtoMATLAB?WatchthisWidgseeE）輯mcis,orreadGettingStarted,哈夫曼樹如下：Columns1through71.00002.00003.00004.00005.00006.00007.00000.37500.18750.12500.12500.12500.06250.187510.00009.00007.00008.00008.00007.00009.000001.0000Q1.000001.0000000000006.00001.00003.00004.00005.00002.00000Colijjnns8through11碼長(zhǎng)二ans=2Code4二g1ans=Coded=01L碼長(zhǎng)二ans=碼長(zhǎng)二3113=Code4二101Coluimts12through22000101Columiis23through33110111Columiis34through39101000編碼效率：N二0.9676譯碼序列如下：skdshsfhsdjdsjks原始序列如下：skdshsfhsdjdsjks錯(cuò)位后的編碼序列WCodeniimber1=Columns1through11000101Columns12through2200010110000100011001010000ColiJjms34through39101000譯碼序列如下；1skdshsfhsdjdsjks原始序列如下；skdshsfhsdjdsjks＜二＞實(shí)驗(yàn)分析：通過上述圖示可以得出其碼表，各碼元的碼長(zhǎng)，平均碼長(zhǎng)，信息熵，編碼效率，譯碼，以及錯(cuò)位后的編碼和再一次的譯碼輸出結(jié)果。而且，在設(shè)計(jì)編碼算法的時(shí)候，參考了其二叉樹的建立，遍歷算法；編寫函數(shù)模塊，譯碼的時(shí)候，參考了同學(xué)的算法，完成了編碼。五、思路及附碼：＜一＞實(shí)驗(yàn)思路：在設(shè)計(jì)算法的時(shí)候，運(yùn)用二叉樹的構(gòu)建、遍歷，再結(jié)合所學(xué)的MATLAB編程知識(shí)來進(jìn)行編碼。在整個(gè)編寫的過程中，首先要清楚其流程，然后通過對(duì)其逐一的編寫函數(shù)模塊，逐一的調(diào)試，最后整合到一個(gè)主函數(shù)調(diào)用中，而在整個(gè)編碼過程中，最大的困難就是對(duì)其進(jìn)行遍歷的時(shí)候，清楚其原理是關(guān)鍵。＜二＞實(shí)驗(yàn)的附代碼：主函數(shù)調(diào)用function[]=huffman221()disp('請(qǐng)輸入待編碼序列');s=input('','s');%調(diào)用概率統(tǒng)計(jì)函數(shù)，輸出各碼元的概率分布矩陣；pro=getpro221(s);%調(diào)用生成huffmantree函數(shù)，輸出基本樹，及完整huffmantree；[HuffmanTree,pro2]=huffmantree221(pro);%調(diào)用編碼函數(shù)，輸出碼表，編碼序列，平均碼長(zhǎng)，信息熵，編碼效率；[Codenumber,huffmantable,Code2]=huffmanencode221(HuffmanTree,pro2,s);%調(diào)用譯碼函數(shù)，輸出譯碼序列以及誤碼率；decodenumber=huffmandecode221(Codenumber,huffmantable,Code2,pro2,s);%通過構(gòu)建二叉樹，遍歷huffman樹，從而得到其對(duì)應(yīng)的碼表；%pro1：各碼元概率分布矩陣，pro2:各碼元按倒序排列后的順序以及對(duì)應(yīng)之前的位置；編碼生成概率分布矩陣%完成對(duì)輸入的序列進(jìn)行各個(gè)碼元的概率統(tǒng)計(jì)；%s:待編碼序列，S：所含的碼元序列functionpro=getpro221(s)pro=[];a=length(s);S=unique(s);b=length(S);c=zeros(1,b);%用以存放個(gè)序列中各個(gè)碼元的個(gè)數(shù)；%進(jìn)行概率計(jì)算；fori=1:bforj=1:aifS(i)==s(j)c(i)=c(i)+1;elsecontinue;end;end;end;pro=c./a;disp(S);disp(pro);構(gòu)建huffmantreefunction[HuffmanTree,pro2]=huffmantree221(pro1%構(gòu)建基礎(chǔ)二叉樹LL=length(pro1);[p1,p2]=sort(pro1,'descend');pro2=zeros(2,LL);pro2(1,:)=p1;pro2(2,:)=p2;n0=size(pro2,2);n1=ceil(log2(n0));%二叉樹的深度；n=LL;tree=ones(6,2*n-1);%建立其6*2*n-1的單位1矩陣，用以存儲(chǔ)二叉樹中各個(gè)結(jié)點(diǎn)，父節(jié)點(diǎn)，以及各個(gè)結(jié)點(diǎn)的編號(hào)；tree(1,:)=1:(2*n-1);%用以編號(hào)并存儲(chǔ)二叉樹中的結(jié)點(diǎn)；tree(5,(n+1):end)=0;%用以存放其根結(jié)點(diǎn)；tree(2,1:n)=pro2(1,:);%用以存放概率分布；tree(6,1:n)=pro2(2,:);%用以存放每個(gè)概率對(duì)應(yīng)的符號(hào)的下標(biāo)；tree(6,n+1:end)=0;disp('基本樹形式：')；disp(tree);%顯示構(gòu)建其的基本樹形式；%對(duì)概率分布矩陣進(jìn)行運(yùn)算，每次進(jìn)行最小兩個(gè)值相加，其和賦予其中一個(gè)，另外一個(gè)置1，重復(fù)操作，%將其每一次輸出的結(jié)果存于s1矩陣中，至最后兩個(gè)概率和為1結(jié)束；s1=ones(n-1,2*n-1);s1(1,:)=sort(tree(2,:));fori=2:ns1(i,:)=[s1(i-1,1)+s1(i-1,2),1,s1(i-1,3:2*n-1)];s1(i,:)=sort(s1(i,:));end;%對(duì)基礎(chǔ)二叉樹進(jìn)行操作，完整構(gòu)造；m1=0;m2=0;s2=tree(2,:);%將tree(2,:)中的概率分布賦予s2矩陣中，在不改變tree(2,:)中概率分布，方便對(duì)其操作；fori=(n+1):(2*n-1);min1=find(s2==s1(i-n,1));%從tree(2，：)中找對(duì)應(yīng)于s1矩陣中每一行的最小的兩個(gè)概率值的下標(biāo);%為避免tree(2,:)中出現(xiàn)兩個(gè)相同的最小值，將進(jìn)行如下判斷并操作；iflength(min1)==1m1=min1;min2=find(tree(2,:)==s1(i-n,2));m2=min2(1);elsem1=min1(1,1);m2=min1(1,2);end;tree(2,i)=tree(2,m1)+tree(2,m2);s2(i)=tree(2,m1)+tree(2,m2);s2(m1)=-1;s2(m2)=-1;tree(5,i)=1;tree(3,m1)=i;tree(3,m2)=i;tree(4,m1)=1;tree(4,m2)=0;tree(5,m1)=0;tree(5,m2)=0;endHuffmanTree=tree;disp('哈夫曼樹如下：');disp(HuffmanTree);end%完成構(gòu)成完整的基本樹，形成huffmantree，并對(duì)其遍歷，得到碼表，通過碼表對(duì)序列進(jìn)行編碼，并求其平均碼長(zhǎng)，信息熵，編碼效率；%HuffmanTree哈夫曼樹，pro碼元概率分布矩陣，S，待編碼序列；編碼序列function[Codenumber,huffmantable,Code2]=huffmanencode221(HuffmanTree,pro,bit)p=pro;a1=unique(bit);a2=bit;len1=length(a1);%碼元序列的長(zhǎng)度；len2=length(a2);%所要編碼序列的長(zhǎng)度；a3=zeros(1,len2);%生成與編碼序列長(zhǎng)度一樣的零矩陣，用以存放編碼對(duì)應(yīng)的下標(biāo)；Code=[];%存放其遍歷一個(gè)碼元所對(duì)應(yīng)的編碼；Code2=[];%記錄各個(gè)碼元的碼長(zhǎng)；Lastnumber=1;Sumnumber=0;%累積計(jì)算編碼總長(zhǎng)度；huffmantable=-ones(len1,len1);%建立len1*len1的單位負(fù)矩陣，用以存放其碼表；%遍歷二叉樹，生成碼表huffmantable;fori=1:len1;%循環(huán)完成len1個(gè)符號(hào)的編碼；k=pro(2,i);key=1;m=find(HuffmanTree(6,1:len1)==k);while(HuffmanTree(5,m)~=1)%判斷是否遍歷到根結(jié)點(diǎn)；Code(key)=HuffmanTree(4,m);key=key+1;m=HuffmanTree(3,m);%指向父節(jié)點(diǎn)；endlc=length(Code);huffmantable(i,1:lc)=fliplr(Code);%將Code矩陣中的編碼左右翻轉(zhuǎn)，完成倒序排列；Code2=[Code2,lc];%將各個(gè)碼元的編碼長(zhǎng)度賦予矩陣Code2;end%顯示碼表，即只輸出矩陣huffmantable中非-1的部分；disp('碼表如下：');Code4=[];fori=1:len1%顯示其碼表；disp(a1(pro(2,i)));flag=1;while(huffmantable(i,flag)~=-1)Code4(flag)=huffmantable(i,flag);flag=flag+1;end;Code4,disp('碼長(zhǎng)='),Code2(i)end;%%通過碼元與待編碼的序列一一比較，輸出huffmantable中對(duì)應(yīng)的編碼；Codenumber=[];fori=1:len2forj=1:len1ifa1(j)==a2(i)v=find(HuffmanTree(6,:)==j);flag=1;while(huffmantable(v,flag)~=-1)Code1(flag)=huffmantable(v,flag);flag=flag+1;Sumnumber=Sumnumber+1;end;Codenumber(Sumnumber-flag+2:Sumnumber)=[Code1(1:flag-1)];end;end;end;disp('編碼如下：');disp(Codenumber);%計(jì)算其平均碼長(zhǎng)；PJ_Code=pro(1,:)*Code2';%計(jì)算其信息熵；HX=0;fori=1:len1HX=HX-pro(1,i)*log2(pro(1,i));end;%計(jì)算其編碼效率；N=HX/PJ_Code;disp('平均碼長(zhǎng)：