霍夫曼编码含源程序.docx

1、霍夫曼编码含源程序多媒体技术基础实验报告 霍夫曼编码学院：电子工程与光电技术学院 专业：电子信息工程姓名： 学号： 任课老师：康其桔实验时间：一、实验内容及要求 1、使用Matlab编程实现霍夫曼编码2、通过键盘输入字符串3、在屏幕上显示编码结果二、实验原理 霍夫曼编码是霍夫曼在1952年提出和描述的“从下到上”的熵编码方法。根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少。其基本步骤为：(1) 将压缩的各字符的出现概率按减少(或增加)的顺序进行排列。(2) 将两个最小的概率进行组合相加得到一个新概率将这一新概率与其它概率

2、一起继续执行1 和2 的操作直至最后概率为1.0。(3) 对每对组合中的概率较大者指定为1,较小者指定为0。(4) 画出由每个信源符号概率到1.0处的路径记下路径的1和0。(5) 对每个信源符号由从右到左写出1/0序列，对概率较高的标1，对概率较低的标0(或对概率较高的标0，对概率较低的标1)，就得到了对应的Huffman码。 下面举个例子来说明霍夫曼编码的具体过程。 设需要编码的信息为：BACDEBACDEBACDEBADEBAEBABABABB,统计各个字符出现的次数分别为B(10次)、A(8次)、C(3次)、D(4次)、E(5次)。各个字符出现的概率为B(10/30)、A(8/30)、E

3、(5/30)、D(4/30)、C(3/30)。霍夫曼编码的过程如下： B(10/30) A(8/30) E(5/30) D(4/30) C(3/30) 霍夫曼编码后平均码长为。而信源熵。由此，我们可以看出，霍夫曼编码结果已经很接近理想信源熵。三、设计方案 设计的流程图如下：四、各模块设计（一）读入字符串并去除空格 在Matalb中使用语句inputstring=input(请输入需要编码的字符:,s)，输入的字符串存入char型数组inputstring中。 去除空格的思想为：输出的inputletters数组存储的是输入字符串去除空格后的字符集的ASCII值，如果需要显示字符需要用语句：di

4、sp(char(inputletters)。这一部分代码如下：inputstring=input(请输入需要编码的字符:,s);%输入字符并存储 spacenumber=0; %存储空格数目 for i=1:length(inputstring) if abs(inputstring(i)=32 spacenumber=spacenumber+1; continue else inputletters(i-spacenumber)=inputstring(i); endenddisp(去除空格后字符为：,char(inputletters)（二）统计字符种类及概率统计字符的种类，需要去除输入字

5、符中的重复字符，并存入数组letters中，其基本流程图如下：这一部分的程序如下：letters(1)=inputletters(1);for m=2:length(inputletters) repeatn=0; %定义一个数记录是否有重复 for n=1:length(letters) if letters(n)=inputletters(m) repeatn=repeatn+1; end end if repeatn=0 letters(length(letters)+1)=inputletters(m); endend概率的统计即是统计letters中每个元素在inputletters

6、出现的次数，除以总次数即可得到每个字符出现的概率。概率统计的程序如下：for p=1:length(letters) repeatn=0; %计算重复次数 for q=1:length(inputletters) if letters(p)=inputletters(q) repeatn=repeatn+1; end end letterp(p)=repeatn/length(inputletters);end对得到概率letterp进行降序排序得到huffmanprob，并使字符集与概率相对应生成字符集huffamnletters。这一过程主要是为了方便输出字符集的输出。这一部分的程序如下：

7、huffmanprob,sort_index = sort(letterp); %用来霍夫曼编码的概率huffmanprob=(fliplr(huffmanprob);sort_index=fliplr(sort_index);for i=1:length(huffmanprob) huffmanletters(i)=letters(sort_index(i); %用来霍夫曼编码的字符集enddisp(-字符及概率-)for i= 1:length(huffmanletters) fprintf(字符：%-4s概率：%5.4fn,char(huffmanletters(i),huffmanpr

8、ob(i)end（三）霍夫曼编码 根据实验原理，在使用Matlab编程实现霍夫曼编码的过程中，需要定义一个元胞数组huffmantabel来存储霍夫曼码表。这个元胞数组的长度与huffman -letters中字符相对应。同时还需定义一个元胞数组numorder来存储每个字符的概率在原概率矩阵中的位置。其基本流程图如下： while length(numorder)1 temp,ind=sort(huffmanprob); pminorder=numorderind(1); pmin=huffmanprob(ind(1); pnminorder=numorderind(2); pnmin=hu

9、ffmanprob(ind(2); for i=1:length(pminorder) huffmantabelpminorder(i)=1,huffmantabelpminorder(i); end for j=1:length(pnminorder) huffmantabelpnminorder(j)=0,huffmantabelpnminorder(j); end numorder(ind(1:2)=; numorderlength(numorder)+1=pminorder,pnminorder; huffmanprob(ind(1:2)=; huffmanprob(length(hu

10、ffmanprob)+1)=pmin+pnmin;end（四）霍夫曼解码在进行霍夫曼解码的过程中，需要将霍夫曼码序列中的元素与霍夫曼码表中的元素进行比较，若一样则输出相对应的字符。由于考虑到霍夫曼码长可变，我们可以归纳每个霍夫曼码的特点，每个霍夫曼码可以用其码长以及十进制数值唯一表示，将其十进制及码长存入一个新的元胞数组huffmandec中，将霍夫曼码元中的一位位取出，算出其十进制对应的值tempsum及二进制长度i存入一个数组A中，使用语句c2=find(cellfun(t)all(A(:)=t(:),huffmandec);即可找到元胞数组huffmandec中与数组A相同的数组的位置。

11、利用这个次序即可找到对应的huffmanletters数组中的字符删除后的数组重新赋值给huffmanletter- s，将这个字符存入decodeletters，将刚刚统计的i个二进制删除并用语句isequal(decodeletters,inputletters)判断解码输出的结果与输入是否相同。将二进制霍夫曼码表转变为十进制霍夫曼码表并与长度一起存入元胞数组的语句如下：for i=1:length(huffmanletters) temparray=huffmantabeli; %temparray是一个临时的矩阵 huffmandeci=bin2dec(num2str(temparra

12、y),length(temparray); %用霍夫曼码表的十进制值及长度形成霍夫曼码的唯一标志end实现霍夫曼解码的流程图如下：这一过程所对应的Matlab源程序为：decodeletters=;while isempty(huffmancodep)=0 tempsum=0; for i=1:length(huffmancodep) tempsum=tempsum*2+huffmancodep(i); A=tempsum i; c2=find(cellfun(t)all(A(:)=t(:),huffmandec); if isempty(c2)=0 decodeletters=decodel

13、etters huffmanletters(c2(1); huffmancodep(1:i)=; break; end endendif isequal(decodeletters,inputletters)=1 disp(经比较解码输出结果与输入相同)end在完成霍夫曼解码之后经过简单的计算即可求出信源熵，压缩比，以及平均码长。五、结果演示 以书本例2.2为例，运行程序，输入A（15个）、B（7个）、C（6个）、D（6个）、E（5个），理论结果为 A（0） B（1 1 1）C（1 1 0）D（1 0 1）E（1 0 0）压缩比为：1.34信源熵为2.1857平均码长为：2.2308而经过程序

14、计算的结果为：经比较，所得结果与例2.2结果相同，即程序运行结果正确六、源程序%代码文件:myhuffman.m%目的：从键盘输入字符集使用huffman编码并解码% 更改记录% Date Programmer Description of change% = = =% 5/11 Original code%重要变量定义：%inputstring:输入字符串%inputletters:除去空格后的字符串存入的数组%huffmanletters:用来霍夫曼编码的字符集%huffmanprob:字符集相对应的概率%huffmantabel:霍夫曼码表，与字符集顺序对应%huffmancode:霍夫

15、曼编码结果%decodeletters:霍夫曼解码输出的字符集%compratio:压缩比 %-开始编码- clcclear allinputstring=input(请输入需要编码的字符:,s);%输入字符并存储 spacenumber=0; %存储空格数目 %=去除空格= for i=1:length(inputstring) if abs(inputstring(i)=32 spacenumber=spacenumber+1; continue else inputletters(i-spacenumber)=inputstring(i); endenddisp(去除空格后字符为：,ch

16、ar(inputletters)%fprintf(去除空格后字符：%s,char(letters) %=统计输入字符种类= letters(1)=inputletters(1);for m=2:length(inputletters) repeatn=0; %定义一个数记录是否有重复 for n=1:length(letters) if letters(n)=inputletters(m) repeatn=repeatn+1; end end if repeatn=0 letters(length(letters)+1)=inputletters(m); endend%disp(输入无重复字符

17、为：,char(letters) %=统计概率= for p=1:length(letters) repeatn=0; %计算重复次数 for q=1:length(inputletters) if letters(p)=inputletters(q) repeatn=repeatn+1; end end letterp(p)=repeatn/length(inputletters);end %=排序并对应= huffmanprob,sort_index = sort(letterp); %用来霍夫曼编码的概率huffmanprob=(fliplr(huffmanprob);sort_inde

18、x=fliplr(sort_index);for i=1:length(huffmanprob) huffmanletters(i)=letters(sort_index(i); %用来霍夫曼编码的字符集end %=输出字符及概率= disp(-字符及概率-)for i= 1:length(huffmanletters) fprintf(字符：%-4s概率：%5.4fn,char(huffmanletters(i),huffmanprob(i)end %=开始霍夫曼编码= huffmantabel=cell(1,length(huffmanletters); %定义元胞数组用来存储huffma

19、n码表 numorder_temp=1:length(huffmanletters);numorder=num2cell(numorder_temp); %将1-.这一系列数转变为元胞数组while length(numorder)1 temp,ind=sort(huffmanprob); %排序，不需要结果，只需要最小概率在原概率中位置 pminorder=numorderind(1); %根据ind得出最小概率元胞数组对应位置，此位置对应编码字符 pmin=huffmanprob(ind(1); pnminorder=numorderind(2); pnmin=huffmanprob(in

20、d(2); for i=1:length(pminorder) huffmantabelpminorder(i)=1,huffmantabelpminorder(i); end for j=1:length(pnminorder) huffmantabelpnminorder(j)=0,huffmantabelpnminorder(j); end numorder(ind(1:2)=; numorderlength(numorder)+1=pminorder,pnminorder; huffmanprob(ind(1:2)=; huffmanprob(length(huffmanprob)+1

21、)=pmin+pnmin;end %=输出霍夫曼码表= disp(-霍夫曼码表-)for i=1:length(huffma nletters) %fprintf(字符：%-4s概率：%fn,char(huffmanletters(i),num2str(huffmantabeli) disp(字母： char(huffmanletters(i) 霍夫曼码： num2str(huffmantabeli)end %=形成霍夫曼码= disp(-霍夫曼码-)huffmancode=; %huffmancode用来存储huffman码for i=1:length(inputletters) c1=fi

22、nd(huffmanletters=inputletters(i); huffmancode=huffmancode,huffmantabelc1(1); endfor i=1:ceil(length(huffmancode)/10)disp(num2str(huffmancode(i-1)*20+1:min(i*20,length(huffmancode)end %=霍夫曼解码= huffmancodep=huffmancode;%将十进制霍夫曼码组元胞数组元素变成十进制数组方便解码for i=1:length(huffmanletters) temparray=huffmantabeli;

23、 %temparray是一个临时的矩阵 huffmandeci=bin2dec(num2str(temparray),length(temparray); %用霍夫曼码表的十进制值及长度形成霍夫曼码的唯一标志end%开始解码decodeletters=;while isempty(huffmancodep)=0 tempsum=0; for i=1:length(huffmancodep) tempsum=tempsum*2+huffmancodep(i); A=tempsum i; c2=find(cellfun(t)all(A(:)=t(:),huffmandec); if isempty

24、(c2)=0 decodeletters=decodeletters huffmanletters(c2(1); huffmancodep(1:i)=; break; end endenddisp(-霍夫曼解码-)disp(char(decodeletters)%判断解码结果与输入是否相同if isequal(decodeletters,inputletters)=1 disp(经比较解码输出结果与输入相同)end %=计算压缩比= disp(-压缩比-)bitsone=ceil(log2(length(huffmanletters);%一个字符需要用几位二进制表示bitsrequired=length(inputletters)*bitsone; %理论上需要的总二进制位数bitsactual=length(huffmancode); %huffman编码用到的二进制位数compratio=bitsrequired/bitsactual; %压缩比fprintf(压缩比：%5.4fn,compratio)Welcome ToDownload !欢迎您的下载，资料仅供参考！