(完整word版)Huffman編譯碼講解

1、信息論與編碼基礎(chǔ)實(shí)驗(yàn)報(bào)告2實(shí)驗(yàn)二 Huffman 編譯碼設(shè)計(jì)思想Huffman 編碼是一種基于統(tǒng)計(jì)的可變長(zhǎng)無(wú)損信源編碼，編碼效率最高。Huffman 編碼首先要統(tǒng)計(jì)出消息序列中每個(gè)符號(hào)的出現(xiàn)概率，根據(jù)概率來(lái)編碼，對(duì)出現(xiàn)概率大的分配短碼， 出現(xiàn)概率小的分配長(zhǎng)碼，達(dá)到平均碼長(zhǎng)最小的效果。本實(shí)驗(yàn)要實(shí)現(xiàn)Huffman 編譯碼以及模擬 BSC 信道傳輸過(guò)程，需要進(jìn)行字符概率統(tǒng)計(jì)、編寫(xiě)編碼算法、加入信道干擾、編寫(xiě)解碼 算法。二實(shí)現(xiàn)流程（一）Huffman 編碼1.統(tǒng)計(jì)各字符概率找出不重復(fù)的字符，構(gòu)成信 源符號(hào)集2.構(gòu)建概率排序矩陣1）將信源消息的概率按大小順序重新排列，為第一列依次找出相同*字符的個(gè)數(shù)32

2、） 把第一列兩個(gè)最小的概率相加，和剩余的概率重新排隊(duì)，作為第二列3） 把最小的兩個(gè)概率相加，再重新排隊(duì)，重復(fù)上述過(guò)程直到最后變成概率例如輸入字符串“ abccddeeee”，得到概率向量為0.1 0.1 0.2 0.2 0.4，則概率排序矩陣為：0.40000.40000.40000.60000.20000.20000.40000.40000.20000.20000.20000.10000.20000.10003.依據(jù)概率排序矩陣編碼規(guī)定每次將概率大的計(jì)為 0,概率小的計(jì)為 1 ;從最后一列開(kāi)始編碼， 倒數(shù)第二 列依據(jù)其概率排序情況，確定和最后一列編碼的關(guān)系。以2 中概率排序矩陣為例，倒數(shù)第二

3、列編碼基于概率矩陣中倒數(shù)第二列后兩個(gè)概率的和是最后一列的首位，所 以把最后一列的 0 直接挪到倒數(shù)第二列的后兩位，作為第一位。按照這樣的規(guī)律， 依次可以作出之前列的編碼。111001010010000000100100010011（二）信道傳輸輸入編碼 比特流-每一位以 P 的轉(zhuǎn)移概率改變-輸出信道作用后的比特流例如輸入 100 100 100,信道傳輸誤碼隨機(jī)比特流001 000 000 ,則第三位傳輸錯(cuò)誤，信道輸出為 101 100 100。用 a1a2a3an 表示輸入比特流,b1b2b3.bn表示信道錯(cuò)誤轉(zhuǎn)移的隨機(jī)比特流,C1C2c表示輸出比特流，則作用關(guān)系可以描述為:a1a21 a3

4、1 | a b b .J bnC1C2C3Cn其中bi=10P1 -P4（三）Huffman 解碼5解碼算法采用查表的思想，即從第一個(gè)比特開(kāi)始在碼表中對(duì)應(yīng)尋找符合的碼值， 如果符 合則取出，若不符合則考察這一比特與下一比特的組合在碼表是否有對(duì)應(yīng)碼， 依次類推，循 環(huán)進(jìn)行，直到循環(huán)結(jié)束取出所有對(duì)應(yīng)的碼來(lái)。三結(jié)論分析（一）對(duì)字符串進(jìn)行 Huffman 編碼、BSC 信道傳輸、譯碼對(duì) Where there is a will, there is a way.進(jìn)行編碼,設(shè)定錯(cuò)誤轉(zhuǎn)移概率 Pe=0.01,模擬傳輸和解碼: huffHuffma棉瑪與解碼輸岀:解碼6)11Q1D01C10100111fl

5、111CC100110010010011100110101 TOOWhara there i& awiltbe日匪丑審ay7得到碼表:字符概率編碼字符概率編碼0.189211w0.05411011e0.1622000s0.05411000a0.08110100t0.05411001i0.081101010.027001110r0.08110010y0.027001111h0.0811001150.027001100l0.05411010W0.027001101編碼性能平均碼長(zhǎng)=3.5676熵=3.52889 編碼效率=0.9892輸出碼串：01101001100000100001110

6、0100110000010000110101100011010011101101011010101001100100100110000010000110101100011010011101101000111101110 計(jì)算壓縮效率：壓縮前字符串一共有 37 個(gè)，ASCII 碼表示一共用去 37*8=296bit壓縮后比特流一共有 146bit壓縮效率為 0.4932BSC 信道傳輸接受碼串：011010011000001000011100100110000010000110101100011010011101101011010101001100100100110000010000110101

7、100011010011101101000111101110錯(cuò)誤比特?cái)?shù)：0譯碼輸出字符串：Where there is a will, there is a way.從輸出結(jié)果可以看出，原字符串經(jīng)過(guò)Hufman 編碼、BSC 信道傳輸和譯碼，正確地得到了傳輸，Huffman 編碼實(shí)現(xiàn)了壓縮，傳輸效率提高。誤碼擴(kuò)散效應(yīng)次數(shù)錯(cuò)誤位數(shù)譯碼結(jié)果12Where there is a will, the,yew,W, a way.21Where there is a will, ti,ae is a way.31Where there is a will,lWWhere is a way.45W,W,ae

8、 e,iere is alr.lh there is a way.54Where there iWWar will, tweia,hs a wa ,Wr做 5 次試驗(yàn)，可以觀察到在不同錯(cuò)誤位數(shù)下的譯碼結(jié)果,顯。前面一位出錯(cuò)將導(dǎo)致后面幾個(gè)字符解碼面目全非?？梢钥闯稣`碼擴(kuò)散效應(yīng)比較明8（二）對(duì) txt 文件進(jìn)行 Hufman 編碼、BSC 信道傳輸、譯碼打開(kāi) text2.txt,進(jìn)行 Huffman 編碼，并在錯(cuò)誤轉(zhuǎn)移概率為 0.01 的信道中傳輸，譯碼后將 字符串輸出為 output.txt 保存。編碼性能1172 個(gè)，ASCII 碼表示一共用去 1172*8=9376bit壓縮后比特流一共有5

9、689bit壓縮效率為 0.6068 誤碼擴(kuò)散效應(yīng)可以看出文檔中文字基本被全部正確譯碼出來(lái)， 存在個(gè)別出錯(cuò)位，但不影響整體的文字 信息的表達(dá)。（三）對(duì)圖像文件進(jìn)行 Huffman 編碼、BSC 信道傳輸、譯碼錯(cuò)誤轉(zhuǎn)移概率圖像編碼前/信息論與編碼基礎(chǔ)編碼后10-210-31n立侑F：i昨同fiftM輻聞（HlJ oiriutbit “ iH摹車立詼F) miEJ MI：-D) (! tgtailflThe TliEy n T 3 nTninuiil. i nn nnd Cndirm. Hic ilFlAIRE pnsrnji uss lheBtnaloe inputs of the C515 t

10、asinlate a dat-aloisger. This vxunpk & how yxwjcanfunf-tioiia in胡3色1“ sJmjJtiilC! a$用田11亡umiiiK InLCKine uf 111口anHDK hi口uLs nf itic8匚515. IhiLHEFJIRE prxiflr.1口lhiL；hii.ihfl i npu IKnfthe 516 tosivulate a dat-nlogaer. This eiaople Ehows hwICHJcaafunetiong In dSciopi to吿innI出M a sighalinWBiD ul.

11、 tbi* HJiaLcjR inpuLS uf Ihc CS15. 7hu the nrwiliufiinputstlw C5|!5 Ins i nu I a Lc cximple stiow-shoJMJ弋內(nèi)仃u&osLrw-l to ganulaie a和釋1也1eoaing intoonje嚴(yán)Li姑牛| ironi EiK |iii/iM r. ipntflrjuiUSPJ;ndalalogger. Thisfunciii in dScope cd：thLXrwil軸inputs of th?IHJ宜EitdcjR iIIIJUIJI；pturan usesC5I5 tosin

12、ulaten血、1口因陽(yáng)1*Ihisfunciiis in dScope轉(zhuǎn)迥I僧shovsIKyou eon u$e*9kAnaLbNJnululG且 ijRnail t;aai可懐也口工 口_tlw C5I5 The THEASUIffi prnflTWi us肚th? onulou inputsC5I5 tasimuLst a dalBloi!. ThiasnOTTlSowkKriu-lUHElhod勺ini dScupc! laa siKIIULcim.i rxg irihKimi of ihr臼nn】i繼i.ripuil恂ci Lbc 51 S_ The* )IEA5LKKpmreiB

13、 uses the u聞leg inputs- of the C5L3 tosinulatc & daialcigr.I hr nn 1 pg Enpuls ci I*theyouThw Tlicnry ciT Inifnimjiit i nn tnd Cnd.i ng_ The HEASIRE pnsfiTHnU5s the luwiloe inputs of the C515 tosiiulateHKJcanfunetiona in dSc4peLO鼻iuJt*lc! a jRiial亡umiiiK IriLOunc uf Ihc anulux hi口uits IiP IJM;C5

14、1S.The8Eft5IJRfi prixfirnji ii3；rsIJHG肋;?？诒荓npuL sif tlw亦iR tJOsimliBteBdataloeffer. Thi-e exavb siie血ho* mj_csn usesin&l funcliliontt in dSeopeio 9iulati a 9ianal|CMOIIIK|jnluuuic! dT the ilFTiSrRE pmrj-tn usrsn daialGeRcr. This funcii-ons in dScopeLHNJ-OfittluK liniJLil/LhicunaLo inputs of the

15、 C5J5 loiirulntc o血rtA】oflgMThisxamcile shoiffl bow you e-an usesina funciiflis in dScope La iiujll i1- nLjfnH.1 iznininK inlravii? ciT LhH!HUHIICIRinjpuls ir tlw C5I5, TheliEASURE projrrmi uses the onalos i中摘刖I the C515 loaiHjlaie右(htalogr.This example shiAii ftoMi you etui nsITa-iKIlid L tLHiclimu

16、f Jtl dScupCi- toJauJule且cunirK inliMini!DTLhr科HH】RKinputs cilLHH!515- The! 1IEA5URF profMHuses lhe-RIMlog inputs of the C5L3 tosiriulEite a ddiiaLogr.HJialuff inpuLM of Ih? C51S. Thr1!IDmruiliDfiinpiiLs口l.hf：(751 Ji tasiliulnij! exoffipk sliow-slio yj c白仃u&esLrml to sinuldie呂siicriLepaing! into

17、orw orfiiihr C515. Tbc HliASJURE平均碼長(zhǎng)=4.4138熵=4.3714 編碼效率=0.9904壓縮前字符串一共有910-4信息論與編離出10-5信息論與編碼基礎(chǔ)編碼性能平均碼長(zhǎng)=4.2687熵=4.2027 編碼效率=0.9845壓縮前圖片大小 5264B壓縮后比特流一共有 30914bit=3864B壓縮效率為 0.7340誤碼擴(kuò)散效應(yīng)從實(shí)驗(yàn)結(jié)果來(lái)看，在錯(cuò)誤轉(zhuǎn)移概率10-3時(shí)誤碼效應(yīng)很明顯，無(wú)法正確恢復(fù)出圖像。隨著信道錯(cuò)誤轉(zhuǎn)移概率下降，圖象恢復(fù)地越來(lái)越好。四思考題解答（一）如何對(duì)文本進(jìn)行概率統(tǒng)計(jì)？第一步，構(gòu)建不重復(fù)字符表。用搜索的方法，從文本第一個(gè)字符開(kāi)始往后

18、讀，記錄字符表，當(dāng)下一個(gè)字符與當(dāng)前字符表中所有字符都不同時(shí)，將其存入并更新字符表。第二步，以第一個(gè)字符為例，在文本中依次搜索，遇到與第一個(gè)字符相等的字符，則計(jì)數(shù)加 1,直到搜索結(jié)束。進(jìn)行第二個(gè)字符的重復(fù)次數(shù)統(tǒng)計(jì)依次進(jìn)行，并將搜索結(jié)束后的 計(jì)數(shù)值存入一個(gè)向量中。即得到和字符順序相對(duì)應(yīng)的重復(fù)個(gè)數(shù)。最后與文本字符總數(shù)作比， 即得到文本中所有不重復(fù)字符的概率，構(gòu)成完整的信源空間。（二）Huffman 碼誤碼擴(kuò)散特性如何緩解？由實(shí)驗(yàn)現(xiàn)象特別是圖象編譯碼可以觀察到，Huffman 碼的誤碼擴(kuò)散效應(yīng)是比較嚴(yán)重的。前面的碼串錯(cuò)位將對(duì)后續(xù)解碼產(chǎn)生較大影響。實(shí)際信道必然有噪聲存在， 變長(zhǎng)碼的結(jié)構(gòu)必然會(huì)被破壞。然而

19、變長(zhǎng)碼是不加同步的碼，無(wú)法自動(dòng)清洗。但是可以人為地在信息序列中每固定長(zhǎng)度的字符后加一個(gè)標(biāo)識(shí)符，假定它在消息序列中出現(xiàn)的概率最小，那么它的碼長(zhǎng)是最大的，我們可以利用這個(gè)碼長(zhǎng)實(shí)現(xiàn)標(biāo)識(shí)清洗。10附錄% %對(duì)信源進(jìn)行統(tǒng)計(jì)，得到字符的概率 clear all;clc;%L0=input(please input a string:); % 輸入字符串 %L0=eeeebccdda;L0=Where 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, L

20、0(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%找出相同字符的個(gè)數(shù)Pc=N/n0;% 得到概率%霍夫曼編碼P=Pc;p0,k0=sort(P);k=fliplr(k0);% 降序排列 p=fliplr(p0);% 降序排列概率 a0=p0;a=p;PB=zeros(n,n-1);% 空的編碼表(矩陣)概率矩陣 for i=1:nPB(i,1)=a(i);%B 第一列表示第一次的概率排序endfor j=1:

21、n-2ap=PB(n-j+1,j)+PB(n-j,j);% 每一列最后兩行概率相加 add probability a(n-j+1)=0;% 最后一行置 0a(n-j)=ap;% 倒數(shù)第二行置為剛才的概率和 a=fliplr(sort(a);% 重新排倒序11for i=1:nPB(i,j+1)=a(i);% 第二列填入重排概率end %查找合并后概率位置 r=find(a=ap);% 找到概率等于剛才概率和的位置PB(n,j+1)=r(end);%必須要加上 end,將同樣的概率排在最下面，保證排序end%開(kāi)始記錄編碼過(guò)程cp=cell(n,n-1);%code pool cp1,n-1=0

22、;% 概率大的為 0 cp2,n-1=1;% 概率小的為 1t=2;for t=2:n-1%給倒數(shù)第 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)% 如果概率和是最大的for j=1:t-1 cpj,n-t=cpj+1,n-t+1;% 后面一列 下面一行的編碼endelsefor j=1: PB( n,n-t+1 ) - 1cp j,

23、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 ;endend end12% %顯示編碼結(jié)果 A=;for i=1:nA=A;L(k(i);end codecell=cell(n,3);codecell=cellstr(A) num2cell(fliplr(p0) cp(:,1) for i=1:n len(i)=length(cpi,1);endP=fliplr(p0); display( 平均碼長(zhǎng) ) lenav=sum(len.*P)% 平均碼長(zhǎng) display( 熵)H=sum(-P.*log2(P) ) displa