作者/王朝驰 李成泽 史傲凯 李靖 电子科技大学(四川 成都 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.
