Xilinx哈夫曼编码系统设计　

作者 孟欢 包海燕 潘飞 电子科技大学 微电子与固体电子学院(四川 成都 610054)

*集成电路创新创业大赛三等奖

孟欢(1991-)，女，硕士生，研究方向：数字系统设计。

摘要：在图像处理、文件传真、视频压缩编码中，哈夫曼编码是最常用的一种编码方式。本文设计并实现了对一段数字序列进行哈夫曼编码并将编码结果串行输出的电路模块，电路由输入数据的排序、数据的哈夫曼编码、数据序列编码的结果输出三个核心模块组成，在Xilinx平台上通过硬件描述语言实现该电路。仿真结果表明，该电路编码正确，并具有较高的工作频率和编码效率。

引言

　　哈夫曼编码是一种可变字长的无损编码方式。对于出现概率大的元素编以短字长的码，对于出现概率小的元素编以长字长的码，来实现平均码长最短。多媒体技术的广泛应用导致数据量的迅速增大，对哈夫曼编码在速度上有了更高的需求。利用硬件设计的大流量和并行性处理的优势，可以大大地提高编码效率和传输速度。哈夫曼编码的核心即建立最优二叉树，各元素的路径就是它所对应的编码结果。主要内容包括数据的排序和元素的编码两个方面。

　　本文是完全在硬件条件下实现哈夫曼编码设计的，在排序部分采用流水线结构，通过流水线实现对数据频数比较，控制数据按照频数大小由小到大排序。在编码模块创新性地采用自顶而下的查找方式，由状态机寻址得到父节点的哈夫曼编码，进而得到左右子节点的哈夫曼编码结果。在输出模块中通过4个寄存器对编码结果进行缓存，控制寄存器读写指针进行编码结果的缓存与输出，保证数据输出的连续性。

1 电路总体结构功能框图

　　利用vivado的设计平台^[1]，以xc7a100tcg324-1作为目标芯片，对输入的数据序列进行哈夫曼编码及输出，设计电路。电路的接口时序如图1所示。

　　1)复位结束，在开始信号start产生后，将一段数字序列(256个0~9的数据元素)输入电路进行哈夫曼编码，data_in的数据宽度为4，输入需要256个时钟周期。

　　2)在编码完成后，产生output_start信号，开始串行输出结果output_data。

　　3)output_data数据包含2个部分。先输出0~9元素对应的编码结果，接着输出数据序列的哈夫曼编码，输出完毕后产生output_done信号。

　　整体结构框图如图2所示。电路主要包括：

　　do_cnt：对输入数据进行统计和存储，输出各元素的频数。

　　hfm_build：完成元素排序。根据输入的频数大小，输出各节点元素的排序结果。

　　hfm_code：数据编码模块。根据hfm_build输出的元素排序结果，自顶向下完成0到9这10个元素的哈夫曼编码。

　　hfm_out：编码输出模块。对编码结果进行单比特的连续输出。

　　output_data：数据输出格式。使用brk信号作为0~9元素的编码输出和序列编码输出的分隔，此时输出为0，之后输出数据序列对应的编码即图中ram_data_out信号，也就是序列对应的编码。所有的编码结果都是先输出低位再输出高位。

1.1 数据排序模块

　　统计部分结束之后需要对数据进行排序，根据输入数据各元素的频次大小，对数据进行排序。该部分主要采用流水线的设计思路，当数据和频次进入排序模块之后，与模块内已经进来的所有数据的频次进行比较，输出频数较大的数据，寄存频数较小的数据。流水线单级结构RTL级电路^[2]设计如图3所示。in_count和in_data为频数和对应元素的输入端，out_count和out_data分别对应频数和对应元素的输出端。

　　10个元素对应18个子节点，要完成对二叉树18个子节点的排序，则总的排序电路由18个单级排序结构组成，根据哈夫曼编码的性质，本设计将每次排序得到的最小两个元素的频数相加作为新元素的频数。例如频数最小的两个元素为9和5，作为左右子节点，父节点对应的频数为9和5的频数之和，其对应的元素为10，生成的父节点依次为11、12....17，新生成的父结点与剩下的元素进行新一轮的排序，而已经比较出两个最小频数的元素，不再参与排序。排序结构的各级输入通过计数器来控制。排序完以后，取每级寄存器中的元素bit0~bit17，即18个节点按照频数由小到大排序的元素序列，输出给编码模块。

1.2 数据编码模块

　　该部分设计主要包括编码FSM、状态控制模块、计数模块、数据编码模块和流水线译码输出模块，其中zero_flag为数据频数为0的标志信号。数据编码模块结构框图如图4所示。

　　根据排序模块的规律，bit0和bit1的父节点是元素10，bit2和bit3的父节点是元素11，bit4和bit5的父节点是元素12，bit6和bit7的父节点是元素13，bit8和bit9的父节点是元素14，bit10和bit11的父节点是元素15，bit12和bit13的父节点是元素16，bit14和bit15的父节点是元素17，bit16和bit17的父节点是根节点。根据哈夫曼树的特点，父节点的编码为xxxxxxxxx，则左节点的哈夫曼编码为xxxxxxxx0，右节点的哈夫曼编码为xxxxxxxx1。

　　编码FSM依次控制输出父节点17至父节点10，首先当输出父节点17时，它为根节点的左节点或右节点，通过查找到排序结果中的对应位置bit16或者bit17，假定bit16的编码为0，bit17的编码为1，则父节点17的编码可以确定，那么它左节点bit14，右节点bit15的编码也就确定了。当编码FSM输出父节点10时，通过查找确定元素10的编码，那么bit0和bit1作为元素10的左右节点，编码结果同样也可以确定。至此，数据0~17对应的code0~code17都已确定。

　　本文设计了流水线比较输出电路来确定数据0-9对应的哈夫曼编码。流水线比较的单级结构如图5所示，要确定0~9这10个元素对应的编码，那么需要级联10级流水线比较的单级结构。其中code0~code17依次送入in_bit端，第i级的Cmp_bit为i，当In_bit[i]和Cmp_bit[i]相同时，那么In_code[i]即为元素i对应的哈夫曼编码，输出为code[i]。如果In_bit[i]和Cmp_bit[i]不相同时，将Out_bit[i]和Out_code[i]输出给下一级继续比较。当10级电路都参与比较以后，每级比较结构对应的输出端code[i]为0-9对应的哈夫曼编码(i=0....9)。

1.3 哈夫曼编码输出

　　在输出阶段，先输出0~9对应的哈夫曼编码，接着输出数字序列对应的哈夫曼编码。考虑到哈夫曼编码变字长输出的特性，那么，编码输出的连续是本模块设计的难点，为了使编码在输出端连续输出，在编码的阶段，进行了每个数据元素编码长度的统计，同时配合4个缓冲寄存器，来实现输出的连续性。哈夫曼输出模块的结构图如图6所示。

　　输入的数据序列，在统计频数后存入ram中，在还没开始输出的时候，从ram中一次读出4个数据，并将对应的编码存入4个缓存寄存器中。当0~9数据元素的编码输出完以后，这时，开始输出reg1中的值，每输出1位，编码长度length减1，同时编码结果code右移1位进行输出。当length为1时，读出ram下一地址的数据，并将对应的编码结果写入reg1中，同时开始输出reg2中的编码值，这样读写在四个reg中的轮流切换，实现了数据的连续输出。

2 设计验证

　　为了直接明了判断设计的正确性，本文设计的测试方案是：将一组随机数据序列存入rand_bin.txt中，先采用C语言完成哈夫曼编码的软件设计^[3]，按照统一的格式存入hafuman.txt文件中，与本设计结果进行比较。

　　创建激励文件test_bench，首先在start信号之后，将rand_bin.txt文件里的数据读出并送给data_in信号，在output_start信号之后，将hafuman.txt文件里的数读出来送给soft_result信号，作为软件编码的结果，将硬件编码结果output_data与软件编码结果soft_result比较，如果相同，那么error信号为低，如果其中有数据不相同，则error变高，提示此次编码有误。

　　测试结果如图7所示。其中error信号保持为低电平，表明哈夫曼编码正确。

3 电路的工作参数总结

3.1 最高频率

　　电路功能正确实现后，对工作时钟进行了约束^[4]，将pll倍频到245M时，如图8所示，观察到电路中各触发器的建立时间余量为正，表明时序通过。

3.2 编码周期

　　在设置好合适的综合策略后^[5]，对电路进行后防真如图9，在某一组随机数据下，本设计需要的工作周期数(start信号到output_start的时钟周期)为316个，其中数据输入的时钟周期数为256，编码生成到编码开始输出的时钟周期数为60。由于哈夫曼编码是变字长的，所以数据序列的编码长度根据输入数据的不同而有所差异，即output_start到output_done之间的时钟周期数在不同的输入数据下结果不同。

　　参考文献：

　　[1]高亚军.vivado入门与提高.http://xilinx.eetop.cn/viewnews-2698.

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

　　[3]steve kilts著,孟宪元译,高级FPGA设计-结构、实现和优化[M].北京:机械工业出版社,2009.

　　[4]何滨.Xilinx FPGA权威设计指南-Vivado 2014集成开发环境[M].北京:电子工业出版社, 2015.

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