Huffman編譯碼講解

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

2、.找出不重復(fù)的,依次找出相同,計(jì)算概率向量字符，構(gòu)成信字符的個(gè)數(shù)源符號(hào)集構(gòu)建概率排序矩陣2.1）將信源消息的概率按大小順序重新排列，為第一列22）把第一列兩個(gè)最小的概率相加，和剩余的概率重新排隊(duì)，作為第二列13）把最小的兩個(gè)概率相加，再重新排隊(duì)，重復(fù)上述過(guò)程直到最后變成概率,則概率排序矩陣?yán)巛斎胱址癮bccddeeee”，得到概率向量為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;從最后一列開(kāi)始編碼，規(guī)定每次將概率大的計(jì)為 0,概 率小的計(jì)為中概率排序矩陣為例，列依據(jù)其概率排序情況，確定和最后一列編碼的關(guān)系。以 2 倒數(shù)第二列編碼基于概率矩陣中倒數(shù)第二列后兩個(gè)概率的和是最后一列的首位， 所直接挪到倒數(shù) 第二列的后兩位，作為第一位。按照這樣的規(guī)律，以把最后一列的 0依次可以作出之前列的編碼。0 1 1 11 01 01 00000 01 00000100100011（二）信道傳輸輸出信道作用p的每一位以輸入編碼VL.I后的比特流轉(zhuǎn)移概率改變比特流ca表示c表示信道錯(cuò)誤轉(zhuǎn)移的隨機(jī)比特流，c表示輸入比特流，bb用aaab.bn213n2n131蹦出比特流，則作用關(guān)系

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

5、字符串進(jìn)行 Huffman編碼、BSC信道傳輸、譯碼對(duì) Where there is a will, there is a way. 進(jìn)行編碼，設(shè)定錯(cuò)誤轉(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 嫡平均碼長(zhǎng)=3.5676 =

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

7、0101001100100100 1100000100001101011000110100111011010001111011100錯(cuò)誤比特?cái)?shù)：譯碼 輸出字符串： Where there is a will, there is a way.信道傳輸和譯碼，正確地得 Huffman從輸出結(jié)果可以看出，原字符串經(jīng)過(guò)編碼、BSC Huffman到了傳輸，編碼實(shí)現(xiàn)了壓縮，傳輸效率提高。誤碼擴(kuò)散效應(yīng)次數(shù)錯(cuò)誤位數(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次試驗(yàn)，可以觀察到在不同錯(cuò)誤位數(shù)下的譯碼結(jié)果，可以看出誤碼擴(kuò)散效應(yīng)比較明顯。前面一位出錯(cuò)將導(dǎo)致后面幾個(gè)字符解碼面目全非。5信道傳輸、譯碼 txt文件進(jìn)行 Huffman編碼、BSC （二）對(duì)譯碼后將 Huffman編碼，并在錯(cuò)誤 轉(zhuǎn)移概率為0.01的信道中傳輸，打開(kāi) text2.txt ,進(jìn)行 字符串輸出為 output.txt保存。.編碼性能=0.9

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

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

11、fman 碼誤碼擴(kuò)散特性如何緩解？碼的誤碼擴(kuò)散效應(yīng)是比較嚴(yán)重的。 由實(shí)驗(yàn)現(xiàn)象特別是圖象編譯碼可以觀察到，Huffman 變長(zhǎng)碼的結(jié)構(gòu)必然前面的碼串錯(cuò)位將對(duì)后續(xù)解碼產(chǎn)生較大影響。實(shí)際信道必然有噪聲存在，但是可以人為地在信息序列中每固無(wú)法自動(dòng)清洗。 會(huì)被破壞。然而變長(zhǎng)碼是不加同步的碼，那么它的碼長(zhǎng)是最大定長(zhǎng)度的字符后加一個(gè)標(biāo)識(shí)符，假定它在消息序列中出現(xiàn)的概率最小，的，我們可以利用這個(gè)碼長(zhǎng)實(shí)現(xiàn)標(biāo)識(shí)清洗。7附錄%對(duì)信源進(jìn)行統(tǒng)計(jì)，得到字符的概率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 %找出相同字符的個(gè)數(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 %開(kāi)始記錄編碼過(guò)程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( 平均碼長(zhǎng))lenav=sum(len.*P)% 平均碼長(zhǎng)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表示錯(cuò)誤概率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);% 作差來(lái)計(jì)算錯(cuò)誤位置 10endep=find(delta=0);%error positiondisplay(length(ep), 錯(cuò)誤位數(shù))cf2=;for i=1:length(cf0)cf2=strcat(cf2,num2str(cf1(i);% 傳輸后得到的編碼化為字符形式endcf2bsc=cf2;% 解碼ncf=length(cf2);