实验二、Huffman编码

信息论与编码实验报告信息学院10电子A班级第组姓名同组成员实验名称实验二、Huffman编码实验设备（1）计算机（2）所用软件：Matlab实验目的了解Huffman编码的基本原理及其特点；熟练掌握Huffman编码的方法步骤；利用Matlab编写二元Huffman编码的程序；验证程序的正确性。实验内容（1）根据Huffman编码的方法步骤，用Matlab编写二元Huffman编码的程序；（2）用习题4.8和例4.5验证程序的正确性。实验报告要求1、简要总结Huffman编码的基本原理及特点；2、写出Huffman编码基本步骤，画出实现Huffman编码的程序流程图；3、实现二元Huffman码编码的Matlab源程序；4、讨论不同的Huffman编码的平均码长如何变化，码字长度偏离平均码长对编码性能的影响。5、实验报告在实验后一周内交给老师，报告单一律用16开大小的纸写，以此单为封面，装订成册。完成时间：2012年12月22日1、简要总结Huffman编码的基本原理及特点；哈夫曼码是用概率匹配方法进行信源编码。它有两个明显的特点：一是哈夫曼的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，从而保证了哈夫曼码是即时码特点：（1）它是一种分组码；（2）它是一种唯一可译码；（3）它是一种即时码。2、写出Huffman编码基本步骤，画出实现Huffman编码的程序流程图；步骤进行：1）将信号源的符号按照出现概率递减的顺序排列。2）将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。3）重复进行步骤1和2直到概率相加的结果等于1为止。4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。5）记录下概率为1处到当前信号源符号之间的0，1序列，从而得到每个符号的编码。3、实现二元Huffman码编码的Matlab源程序；probabilities=[0.08560.01390.02790.03780.13040.02890.01990.05280.06270.00130.00420.03390.02490.07070.07970.01990.00120.06770.06070.10450.02490.00920.01490.00170.01990.0008];probabilities=probabilities/sum(probabilities);forindex=1:length(probabilities)codewords{index}=[];set_contents{index}=index;set_probabilities(index)=probabilities(index);enddisp('-------------------------------------------------------------------------');disp('Thesetsofsymbolsandtheirprobabilitiesare:')forset_index=1:length(set_probabilities)disp([num2str(set_probabilities(set_index)),'',num2str(set_contents{set_index})]);endwhilelength(set_contents)1[temp,sorted_indices]=sort(set_probabilities);zero_set=set_contents{sorted_indices(1)};zero_probability=set_probabilities(sorted_indices(1));forcodeword_index=1:length(zero_set)codewords{zero_set(codeword_index)}=[codewords{zero_set(codeword_index)},0];endone_set=set_contents{sorted_indices(2)};one_probability=set_probabilities(sorted_indices(2));forcodeword_index=1:length(one_set)codewords{one_set(codeword_index)}=[codewords{one_set(codeword_index)},1];enddisp('Thesymbols,theirprobabilitiesandtheallocatedbitsare:');forindex=1:length(codewords)disp([num2str(index),'',num2str(probabilities(index)),'',num2str(codewords{index})]);endset_contents(sorted_indices(1:2))=[];set_contents{length(set_contents)+1}=[zero_set,one_set];set_probabilities(sorted_indices(1:2))=[];set_probabilities(length(set_probabilities)+1)=zero_probability+one_probability;disp('Thesetsandtheirprobabilitiesare:')forset_index=1:length(set_probabilities)disp([num2str(set_probabilities(set_index)),'',num2str(set_contents{set_index})]);endenddisp('-------------------------------------------------------------------------');disp('Thesymbols,theirprobabilitiesandtheallocatedHuffmancodewordsare:');forindex=1:length(codewords)disp([num2str(index),'',num2str(probabilities(index)),'',num2str(codewords{index}(length(codewords{index}):-1:1))]);endentropy=sum(probabilities.*log2(1./probabilities));av_length=0;forindex=1:length(codewords)av_length=av_length+probabilities(index)*length(codewords{index});enddisp(['Thesymbolentropyis:',num2str(entropy)]);disp(['TheaverageHuffmancodewordlengthis:',num2str(av_length)]);disp(['TheHuffmancodingrateis:',num2str(entropy/av_length)]);4、讨论不同的Huffman编码的平均码长如何变化，码字长度偏离平均码长对编码性能的影响。对于不同方式的huffman编码，其平均码长保持不变。若码字长度偏离平均码长太大，则需要大量的存储设备来缓冲码字长度的差异，若存储量不够时，可能有时取空，有时溢出。不同的Huffman编码的平均码长不变，码字长度偏离平均码长越小，那么这种码长方差就越小，编码器和解码器就越简单。在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,应使合并后的新符号尽可能排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。