电子产品世界

作者/王朝驰 李成泽 史傲凯 李靖 电子科技大学(四川 成都 610054)

第一届(2016-2017)全国大学生集成电路创新创业大赛全国总决赛FPGA设计方向二等奖

本文所提出的方案的主要功能是连续接收256个0~9之间的任意数值，针对这256个数据完成输入数据元素的哈夫曼编码，最后先输出0~9元素对应的编码，再按照输入数据顺序输出各数据对应的哈夫曼编码。

　　1 系统设计方案

　　哈夫曼编码的基本思想是将出现概率较大的数据用较短的编码表示，而将出现概率较小的数据用较长的编码表示。通常的做法是先根据输入数据的频次构造一棵哈夫曼树，再通过遍历树中的每一个节点来生成叶子节点即输入数据的哈夫曼编码。但是传统的方法存在两个比较大的缺陷：一是在构造哈夫曼树时，每次生成一个父节点都会进行一次排序操作，这样的多次排序操作不仅会花费大量的时间，也会耗费大量的硬件资源;二是编码操作是在哈夫曼二叉树生成之后进行，其实每次当一个父节点生成的时候，该父节点包含的叶子节点的哈夫曼编码的一个比特就已经确定了，所以如果采用传统的方法，就必须要保存整棵二叉树，并且没有有效利用生成二叉树的这段时间，这样做也浪费了更多的资源和更多的时间。

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

　　(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个时钟周期，偶排序和奇排序交替进行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的第0bit为1，说明它包含的叶子节点为元素0。

　　初始状态下，各寄存器的值如图3中(a)所示，通过四个指针进行比较可以确定最小的两个频次为4和2，比较完成后指针发生移动到如图(b)所示的位置，并且频次4和2合并生成父节点6，存储到第一个父节点寄存器b0中，对应的将该父节点的叶子节点寄存器修改为“11000”，表示该父节点包含3和4两个叶子节点，最后对两个叶子节点分别分配编码1和0，写入到对应的编码寄存器并修改长度值。由此，得到图3(b)中所示的第一次比较完成后的状态。在该状态下，同样的，根据四个指针确定最小的两个频次值，移动指针，生成父节点，修改父节点寄存器和其对应的叶子节点寄存器，修改叶子节点对应的编码寄存器。如此循环往复，直到最后只剩下两个节点，对剩下的节点直接分配编码，最后再修改对应的编码寄存器，即可得到各数据元素对应的哈夫曼编码，如图3(c)所示，图中，节点a0对应的叶节点编码为“00000”，对应长度为3，表示元素4的哈夫曼编码为“000”。

　　从以上过程中可以看出，该方案的优点在于生成二叉树的同时生成数据元素的编码，所以生成编码不需要额外的时间，有效的减小了编码总周期数，并且生成二叉树时不需要保存整棵二叉树，和传统方案相比，只需要保存父节点所包含的叶子节点，减少了寄存器的使用，进一步减小了硬件消耗。

　　图4 仿真时序图

　　3 硬件实现

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

　　参考文献：

　　[1]王防修,周康.基于二叉排序树的哈夫曼编码[J].武汉轻工大学学报,2011,30(4):45-48.

　　[2]吴晨晖,王映辉.一种基于自顶向下的哈夫曼编码方法[J].计算机技术与发展,2009,19(10):51-53.

　　[3] Matai J, Kim J Y, Kastner R. Energy efficient canonical huffman encoding[C]// IEEE, International Conference on Application-Specific Systems, Architectures and Processors. IEEE, 2014:202-209.

　　[4]谢娜.哈夫曼树算法的改进[J].电脑知识与技术,2010(29):8224-8226.

　　[5] ThomasH.Cormen.算法导论[M].机械工业出版社,2007.

关键词： 哈夫曼编码 FPGA