作者 陆哲敏 易庆阳 杨一凡 蒋剑飞 上海交通大学(上海 200240)
*“榜首届(2016-2017)全国大学生集成电路立异创业大赛全国总决赛“FPGA规划方向三等奖
摘要：针对不同的运用场景，给出两种计划，一种用码表完结，另一种用静态编码完结。码表办法将标题与实践运用结合起来，针对不同场景给出不同的码表快速编码;不过考虑到无规律信号的编码，所以经过静态编码使咱们的著作愈加具有普适性，咱们还选用三位范式编码的办法，缩短输出周期;一起在数据输入完毕之前开端排序，削减编码实践占用的时刻。
0 导言
哈夫曼编码是依据带权途径最小的最优二叉树——哈夫曼树的一种均匀码长最短的编码办法。哈夫曼编码常用于数据的无损紧缩，尤其在卫星勘探、医学图画处理、雷达测验体系等范畴有着广泛运用[1]。
以对一段长度为256的0~9的数据进行编码为例，假如选用定长编码，则需求4位表明一个0~9的数字，总共需求4*256 = 1024位完结编码，而假如选用哈夫曼编码能够大大下降需求的位数。
1 算法规划
在开端规划前，咱们先对现在干流哈夫曼计划作简略剖析：
1.静态编码：编码速度与资源占用方面都在合理规模内，尽管编码速度比码表慢，可是通用性要比码表好;
2.动态编码：动态编码依据的是一棵动态改动的哈夫曼树，每个数据的编码都是由它前面一切数据组成的哈夫曼树决议的，尽管能够同步输出编码序列，可是对资源占用较大;
3.码表计划：码表只针对特定散布的数据能够获得杰出紧缩率，可是有着其极小的资源占用和无需杂乱运算的长处。
经过以上剖析，咱们挑选码表和静态编码相结合的办法进行编码。在输入完结前，对输入序列的散布进行判别，假如契合码表的散布要求，则直接由码表编码，加快编码的速度，假如不契合，则进行静态编码，以完结编码速度和紧缩率的平衡。
为完结哈夫曼编码，咱们将整个体系分为5个模块：核算、排序、编码、码表和输出。
数据由数据源输入之后，首要对其核算与排序。在整个进程中，排序进行两次，榜首次在第251个周期，用于判别运用码表仍是静态编码;第2次则依据编码办法的不同而改动：假如运用码表编码，则在第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页，欢迎您写论文时引证，并注明出处。
