关 闭

新闻中心

EEPW首页 > 工控自动化 > 设计应用 > 基于FPGA的快速哈夫曼编码设计

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

作者:陆哲敏 易庆阳 杨一凡 蒋剑飞时间:2018-02-27来源:电子产品世界收藏
编者按:针对不同的应用场景,给出两种方案,一种用码表实现,另一种用静态编码实现。码表方式将题目与实际应用结合起来,针对不同场景给出不同的码表快速编码;不过考虑到无规律信号的编码,所以通过静态编码使我们的作品更加具有普适性,我们还采用三位范式编码的方式,缩短输出周期;同时在数据输入结束之前开始排序,减少编码实际占用的时间。

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

本文引用地址:http://www.eepw.com.cn/article/201802/376169.htm

  *“第一届(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页,欢迎您写论文时引用,并注明出处。



评论

技术专区

关闭