Huffman编译码

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

2、排队，作为第二列3) 把最小的两个概率相加，再重新排队，重复上述过程直到最后变成概率1例如输入字符串“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（二）信道传输用a1a2a3an表示输入比特流，b1b2b3.bn表示信道错误转移的随机比特流，c1c2cn表示输出比特流，则作用关系可以描述为：其中例如输入100 100 100，信道传输误码随机比特流001 000 000，则第三位传输错误，信道输出为101 100 100。（三）Huffman解码 解码算法采用查表的思想，即从第一个比特开始在码表中对应寻找符合的码值，如果符合则取出，若不符合则考察这一比特与下一比特的组合在码表

4、是否有对应码，依次类推，循环进行，直到循环结束取出所有对应的码来。三 结论分析（一）对字符串进行Huffman编码、BSC信道传输、译码对Where there is a will, there is a way. 进行编码, 设定错误转移概率Pe=0.01, 模拟传输和解码：得到码表： 字符概率编码字符概率编码 0.189211w0.05411011e0.1622000s0.05411000a0.08110100t0.05411001i0.08110101.0.027001110r0.08110010y0.027001111h0.08110011,0.027001100l0.05411010

5、W0.027001101编码性能平均码长=3.5676 熵=3.52889 编码效率=0.9892输出码串:011010011000001000011100100110000010000110101100011010011101101011010101001100100100110000010000110101100011010011101101000111101110计算压缩效率：压缩前字符串一共有37个，ASCII码表示一共用去37*8=296bit压缩后比特流一共有146bit压缩效率为0.4932BSC信道传输接受码串：011010011000001000011100100110000

6、010000110101100011010011101101011010101001100100100110000010000110101100011010011101101000111101110错误比特数：0译码输出字符串：Where there is a will, there is a way.从输出结果可以看出，原字符串经过Huffman编码、BSC信道传输和译码，正确地得到了传输， Huffman编码实现了压缩，传输效率提高。误码扩散效应次数错误位数译码结果12Where there is a will, the,yew,W, a way.21Where there is a wi

7、ll, ti,ae is a way.31Where there is a will,lWWhere is a way.45W,W,ae e,iere is alr.lh there is a way.54Where there iWWar will, tweia,hs a wa ,Wr做5次试验，可以观察到在不同错误位数下的译码结果，可以看出误码扩散效应比较明显。前面一位出错将导致后面几个字符解码面目全非。（二）对txt文件进行Huffman编码、BSC信道传输、译码打开text2.txt，进行Huffman编码，并在错误转移概率为0.01的信道中传输，译码后将字符串输出为output.tx

8、t保存。编码性能平均码长=4.4138 熵=4.3714 编码效率=0.9904压缩前字符串一共有1172个，ASCII码表示一共用去1172*8=9376bit压缩后比特流一共有5689bit压缩效率为0.6068误码扩散效应可以看出文档中文字基本被全部正确译码出来，存在个别出错位，但不影响整体的文字信息的表达。（三）对图像文件进行Huffman编码、BSC信道传输、译码错误转移概率图像编码前/编码后10-210-310-410-5编码性能平均码长=4.2687 熵=4.2027 编码效率=0.9845压缩前图片大小5264B压缩后比特流一共有30914bit=3864B压缩效率为0.734

9、0误码扩散效应从实验结果来看，在错误转移概率<10-3时误码效应很明显，无法正确恢复出图像。随着信道错误转移概率下降，图象恢复地越来越好。四 思考题解答（一）如何对文本进行概率统计？第一步，构建不重复字符表。用搜索的方法，从文本第一个字符开始往后读，记录字符表，当下一个字符与当前字符表中所有字符都不同时，将其存入并更新字符表。第二步，以第一个字符为例，在文本中依次搜索，遇到与第一个字符相等的字符，则计数加1，直到搜索结束。进行第二个字符的重复次数统计依次进行，并将搜索结束后的计数值存入一个向量中。即得到和字符顺序相对应的重复个数。最后与文本字符总数作比，即得到文本中所有不重复字符的概率，

10、构成完整的信源空间。（二）Huffman码误码扩散特性如何缓解？由实验现象特别是图象编译码可以观察到，Huffman码的误码扩散效应是比较严重的。前面的码串错位将对后续解码产生较大影响。实际信道必然有噪声存在，变长码的结构必然会被破坏。然而变长码是不加同步的码，无法自动清洗。但是可以人为地在信息序列中每固定长度的字符后加一个标识符，假定它在消息序列中出现的概率最小，那么它的码长是最大的，我们可以利用这个码长实现标识清洗。附录 %对信源进行统计，得到字符的概率clear all;clc;%L0=input('please input a string:'); %输入字符串%L0=

11、'eeeebccdda'L0='Where there is a will,there is a way.'n0=length(L0);L=L0(1); i=2;while i<=n0 if strfind(L,L0(i) i=i+1; else L=L, L0(i); i=i+1; endend%找出不重复的字符(包括空格) 构成信源n=length(L);N=zeros(1,n);for i=1:n for j=1:n0 if L(i)=L0(j) N(i)=N(i)+1; end endend %找出相同字符的个数Pc=N/n0;%得到概率%霍夫曼编

12、码P=Pc;p0,k0=sort(P);k=fliplr(k0);%降序排列p=fliplr(p0);%降序排列概率a0=p0;a=p;PB=zeros(n,n-1);%空的编码表（矩阵）概率矩阵for i=1:n PB(i,1)=a(i);%B第一列表示第一次的概率排序endfor j=1:n-2 ap=PB(n-j+1,j)+PB(n-j,j);%每一列最后两行概率相加 add probability a(n-j+1)=0;%最后一行置0 a(n-j)=ap;%倒数第二行置为刚才的概率和 a=fliplr(sort(a);%重新排倒序 for i=1:n PB(i,j+1)=a(i);%第

13、二列填入重排概率 end %查找合并后概率位置 r=find(a=ap);%找到概率等于刚才概率和的位置 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 %给倒数第t列元素编码 cp t,n-t =cp PB(n,n-t+1) ,n-t+1,'0'%根据倒数t-1列的概率排序情况确定倒数第t列的 cpt+1,n-t=cp PB(n,n

14、-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;%后面一列 下面一行的编码 end else for j=1: PB( n,n-t+1 ) - 1 cp j, n-t=cp j, n-t+1; end for j=PB(n,n-t+1):t-1 cp j, n-t=cp j+1 , n-t+1 ; end endend%显示编码结果A=;for i=1:n A=A;L(k(i);endcodecell=cell(n,3);codecell

15、=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) )display('编码效率')P=H/lenavcf=;for i=1:n0 cf=cf cell2mat(codecell(find(A=L0(i),3);enddisplay('编码')cfD1=cell2m

16、at(codecell(1,3);D2=cell2mat(codecell(2,3);D3=cell2mat(codecell(3,3);%BSC传输cf0=cf;p=10(-2);%P表示错误概率for i=1:length(cf0)cf1(i)=mod(str2num(cf0(i)+(unidrnd(ceil(1/p)=1),2);%模2加得到传输后的编码delta(i)=cf1(i)-str2num(cf0(i);%作差来计算错误位置endep=find(delta=0);%error position display(length(ep),'错误位数')cf2=;for i=1:length(cf0) cf2=strcat(cf2,num2str(cf1(i);%传输后得到的编码化为字符形式endcf2bsc=cf2; % %解码ncf=length(cf2); df=;m=1;i=1;times=ceil(ncf/max(