基于FPGA的快速哈夫曼编码设计

作者　陆哲敏 易庆阳 杨一凡 蒋剑飞　　上海交通大学(上海 200240)

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

摘要：针对不同的应用场景，给出两种方案，一种用码表实现，另一种用静态编码实现。码表方式将题目与实际应用结合起来，针对不同场景给出不同的码表快速编码;不过考虑到无规律信号的编码，所以通过静态编码使我们的作品更加具有普适性，我们还采用三位范式编码的方式，缩短输出周期;同时在数据输入结束之前开始排序，减少编码实际占用的时间。

0 引言

　　哈夫曼编码是基于带权路径最小的最优二叉树——哈夫曼树的一种平均码长最短的编码方式。哈夫曼编码常用于数据的无损压缩，尤其在卫星探测、医学图像处理、雷达测试系统等领域有着广泛应用^[1]。

　　以对一段长度为256的0~9的数据进行编码为例，如果采用定长编码，则需要4位表示一个0~9的数字，一共需要4*256 = 1024位实现编码，而如果采用哈夫曼编码可以大大降低需要的位数。

1 算法设计

　　在开始设计前，我们先对目前主流哈夫曼方案作简单分析：

　　1.静态编码：编码速度与资源占用方面都在合理范围内，虽然编码速度比码表慢，但是通用性要比码表好;

　　2.动态编码：动态编码依据的是一棵动态变化的哈夫曼树，每个数据的编码都是由它前面所有数据组成的哈夫曼树决定的，虽然可以同步输出编码序列，但是对资源占用较大;

　　3.码表方案：码表只针对特定分布的数据可以获得良好压缩率，但是有着其极小的资源占用和无需复杂运算的优点。

　　经过以上分析，我们选择码表和静态编码相结合的方式进行编码。在输入完成前，对输入序列的分布进行判断，如果符合码表的分布要求，则直接由码表编码，加快编码的速度，如果不符合，则进行静态编码，以实现编码速度和压缩率的平衡。

　　为实现哈夫曼编码，我们将整个系统分为5个模块：统计、排序、编码、码表和输出。

　　数据由数据源输入之后，首先对其统计与排序。在整个过程中，排序进行两次，第一次在第251个周期，用于判断使用码表还是静态编码;第二次则根据编码方式的不同而改变：如果使用码表编码，则在第256个周期开始排序;如果使用静态编码，则在第254个周期排序，这是由于最后两个权值对压缩率影响极小，所以通过丢弃最后两个权值信息加快编码速度。

　　为了进一步减小资源占用与输出周期，编码和码表模块输出的码长均由3位构成，这样设计比起4位输出时要节省10个周期。理论支撑是出现码长为9的情况时，数据频率需要满足第i个数的码长大于前i-2个数的码长之和，这种情况的概率是极小的;而且即使出现码长为9的情况时，最大的4个码长——9、9、8、7也可以用8、8、8、8来近似，由于最大码长对应的数据的频率很小，压缩率的损失也很小。故码长为9的情况可以舍弃，所以认为码长在1~8之间，用3位二进制来表示。

1.1 统计模块

　　统计模块的功能是对输入的数据统计出现的频数。设计的思想是给0到9每个数字构造一个计数器，先初始化计数器值为0，每次输入一个数字之后其相应的计数器加1，这样，在数据全部输入完成后即可得到0到9这10个数字的权重。

1.2 排序模块

　　排序模块的功能是对已经统计好的数据进行排序。设计的思想是：将每个权值都两两比较一次，由比较结果就可以快速确定它在一个降序排列的存储器seq中的位置。由于这些比较都是并行的组合逻辑，所以只需要读一次比较结果，一个周期即可完成排序。

1.3 码表模块

　　排序模块的排序结果作为码表模块选择何种编码方式的判断依据，当序列接近于等概率分布时，哈夫曼编码基本等效于等长编码，此时进行静态编码效率较低，所以通过码表1直接编码;除此之外，当序列分布范围极广，即分布十分不均匀的时候，用静态编码效率也比较低，此时采用码表2进行编码。两张码表如表1、表2所示。

1.4 编码模块

　　如果码表模块无法对输入数据进行编码，则必须通过编码模块完成静态编码。

　　编码过程是由构建哈夫曼树和分配码长两个过程组成的[4]，此模块中我们使用到3个存储器，一个是上文提到的seq，记录排序好的十个数据以及各自权值;另一个存储器是node，是由哈夫曼树中的非叶节点构成的;而最后一个存储器为result，保存整棵哈夫曼树。

　　10个叶结点组成的哈夫曼树应有19个结点，但是根结点不参与编码，所以result只保存18个结点，同样，node结点也只保存8个内部结点。

　　为了提高编码效率，构建node存储器和构建result存储器是同步进行的，而构建哈夫曼树和分配码长的操作均为两个结点同时操作，编码过程也没有选择常规的自底向上的编码，而是选择了自顶向下的编码方式，避免重复读取内部结点[5]，如此下来，构造result的过程耗时10个周期，编码过程最快只需耗时8个周期。

　　具体过程如下：

　　假设已有：降序排列的权值序列seq = {seq0, seq1, seq2, seq3, seq4, seq5, seq6, seq7, seq8. seq9}，初始化好的存储器为node={FFH,FFH……,FFH}。

　　1)第1个周期开始构造内部结点node存储器：

　　a)依次从seqn、seqn-1、nodek和nodek+1中寻找最小的两个值(如果权值相同，认为排前面的权值小);

　　b)将最小的两个权值相加后放入node中;

　　c)将n、k作相应移动;

　　d重复a。

　　2)第2个周期开始同步进行哈夫曼树result存储器的构造：

　　a)依次从seqn、seqn-1、nodek和nodek+1中寻找最小的两个值(如果权值相同，认为排前面的权重小);

　　b)将两个最小权值依次放入result中;

　　c)将n、k作相应移动;

　　d)重复a。

　　3)第11个周期开始编码：

　　a)初始码长result[17]=result[16]=1;

　　b)根据标记位，可以知道某一个结点是否有子结点：

　　i.如果有子结点，给子结点分配码长;如果子节点已经是树尾，则编码结束;

　　ii.如果没有子结点，排查下一个结点。

　　4)输出码长数据，即按0~9顺序输出编码结果。

　　1.5 输出模块

　　输出模块主要有三个工作：存储输入数据、求范式哈夫曼编码、对输入数据编码并输出。具体介绍求范式哈夫曼编码[6]工作：

　　编码模块工作完成后，输出模块开始接收码长信息(code_length)，同时记录每个码长出现的次数(size_of_len)和顺序(code_order)，然后根据这些信息求出每个符号的范式哈夫曼编码。

　　如表3所示，第一行表示code的位，第一列表示码长。把码长1出现的次数二进制值对齐第8位，把码长2出现的次数二进制值对齐第7位，以此类推，最后将表格按行相加，即得到数i的编码。

2 验证分析与FPGA实现

　　根据前述的算法设计，最终得到如图1所示的模块连接图。

　　为了验证编码的准确性，首先采用C++编写常规的静态哈夫曼编码算法，同时在Testbench中，采用读写文件的方式将输出结果就保存到文件中，最后再验证两者输出的一致性。

　　对于题目提出的Totalcycles参数，它主要包含了输入数据的256个周期，编码用时以及输出用时。我们的输出用时包含2个部分：一是输出范式编码表，总计30个周期;二是输出编码序列。所以Totalcycles = 256 + 编码用时 + 30 + 编码序列长度。根据测量结果，Totalcycles最优为码表2的547个周期，最差为码表1的1159个周期。

　　对于压缩算法的另一个重要指标压缩率，这里定义为编码后的数据长度与编码前的数据长度之比^[7]，根据测量结果，最优压缩率为25.20%，最差为85.06%，同样分别发生在表1和表2。

　　在目标器件XC7A100T-1CSG324C 上综合实现后，可以得到我们的设计一共使用了1819个查找表和785个寄存器;同时调用了Block Ram的IP核用于存储输入的256个序列。在将扇出约束为50的情况下，由时序报告可知8.600ns的时钟下还有0.025ns的余量，经计算此时的工作频率为116.28MHz^[8]，关键路径位于编码模块的哈夫曼树构造过程。

　　在FPGA上，运用Vivado Logic Analyzer验证后，得到的波形与预期结果完全一致。

3 结论

　　哈夫曼编码从被提出开始，就一直被关注和研究。经过60多年的发展，它已经被广泛应用于数据压缩的各个领域。

　　我们的设计的主要有以下特点：

　　1)与实际应用场景结合起来，提供了两个码表和一种静态编码的方案。在输入数据符合码表条件时，自动调用码表加快编码速度。

　　2)采用范式编码的方式输出，易于解码，并使输出哈夫曼编码表的过程缩短4~24个周期。

　　3)采用3位码长输出，在几乎不损失压缩率的情况下，将输出码表的体积减小25%。

　　4)采用预先编码方案，进一步缩短编码耗时。

　　最初的方案中，静态编码耗时共需要70多个周期，后来几经优化，利用FPGA同步处理的优势，最终降到19个周期，加上预先编码方案，实际占用为17个周期。

　　在判断使用表1、表2或使用静态编码的时候，设计采用了数据频度的极差作为条件，但是在实际测试中我们发现极差并不是特别准确，真正的码表选择和数据分布有着极为复杂的关系，最终我们只能通过收紧判断条件，更多的采用静态编码以避免加速失效。所以码表和码表的选择条件，还需要更多的实验检验和数学证明。

　　参考文献：

　　[1]Latha Pillai, “Huffman Coding” EXILINX, Virtex Series, XAPP616 (v1.0) Apr 22, 2003.

　　[2]方敏,秦晓新.动态哈夫曼编码的数据压缩方法[J].计算机世界,1994(7):29-33.

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

　　[4]李伟生,李域,王涛.一种不用建造Huffman树的高效Huffman编码算法[J].中国图像图形学报,2005,10(3):382-387.

　　[5]林建英,伍勇,李建华,等.一种易于硬件实现的快速自适应哈夫曼编码算法[J].大连理工大学学报,2008,48(3):436-440.

　　[6]张全伙,于洪斌,林榆.优化哈夫曼编码数据压缩技术及程序实现[J].华侨大学学报(自然科学版),1995,16(3):344-348.

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

　　[8]Latha Pillai, “Huffman Coding” EXILINX, Virtex Series, XAPP616 (v1.0) Apr 22, 2003.

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