哈夫曼编码 静态哈夫曼编码的快速硬件实现

王李成泽石奥开李菁

中国电子科技大学(四川成都610054)

首届(2016-2017)全国本科集成电路创新创业大赛全国总决赛FPGA设计方向二等奖

本文提出的方案主要功能是连续接收0-9之间的256个任意值，对这256个数据完成输入数据元素的霍夫曼编码，最后先输出0-9个元素对应的编码，再根据输入数据序列输出每个数据对应的霍夫曼编码。

1系统设计方案

霍夫曼编码的基本思想是用较短的编码来表示出现概率较高的数据，而用较长的编码来表示出现概率较低的数据。通常的做法是根据输入数据的频率构造一个霍夫曼树，然后通过遍历树中的每个节点来生成叶节点，即输入数据的霍夫曼码。但是传统的方法有两大缺陷:一是构造Huffman树时，每次生成一个父节点，都会排序一次，不仅耗时，而且消耗大量硬件资源；第二，编码操作在霍夫曼二叉树生成后进行。事实上，每次生成父节点时，父节点中包含的叶节点的霍夫曼编码的一位已经被确定。因此，如果采用传统的方法，必须节省整个二叉树，生成二叉树的时间没有得到有效利用，浪费了更多的资源和时间。

基于以上两点，本文提出以下改进方案，操作步骤如下:

(1)统计所有输入数据元素的频率，依次将输入数据存入FIFO。

(2)将所有频率数据排序一次，给出排序后的频率数据。

(3)根据有序频率数据生成霍夫曼二叉树，每次生成一个父节点时，确定父节点中包含的叶节点的霍夫曼码的一位，并在构建二叉树时生成所有叶节点的霍夫曼码。

(4)根据生成的霍夫曼码，先依次输出0~9对应的码，然后根据输入的数据依次输出每个数据对应的霍夫曼码。

图1系统框图

对应于该方案的系统框图如图1所示，其中每个模块对应于上述操作步骤。

2系统实施

本部分将分模块介绍整个系统的实现方案。因为统计模块和输出模块没有优化，所以只介绍排序模块、二叉树和代码生成模块中使用的算法。

2.1分类模块

排序模块的主要功能是实现10个频率数据的排序操作。常用的排序算法有冒泡排序、快速排序、合并排序等。考虑到硬件实现的难度、分拣周期的数量以及消耗的硬件资源，我们选择使用分拣网络进行分拣。

图2奇偶校验排序网络

分类网络有很多种。本文主要使用的排序网络是奇偶排序网络，如图2所示，是一个四输入奇偶排序网络。图中有四条横线，分别代表四个网络a1、a2、a3和a4。网络之间的垂直连接线表示比较操作，在每次比较中，大的数字被切换到网络的上层，小的数字被切换到网络的下层。在第一个时钟周期，a1和a2、a3和a4同时比较排序，即均匀排序；在第二时钟周期中，a2和a3同时被比较和排序，即奇数排序；在第三时钟周期中，a1和a2、a3和a4同时被比较和排序；并且在第四时钟周期中，a2和a3被比较和排序。四个时钟周期后，四个网络上的数据将从大到小排列。

同样，使用排序网络对10个数据进行排序时，总共需要10个网络，消耗10个时钟周期。偶数排序和奇数排序交替进行5次，其中偶数排序同时进行5次比较运算，奇数排序同时进行4次比较运算。因此，分拣网络充分利用了硬件并行的特点，有利于缩短分拣周期。而且偶排序和奇排序的比较操作每次都是一样的，所以偶排序模块和奇排序模块可以复用，有利于减少硬件资源的消耗，整个排序模块只消耗9个比较器。

2.2二叉树和代码生成模块

排序操作完成后，为了更快地完成输入数据元素的霍夫曼编码，本文提出了二叉树生成和编码同时进行的方案，下面将结合实例给出该方案的具体实现过程。

图3二叉树生成和编码

这个方案的一个例子如图3所示。图中有五组寄存器:(1)叶节点寄存器a0~a4，存储元素0~4及其频率从小到大。例如，a0中的“4:2”表示元素4的频率为2。(2)父节点寄存器b0~b2按照父节点的生成顺序依次存储生成的父节点频率，因此父节点频率也是从小到大排列的。为了避免影响指针搜索的最小两个频率，将其初始值设置为一个较大的数，这里为255；(3)指针pta0、pta1、ptb0和ptb1指向要比较的四个数字。通过比较这四个数字，我们可以在所有频率中找到最小的两个频率，并生成一个父节点。可以用反证法证明，最小的两个频率一定在这四个指针所指的数据中。比较方法是比较pta0和ptb1指向的数字，比较pta1和ptb0指向的数字。根据比较结果，可以确定最小的两个频率。因为两次比较是同时进行的，所以只需要一次比较时间就可以确定最小的两个频率值，也避免了重新排序。每次比较后，指针会根据比较结果移动。(4)叶节点码寄存器，如a0~a4下面两行数据所示，用于存储霍夫曼码和叶节点的码长。(5)父节点中包含的叶节点寄存器，如图中指针上方的数据所示，用于存储父节点中包含的叶节点。如果b0的第00位为1，则表示其中包含的叶节点为元素0。

在初始状态下，每个寄存器的值如图3 (a)所示。通过比较四个指针，可以确定最小的两个频率是4和2。比较完成后，指针移动到图(b)所示的位置，频率4和2相结合，生成父节点6，存储在第一个父节点寄存器b0中。相应地，父节点的叶节点寄存器被修改为“11000”，表示父节点包含三个和四个。因此，获得了第一次比较完成后的图3(b)所示的状态。在这种状态下，类似地，根据四个指针确定最小的两个频率值，移动指针，生成父节点，修改父节点寄存器及其对应的叶节点寄存器，修改叶节点对应的编码寄存器。如此反复，直到只剩下两个节点，剩下的节点直接赋码。最后，修改相应的编码寄存器，得到每个数据元素对应的霍夫曼码，如图3(c)所示。图中，节点a0对应的叶节点码为“0000”，对应的长度为3，表示元素4的霍夫曼码为“000”。

从上述过程可以看出，这种方案的优势在于生成二叉树的同时生成数据元素的代码，因此代码生成不需要额外的时间，有效减少了编码周期的总数，生成二叉树时不需要保存整个二叉树。与传统方案相比，只需要保存父节点中包含的叶节点，减少了寄存器的使用，进一步降低了硬件消耗。

图4模拟时序图

3硬件实现

基于上述系统设计方案，本文采用Xilinx的Vivado软件平台进行综合实现。使用的芯片型号为xc7a100tcsg324-1。根据仿真结果，该设计从数据输入结束到编码完成总共消耗32个时钟周期，最差情况下运行频率达到250MHz。如图4所示，仿真时序图显示data_in为输入数据，output_data为编码后的串行数据输出。起始信号有效后，连续输入256个数据，系统根据输入的数据完成编码。最后，霍夫曼编码和编码的数据序列通过output_start信号串行输出，输出后的一个时钟周期内ouput _ done信号被拉高。

参考文献:

王芳秀，周康。引用该论文王志平，王志平，王志平.武汉轻工业学院学报，2011，30(4):45-48。

吴、。引用该论文王志平，王志平，王志平.计算机技术与发展，2009，19(10):51-53。

[3] Matai J，Kim J Y，Kastner R .能效规范霍夫曼编码[C]// IEEE，特定应用系统、架构和处理器国际会议。IEEE，2014:202-209。

娜娜。霍夫曼树算法的改进[J]。《计算机知识与技术》，2010(29):8224-8226。

[5]托马斯。科曼。算法导论[M]。机械工业出版社，2007。