霍夫曼编码的分析与实现.doc

《霍夫曼编码的分析与实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息论与编码设计作业霍夫曼编码的分析与实现通信1311刘倩陈青云袁冬梅目录一、设计内容1二、设计原理21、霍夫曼编码步骤：22、霍夫曼编码特点：42.1最佳编码：42.2霍夫曼的显著特点：42.3霍夫曼编码的非唯一性4三、设计步骤51、以框图形式画出哈霍夫曼码过程52、计算平均码长、编码效率、冗余度。5四、霍夫曼编码的MATLAB实现:61、MATLAB编程62、运行结果及分析：7五.分工情况8霍夫曼编码的分析与实现一、设计内容  1、根据霍夫曼编码算法，考虑一个有多种可能的符号（各种符号发生的概率不同的信源）得到

2、霍夫曼编码和码树； 2、 使用MATLAB进行编程，编写的函数具有通用性，理解每个函数的具体意义和适用范围，程序输出显示所有的码字，平均码长，编码效率。 例如:一个有n个符号的信源X，各个符号出现的概率为：P:x1x2x3x4x5x6···例：P(X):0.40，0.18，0.15，0.10，0.07，0.05，0.03，0.02进行霍夫曼编码，计算出平均码长、编码效率、冗余度。  二、设计原理1、霍夫曼编码步骤：（1）将信源消息符号按其出现的概率大小依次排列：P1 ≥ P2 ≥ ··· ≥ Pn 。（2）取两个概

3、率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新的字母的概率，与未分配的二进制符号的字母重新排队。 （3）对重排后的两个概率最小符号重复步骤（2）的过程。 （4）不断继续上述过程，直到最后两个符号配以0和1为止。 （5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字 。Huffman编码的程序流程图：开始输入信源符号对应概率P（i） 否判断P（i）是否>0是否判别概率总和是否<=1是   对概率数组q升序排序用0，1表示概率最小的两个信源符号将数组q前两项加和，得到新的概率序

4、列否否判断信源符号是否只剩两个符号 生成n-1行n列，每个元素含有n个字符的空白矩阵是进行Huffman编码，并完成码字分配计算一个Huffman码字的平均码长结束计算信源熵和编码效率2、霍夫曼编码特点： 2.1最佳编码：能载荷一定的信息量，且码字的平均长度最短，可分离的变长的码字集合称为最佳变长码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字最短，为最佳编码方法。霍夫曼码是用用概率匹配的方法进行信源编码。2.2霍夫曼的显著特点：1.霍夫曼的编码方法保证了概率大的符号对应于短码，概

5、率小的符号度对应于长码，充分利用了短码；2.霍夫曼是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其他终端节点对应的编码的前缀，即霍夫曼编码所得的码字为即时码。  3.霍夫曼编码是一种分组码，各个信源符号都被映射成一组固定次序的码符号。  4.霍夫曼编码是一种唯一可解的码，任何符号序列只能以一种方式译码。注：它可以单个信源符号编码或用L较小的信源序列编码。但是应当注，要达到很高的效率仍然需要按长序列计算，这样才能使平均码字长度降低。编码过程中，当缩减信源的概率分布重新排列时，应使合并得到的概率和

6、尽量处于高的位置，这样可使合并的元素重复编码次数减少，使短码得到充分利用。2.3霍夫曼编码的非唯一性霍夫曼编码方法得到的码并非是唯一的，造成并非唯一的原因是：（1）首先，每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1可以任意的，所以可以得到不同的霍夫曼码，但不会影响码字的长度。（2）对信源进行缩减时两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的霍夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可以获得较小的

7、码方差。  三、设计步骤 1、以框图形式画出哈霍夫曼码过程  霍夫曼编码过程：哈夫曼码树：2、计算平均码长、编码效率、冗余度。  在变字长编码时每个符号的平均码长为： =2.71码元/符号平均信息量就是信息熵为：=0.3×log（0.3）+0.2×log（0.2）+0.18×log（0.18）+0.1×log(0.1)+0.08×log(0.08)+0.07×log(0.07)+0.04×log(0.04)+0.03×log(0.03)=2.66码元/符号   编码效率为： h  冗余度为:四、霍夫曼编码的MATL

8、AB实现: 1、MATLAB编程 p=input('请输入数据:') %提示输入界面   n=length(p); %N取输入行向量P的长度，即需要编码元素个数。for i=1:n     if p(i)<0 %判断输入P矩阵各元素是否全为大于零的有效概率值；fprintf(' 提示：概率值不能小于0!');     p=input('请重新输入数据