基于verilog实现哈夫曼编码的新方法

作者/ 贾先韬 张旭 刘泽曦 山东大学 物理学院(山东 济南 250100)

*大学生集成电路创新创业大赛全国总决赛三等奖

摘要：传统的硬件实现哈夫曼编码的方法主要有：预先构造哈夫曼编码表，编码器通过查表的方法输出哈夫曼编码^[1];编码器动态生成哈夫曼树，通过遍历节点方式获取哈夫曼编码^[2-3]。第一种方法从平均码长角度看，在很多情况下非最优;第二种方法需要生成完整的哈夫曼树，会产生大量的节点，且需遍历哈夫曼树获取哈夫曼编码，资源占用多，实现较为麻烦。本文基于软件实现^[4]时，使用哈夫曼树，会提出一种适用于硬件并行实现的新数据结构——字符池，通过对字符池的频数属性比较和排序来决定各个字符节点在字符池中的归属。配置字符池的同时逐步生成哈夫曼编码，可以提高硬件利用率，并且无需额外操作来提取哈夫曼编码。

引言

　　哈夫曼(Huffman)编码对出现频率较高的字符采用较短的编码，对出现频率较低的字符采用较长的编码，它可以保证平均码长最短，具有较高的编码效率。因而哈夫曼编码被广泛应用于数据压缩领域。已有的硬件实现方法包括预先构造哈夫曼编码表和模仿软件实时生成完整哈夫曼树两种。前一种方法在大多数情况下不是最优编码，后一种方法不仅需要生成大量节点，而且需要额外硬件模块实现遍历节点操作。针对这些问题，本文提出一种新的适用于硬件实现的数据结构——字符池来对输入数据实时生成哈夫曼编码。

1 哈夫曼编码的原理

　　哈夫曼编码是一种不等长编码，根据每个字符出现频率进行编码，每个字符的编码不能是其他字符编码的前缀，所有字符编码总长度相比原码而言将会降低。

2 哈夫曼编码硬件总体实现方案

　　本文采用自顶而下的设计方式。总体框架由一个顶层模块、接收模块、计算模块、输出模块和FIFO模块构成。顶层模块由其余4个模块连接而成，系统总体结构如图1所示。

　　接收模块：接收数据源并分类统计各字符出现的频数，数据接收完成后，接收模块向计算模块发送开始计算信号。计算模块进行计算，生成各字符对应的编码值，做成编码表，结束后向输出模块发送输出信号。最后输出模块通过查表方式输出各字符的编码值以及哈夫曼编码结果。FIFO模块用于接收原始数据和向输出模块提供数据源。

3 实现流程

　　本文使用verilog语言在vivado平台上进行哈夫曼编码硬件模块的实现，选用器件为xc7a100tcsq324-1。

3.1 FIFO模块

　　本文的FIFO模块使用vivado的IP核生成，设计时选择好相应参数配置，生成verilog文件后即可直接调用。

3.2 输入模块

　　使用多个计数器对输入各字符频数以及输入字符总量进行计数，频数被存放在寄存器中，当字符输入结束(例如输入字符总量达到了约定值)时，输入模块向计算模块输出计算开始信号，同时频数寄存器中的数据被并行输出至计算模块。

3.3 计算模块

3.3.1 新数据结构及对应的硬件实现

　　本文基于哈夫曼树的思想构建了新的数据结构——字符池用于硬件实现哈夫曼编码。根据n种字符构建n个字符池和n个字符节点。每个字符池包含一个属性：包含的所有字符的频数之和。每个字符节点包含以下属性：所属字符池序号、自身编码值和自身编码长度。因此，定义n个寄存器记录字符节点对应的字符池序号、n个寄存器记录编码值、n个寄存器记录编码长度以及n个寄存器记录字符池的频数。

3.3.2 哈夫曼编码计算流程

　　进行哈夫曼编码计算时，计算模块通过执行循环操作完成各字符编码的生成以及字符在字符池中的移动。以图2中的实例描述计算流程。

　　图2中共有5种字符，各自频数为：“0”：5，“1”：10，“2”：20，“3”：30，“4”：35。

　　图2(a)为初始化效果，此时每个字符池包含一个字符，每个字符池的频数恰为那个字符的频数;每个字符的编码值和编码长度清零。图2(a)到图2(d)共经过4次循环操作，最终可以从图2(d)中读取出每个字符的编码值和编码长度，“0”编码值为0011，“1”编码值为1011，“2”编码值为111，“3”编码值为01，“4”编码值为0。

　　每次循环操作包含排序、挑选、最小值和次小值求和、频数更新、字符移动、编码值更新及编码长度更新8步。其中前4步按顺序完成，然后同时完成后4步。总循环次数由字符种类数控制。

　　排序操作功能是将每个节点池的频数从小到大进行排序，本文借鉴了参考文献[5]中的方法，硬件实现时通过构建比较器阵列将每两个数两两比较，再通过加法器对每个字符频数的比较结果求和。对一个字符频数，若它小于另一个字符的频数，则相应结果为0，否则为1。那么通过指定字符频数与其他字符频数的比较结果之和可以得知它的频数在所有频数中的位置。

　　挑选操作是将排序操作中比较结果为0和1对应的字符频数选出，它们代表最小频数和次小频数，挑选操作同时挑选出这两个频数对应的字符池ID。硬件实现时构建多个比较器，将比较结果之和与0和1比较，再通过多路复用器从多个频数和字符池ID中准确挑选出所需的值。例如在图2(b)中，挑选出的两个频数为15和20，它们对应字符池ID为1和2。

　　接下来的最小值和次小值求和操作就是将挑选操作挑选出的最小频数和次小频数求和，然后输出。此步骤硬件实现时需要一个多位加法器。例如在图2(b)中，求和值为15+20=35。

　　频数更新操作指根据挑选操作挑选出的结果进行字符池频数的更新。按照本文约定方法，将最小频数对应字符池的频数更新成无效值，无效值应大于所有可能的频数，它的目的是避免此字符池的频数被接下来的循环挑选操作挑选出。本文将次小频数对应字符池的频数以求和操作的加法结果替代。例如图2(c)中1号字符池频数变成100，2号字符池频数变成35。

　　字符移动操作指将特定字符从一个字符池移动到另一个字符池中。按照本文约定方法，将最小频数对应字符池的所有字符移动到次小频数对应字符池中。例如将图2(c)和图2(b)对比可发现1号字符池的字符“0”和“1”被移动到了2号字符池中。

　　编码值、编码长度更新操作中，按本文约定方法，将最小频数对应字符池的所有字符编码值左移1位并在最后一位补0，长度加1。将次小频数对应字符池的所有字符编码值左移1位并在最后一位补1，长度加1。将图2(c)和图2(b)对比可看出，字符“0”的编码值从0变成00，“1”编码值从1变成10，“2”编码值从无变成1。

　　所有循环结束后编码表已生成，计算模块向输出模块发送计算结束信号。

3.4 输出模块

　　输出模块负责从FIFO中读取出原始数据、从编码表中获取编码值，再通过并串转换以一位数据口首先输出各字符编码值，再输出字符串编码结果。

4 仿真和调试

　　本文使用vivado对顶层模块进行综合实现，通过实现后仿真验证 结果正确性。

　　图3展示了模块输入时序。本文测试时以huf_in_start高电平脉冲标志数据输入开始，实际数据以4为并口输入，测试字符范围为“0”至“9”。

　　图4展示了模块输出时序。通过huf_out_start高电平脉冲表明输出开始。首先输出各字符编码序列，包含4bit编码长度和实际编码值，然后输出原始字符串的编码值。huf_out_end高电平脉冲表明输出结束。

　　图5为vivado控制台输出，它展示了各字符编码值以及原始字符和testbench进行的解码字符比较，说明模块正常运行。

5 结论

　　本文提出了一种新的在硬件上实现哈夫曼编码的方法，利用本文的字符池数据结构，对每次输入的数据实时生成哈夫曼编码表，从平均码长角度保证了编码的最优，同时避免了生成完整的哈夫曼树，减少了资源占用，并避免了遍历哈夫曼树所需的额外操作，实现方便快捷。

　　参考文献：

　　[1]邓丽娟,田金文,柳健,等.哈夫曼编码器IP核的设计与实现[J].微电子学与计算机,2005(02):9-12.

　　[2]张颖超.基于FPGA的Huffman编码并行实现及高速存储系统设计[D].长安大学,2015.

　　[3]曾英,邓曙光.基于FPGA的Huffman编码器的设计[J].湖南城市学院学报(自然科学版), 2014(01):32-35.

　　[4]杨兰.基于C语言的哈夫曼编码的实现[J].软件导刊,2012(09):40-42.

　　[5]师廷伟,金长江.基于FPGA的并行全比较排序算法[J].数字技术与应用,2013(10):126-127.

　　本文来源于《电子产品世界》2017年第12期第40页，欢迎您写论文时引用，并注明出处。