(完整word版)Huffman编译码讲解

1、信息论与编码基础实验报告2实验二 Huffman 编译码设计思想Huffman 编码是一种基于统计的可变长无损信源编码，编码效率最高。Huffman 编码首先要统计出消息序列中每个符号的出现概率，根据概率来编码，对出现概率大的分配短码， 出现概率小的分配长码，达到平均码长最小的效果。本实验要实现Huffman 编译码以及模拟 BSC 信道传输过程，需要进行字符概率统计、编写编码算法、加入信道干扰、编写解码 算法。二实现流程（一）Huffman 编码1.统计各字符概率找出不重复的字符，构成信 源符号集2.构建概率排序矩阵1）将信源消息的概率按大小顺序重新排列，为第一列依次找出相同*字符的个数32

2、） 把第一列两个最小的概率相加，和剩余的概率重新排队，作为第二列3） 把最小的两个概率相加，再重新排队，重复上述过程直到最后变成概率例如输入字符串“ 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.依据概率排序矩阵编码规定每次将概率大的计为 0,概率小的计为 1 ;从最后一列开始编码， 倒数第二 列依据其概率排序情况，确定和最后一列编码的关系。以2 中概率排序矩阵为例，倒数第二

3、列编码基于概率矩阵中倒数第二列后两个概率的和是最后一列的首位，所 以把最后一列的 0 直接挪到倒数第二列的后两位，作为第一位。按照这样的规律， 依次可以作出之前列的编码。111001010010000000100100010011（二）信道传输输入编码 比特流-每一位以 P 的转移概率改变-输出信道作用后的比特流例如输入 100 100 100,信道传输误码随机比特流001 000 000 ,则第三位传输错误，信道输出为 101 100 100。用 a1a2a3an 表示输入比特流,b1b2b3.bn表示信道错误转移的随机比特流,C1C2c表示输出比特流，则作用关系可以描述为:a1a21 a3

4、1 | a b b .J bnC1C2C3Cn其中bi=10P1 -P4（三）Huffman 解码5解码算法采用查表的思想，即从第一个比特开始在码表中对应寻找符合的码值， 如果符 合则取出，若不符合则考察这一比特与下一比特的组合在码表是否有对应码， 依次类推，循 环进行，直到循环结束取出所有对应的码来。三结论分析（一）对字符串进行 Huffman 编码、BSC 信道传输、译码对 Where there is a will, there is a way.进行编码,设定错误转移概率 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编码性能平均码长=3.5676熵=3.52889 编码效率=0.9892输出码串：01101001100000100001110

6、0100110000010000110101100011010011101101011010101001100100100110000010000110101100011010011101101000111101110 计算压缩效率：压缩前字符串一共有 37 个，ASCII 码表示一共用去 37*8=296bit压缩后比特流一共有 146bit压缩效率为 0.4932BSC 信道传输接受码串：011010011000001000011100100110000010000110101100011010011101101011010101001100100100110000010000110101

7、100011010011101101000111101110错误比特数：0译码输出字符串：Where there is a will, there is a way.从输出结果可以看出，原字符串经过Hufman 编码、BSC 信道传输和译码，正确地得到了传输，Huffman 编码实现了压缩，传输效率提高。误码扩散效应次数错误位数译码结果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 次试验，可以观察到在不同错误位数下的译码结果,显。前面一位出错将导致后面几个字符解码面目全非。可以看出误码扩散效应比较明8（二）对 txt 文件进行 Hufman 编码、BSC 信道传输、译码打开 text2.txt,进行 Huffman 编码，并在错误转移概率为 0.01 的信道中传输，译码后将 字符串输出为 output.txt 保存。编码性能1172 个，ASCII 码表示一共用去 1172*8=9376bit压缩后比特流一共有5

9、689bit压缩效率为 0.6068 误码扩散效应可以看出文档中文字基本被全部正确译码出来， 存在个别出错位，但不影响整体的文字 信息的表达。（三）对图像文件进行 Huffman 编码、BSC 信道传输、译码错误转移概率图像编码前/信息论与编码基础编码后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弋內仃u&osLrw-l to ganulaie a和释1也1eoaing intoonje严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口因阳1*Ihisfunciiis in dScope转迥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肋;叮口鼻LnpuL 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平均码长=4.4138熵=4.3714 编码效率=0.9904压缩前字符串一共有910-4信息论与编离出10-5信息论与编码基础编码性能平均码长=4.2687熵=4.2027 编码效率=0.9845压缩前图片大小 5264B压缩后比特流一共有 30914bit=3864B压缩效率为 0.7340误码扩散效应从实验结果来看，在错误转移概率10-3时误码效应很明显，无法正确恢复出图像。随着信道错误转移概率下降，图象恢复地越来越好。四思考题解答（一）如何对文本进行概率统计？第一步，构建不重复字符表。用搜索的方法，从文本第一个字符开始往后

18、读，记录字符表，当下一个字符与当前字符表中所有字符都不同时，将其存入并更新字符表。第二步，以第一个字符为例，在文本中依次搜索，遇到与第一个字符相等的字符，则计数加 1,直到搜索结束。进行第二个字符的重复次数统计依次进行，并将搜索结束后的 计数值存入一个向量中。即得到和字符顺序相对应的重复个数。最后与文本字符总数作比， 即得到文本中所有不重复字符的概率，构成完整的信源空间。（二）Huffman 码误码扩散特性如何缓解？由实验现象特别是图象编译码可以观察到，Huffman 码的误码扩散效应是比较严重的。前面的码串错位将对后续解码产生较大影响。实际信道必然有噪声存在， 变长码的结构必然会被破坏。然而

19、变长码是不加同步的码，无法自动清洗。但是可以人为地在信息序列中每固定长度的字符后加一个标识符，假定它在消息序列中出现的概率最小，那么它的码长是最大的，我们可以利用这个码长实现标识清洗。10附录% %对信源进行统计，得到字符的概率 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%找出不重复的字符 (包括空格 ) 构成信源 n=length(L);N=zeros(1,n);for i=1:nfor j=1:n0if L(i)=L0(j)N(i)=N(i)+1;endendend%找出相同字符的个数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;% 倒数第二行置为刚才的概率和 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%开始记录编码过程cp=cell(n,n-1);%code pool cp1,n-1=0

22、;% 概率大的为 0 cp2,n-1=1;% 概率小的为 1t=2;for t=2:n-1%给倒数第 t 列元素编码cp t,n-t =cp PB(n,n-t+1) ,n-t+1,0;% 根据倒数 t-1 列的概率排序情况确定倒数第 的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% %显示编码结果 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( 平均码长 ) lenav=sum(len.*P)% 平均码长 display( 熵)H=sum(-P.*log2(P) ) displa