作者 孟欢 包海燕 潘飞 电子科技大学 微电子与固体电子学院(四川 成都 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页，欢迎您写论文时引证，并注明出处。
