Huffman編譯碼講解

1、信息論與編碼基礎(chǔ)實驗報告實驗二Huffman 編譯碼一 設(shè)計思想 編碼首HuffmanHuffman 編碼是一種基于統(tǒng)計的可變長無損信源編碼，編碼效率最高。先要統(tǒng)計出消息序列中每個符號的出現(xiàn)概率，根據(jù)概率來編碼，對出現(xiàn)概率大的分配短碼，編譯碼以及模Huffman出現(xiàn)概率小的分配長碼，達到平均碼長最小的效果。本實驗要實現(xiàn)信道傳輸過程，需要進行字符概率統(tǒng)計、編寫編碼算法、加入信道干擾、編寫解碼擬BSC 算法。 實現(xiàn)流程二 編碼（一）Huffman輸入字符串統(tǒng)計各字符概率兩最小概率相加概率逐次排序構(gòu)建概率排序矩陣依據(jù)概率排序矩陣逐次逆向編碼生成碼表.輸出編碼比特流圖1編碼基本流程1 .統(tǒng)計各字符概率

2、.找出不重復(fù)的,依次找出相同,計算概率向量字符，構(gòu)成信字符的個數(shù)源符號集構(gòu)建概率排序矩陣2.1）將信源消息的概率按大小順序重新排列，為第一列22）把第一列兩個最小的概率相加，和剩余的概率重新排隊，作為第二列13）把最小的兩個概率相加，再重新排隊，重復(fù)上述過程直到最后變成概率,則概率排序矩陣例如輸入字符串“abccddeeee”，得到概率向量為0.1 0.1 0.2 0.2 0.4為：0.6000 0.4000 0.4000 0.40000.4000 0.4000 0.2000 0.20000.2000 0.2000 0.20000.1000 0.20000.10003.依據(jù)概率排序矩陣編碼倒數(shù)

3、第二 1;從最后一列開始編碼，規(guī)定每次將概率大的計為 0,概 率小的計為中概率排序矩陣為例，列依據(jù)其概率排序情況，確定和最后一列編碼的關(guān)系。以 2 倒數(shù)第二列編碼基于概率矩陣中倒數(shù)第二列后兩個概率的和是最后一列的首位， 所直接挪到倒數(shù) 第二列的后兩位，作為第一位。按照這樣的規(guī)律，以把最后一列的 0依次可以作出之前列的編碼。0 1 1 11 01 01 00000 01 00000100100011（二）信道傳輸輸出信道作用p的每一位以輸入編碼VL.I后的比特流轉(zhuǎn)移概率改變比特流ca表示c表示信道錯誤轉(zhuǎn)移的隨機比特流，c表示輸入比特流，bb用aaab.bn213n2n131蹦出比特流，則作用關(guān)系

4、可以描述為:ccc.cb.aaa.abbb n132n3n11232p1 b其中1 0p例如輸入100 100 100,信道傳輸誤碼隨機比特流001 000 000,則第三位傳輸錯誤，信101 100 100道輸出為。Huffman （三）解碼 3如果符即從第一個比特開始在碼表中對應(yīng)尋找符合的碼值，解碼算法采用查表的思想，循依次類推，合則取出，若不符合則考察這一比特與下一比特的組合在碼表是否有對應(yīng)碼，環(huán)進行，直到循環(huán)結(jié)束取出所有對應(yīng)的碼來。輸入編碼比特串cf取cf第1到i位i=1i=i+1在碼表中搜索cf除去前i位N有對應(yīng)的碼字Y輸出一位字符Y取出的總比特數(shù)（編碼比特數(shù)N結(jié)束三結(jié)論分析（一）對

5、字符串進行 Huffman編碼、BSC信道傳輸、譯碼對 Where there is a will, there is a way. 進行編碼，設(shè)定錯誤轉(zhuǎn)移概率 Pe=0.01,模擬傳輸和解碼:4得到碼表:字概編字概編1011w0.1892 0.0541111000s0.1622e0.054100010010.05410.08110100ta 0111001010.08110.0270i. 0111100100.0811yr0.0270 01100 0011 0.0811 h 0.0270, 01101lW 0.05411010 0.0270編碼性能=0.9892 嫡平均碼長=3.5676 =

6、3.52889 編碼效率： 輸出碼串011010011000001000011100100110000010000110101100011010011101101011010101001100100100110000010000110101100011010011101101000111101110 計算壓縮效率：37*8=296bitASCII個，碼表示一共用去37壓縮前字符串一共有146bit壓縮后比特流一共有0.4932壓縮效率為BSC信道傳輸接受碼串：01101001100000100001110010011000001000011010110001101001110110101101

7、0101001100100100 1100000100001101011000110100111011010001111011100錯誤比特數(shù)：譯碼 輸出字符串： Where there is a will, there is a way.信道傳輸和譯碼，正確地得 Huffman從輸出結(jié)果可以看出，原字符串經(jīng)過編碼、BSC Huffman到了傳輸，編碼實現(xiàn)了壓縮，傳輸效率提高。誤碼擴散效應(yīng)次數(shù)錯誤位數(shù)譯碼結(jié)果Where there is a will, the,yew,W, a way. 2 1Where there is a will, ti,ae is a way. 1 2Where th

8、ere is a will,lWWhere is a way. 1 3W,W,ae e,iere is alr.lh there is a way. 5 4Where there iWWar will, tweia,hs a wa ,Wr45做5次試驗，可以觀察到在不同錯誤位數(shù)下的譯碼結(jié)果，可以看出誤碼擴散效應(yīng)比較明顯。前面一位出錯將導致后面幾個字符解碼面目全非。5信道傳輸、譯碼 txt文件進行 Huffman編碼、BSC （二）對譯碼后將 Huffman編碼，并在錯誤 轉(zhuǎn)移概率為0.01的信道中傳輸，打開 text2.txt ,進行 字符串輸出為 output.txt保存。.編碼性能=0.9

9、904編碼效率 平均碼長=4.4138嫡=4.37141172*8=9376bit碼表示一共用去壓縮前字符串一共有1172個，ASCII5689bit壓縮后比特流一共有0.6068壓縮效率為誤碼擴散效應(yīng)但不影響整體的文字可以看出文檔中文字基本被全部正確譯碼出來，存在個別出錯位,信息的表達。BSC編碼、信道傳輸、譯碼（三）對圖像文件進行Huffman-2圖像錯誤轉(zhuǎn)移概率信息論與編碼基礎(chǔ)106編碼前編碼后平均碼長=4.26875264B移概率下降，圖象恢復(fù)地越來越好。四思考題解答 （一）如何對文本進行概率統(tǒng)計?-5 10編碼性能=0.9845編碼效率嫡=4.2027壓縮前圖片大小30914bit=

10、3864B壓縮后比特流一共有 0.7340壓縮效率為誤碼擴散效應(yīng)-3時誤10著信道錯誤轉(zhuǎn)碼效應(yīng)很明顯，無法正確恢復(fù)出圖像。隨從實驗結(jié)果來看，在錯誤轉(zhuǎn)移概率表，當下一個字符與當前字符表中所有字符都不同時,將其存入并更新字符表。則計遇到與第一個字符從文本第一個字符開始往后讀，記錄字符第一步，構(gòu)建不重復(fù)字符表。用搜索的方法,直到搜索結(jié)束。進行第二個字相等的字符，第二步，以第一個字符為例，在文本中依次搜索,符的重復(fù)次數(shù)統(tǒng)計依次進行，并將搜索結(jié)束后的 1數(shù)加計數(shù)值存入一個向量中。即得到和字符順序相對應(yīng)的重復(fù)個數(shù)。最后與文本字符總數(shù)作比，即得到文本中所有不重復(fù)字符的概率，構(gòu)成完整的信源空間。（二） Huf

11、fman 碼誤碼擴散特性如何緩解？碼的誤碼擴散效應(yīng)是比較嚴重的。 由實驗現(xiàn)象特別是圖象編譯碼可以觀察到，Huffman 變長碼的結(jié)構(gòu)必然前面的碼串錯位將對后續(xù)解碼產(chǎn)生較大影響。實際信道必然有噪聲存在，但是可以人為地在信息序列中每固無法自動清洗。 會被破壞。然而變長碼是不加同步的碼，那么它的碼長是最大定長度的字符后加一個標識符，假定它在消息序列中出現(xiàn)的概率最小，的，我們可以利用這個碼長實現(xiàn)標識清洗。7附錄%對信源進行統(tǒng)計，得到字符的概率clear all;clc;%L0=input(please input a string:); % 輸入字符串 %L0=eeeebccdda;L0=Where

12、there is a will,there is a way.; n0=length(L0);L=L0(1); i=2;while i=n0if strfind(L,L0(i) i=i+1;elseL=L, L0(i);i=i+1;endend%找出不重復(fù)的字符(包括空格) 構(gòu)成信源n=length(L);N=zeros(1,n);for i=1:nfor j=1:n0if L(i)=L0(j) N(i)=N(i)+1;endendend %找出相同字符的個數(shù)Pc=N/n0;% 得到概率%霍夫曼編碼P=Pc;p0,k0=sort(P);k=fliplr(k0);% 降序排列p=fliplr(p

13、0);% 降序排列概率a0=p0;a=p;PB=zeros(n,n -1);%空的編碼表(矩陣)概率矩陣 for i=1:n8PB(i,1)=a(i);%B 第一列表示第一次的概率排序endfor j=1:n -2ap=PB(n-j+1,j)+PB(n -j,j);% 每一列最后兩行概率相加add probabilitya(n-j+1)=0;% 最后一行置0a(n-j)=ap;% 倒數(shù)第二行置為剛才的概率和a=fliplr(sort(a);% 重新排倒序for i=1:nPB(i,j+1)=a(i);% 第二列填入重排概率end%查找合并后概率位置r=find(a=ap);% 找到概率等于剛才

14、概率和的位置PB(n,j+1)=r(end);%必須要加上end,將同樣的概率排在最下面，保證排序 end %開始記錄編碼過程cp=cell(n,n -1);%code poolcp1,n -1=0;% 概率大的為0cp2,n -1=1;% 概率小的為1t=2;for t=2:n -1%給倒數(shù)第t 列元素編碼t 列的cp t,n -t =cp PB(n,n -t+1) ,n -t+1,0;% 根據(jù)倒數(shù)t-1 列的概率排序情況確定倒數(shù)第cpt+1,n -t=cp PB(n,n -t+1),n -t+1 ,1;% 這兩步是確定每一列最小概率的編碼的if(PB(n,n -t+1)=1)% 如果概率和

15、是最大的for j=1:t -1cpj,n -t=cpj+1,n -t+1;% 后面一列下面一行的編碼endelsefor j=1: PB( n,n -t+1 ) - 1cp j, n -t=cp j, n -t+1;endfor j=PB(n,n -t+1):t -1cp j, n -t=cp j+1 , n -t+1 ;endendend9%顯示編碼結(jié)果A=;for i=1:nA=A;L(k(i);endcodecell=cell(n,3);codecell=cellstr(A) num2cell(fliplr(p0) cp(:,1) for i=1:nlen(i)=length(cpi,

16、1);endP=fliplr(p0);display( 平均碼長)lenav=sum(len.*P)% 平均碼長display( 熵 )H=sum( -P.*log2(P) )display( 編碼效率)P=H/lenavcf=;for i=1:n0cf=cf cell2mat(codecell(find(A=L0(i),3);enddisplay( 編碼 ) cfD1=cell2mat(codecell(1,3);D2=cell2mat(codecell(2,3);D3=cell2mat(codecell(3,3);%BSC 傳輸cf0=cf;p=10A(-2);%P表示錯誤概率for i=1:length(cf0)模 2 加得到傳輸后的編碼cf1(i)=mod(str2num(cf0(i)+(unidrnd(ceil(1/p)=1),2);% delta(i)=cf1(i) -str2num(cf0(i);% 作差來計算錯誤位置 10endep=find(delta=0);%error positiondisplay(length(ep), 錯誤位數(shù))cf2=;for i=1:length(cf0)cf2=strcat(cf2,num2str(cf1(i);% 傳輸后得到的編碼化為字符形式endcf2bsc=cf2;% 解碼ncf=length(cf2);