作者 / 贾先韬 张旭 刘泽曦 山东大学 物理学院(山东 济南 250100)
*大学生集成电路立异创业大赛全国总决赛三等奖
摘要：传统的硬件完结哈夫曼编码的办法主要有：预先结构哈夫曼编码表，编码器经过查表的办法输出哈夫曼编码[1];编码器动态生成哈夫曼树，经过遍历节点办法获取哈夫曼编码[2-3]。榜首种办法从均匀码长视点看，在许多情况下非最优;第二种办法需求生成完好的哈夫曼树，会发生很多的节点，且需遍历哈夫曼树获取哈夫曼编码，资源占用多，完结较为费事。本文依据软件完结[4]时，运用哈夫曼树，会提出一种适用于硬件并行完结的新数据结构——字符池，经过对字符池的频数特点比较和排序来决议各个字符节点在字符池中的归属。装备字符池的一起逐渐生成哈夫曼编码，能够进步硬件使用率，并且无需额定操作来提取哈夫曼编码。
导言
哈夫曼(Huffman)编码对呈现频率较高的字符选用较短的编码，对呈现频率较低的字符选用较长的编码，它能够确保均匀码长最短，具有较高的编码功率。因而哈夫曼编码被广泛使用于数据压缩范畴。已有的硬件完结办法包括预先结构哈夫曼编码表和仿照软件实时生成完好哈夫曼树两种。前一种办法在大多数情况下不是最优编码，后一种办法不只需求生成很多节点，并且需求额定硬件模块完结遍历节点操作。针对这些问题，本文提出一种新的适用于硬件完结的数据结构——字符池来对输入数据实时生成哈夫曼编码。
1 哈夫曼编码的原理
哈夫曼编码是一种不等长编码，依据每个字符呈现频率进行编码，每个字符的编码不能是其他字符编码的前缀，一切字符编码总长度比较原码而言将会下降。
2 哈夫曼编码硬件整体完结计划
本文选用自顶而下的规划办法。整体结构由一个顶层模块、接纳模块、核算模块、输出模块和FIFO模块构成。顶层模块由其他4个模块衔接而成，体系整体结构如图1所示。
接纳模块：接纳数据源并分类核算各字符呈现的频数，数据接纳完结后，接纳模块向核算模块发送开端核算信号。核算模块进行核算，生成各字符对应的编码值，做成编码表，完毕后向输出模块发送输出信号。终究输出模块经过查表办法输出各字符的编码值以及哈夫曼编码成果。FIFO模块用于接纳原始数据和向输出模块供给数据源。
3 完结流程
本文运用verilog言语在vivado渠道上进行哈夫曼编码硬件模块的完结，选用器材为xc7a100tcsq324-1。
3.1 FIFO模块
本文的FIFO模块运用vivado的IP核生成，规划时选择好相应参数装备，生成verilog文件后即可直接调用。
3.2 输入模块
运用多个计数器对输入各字符频数以及输入字符总量进行计数，频数被存放在寄存器中，当字符输入完毕(例如输入字符总量达到了约好值)时，输入模块向核算模块输出核算开端信号，一起频数寄存器中的数据被并行输出至核算模块。
3.3 核算模块
3.3.1 新数据结构及对应的硬件完结
本文依据哈夫曼树的思维构建了新的数据结构——字符池用于硬件完结哈夫曼编码。依据n种字符构建n个字符池和n个字符节点。每个字符池包括一个特点：包括的一切字符的频数之和。每个字符节点包括以下特点：所属字符池序号、本身编码值和本身编码长度。因而，界说n个寄存器记载字符节点对应的字符池序号、n个寄存器记载编码值、n个寄存器记载编码长度以及n个寄存器记载字符池的频数。
3.3.2 哈夫曼编码核算流程
进行哈夫曼编码核算时，核算模块经过履行循环操作完结各字符编码的生成以及字符在字符池中的移动。以图2中的实例描绘核算流程。
图2中共有5种字符，各自频数为：“0”：5，“1”：10，“2”：20，“3”：30，“4”：35。
图2(a)为初始化作用，此刻每个字符池包括一个字符，每个字符池的频数恰为那个字符的频数;每个字符的编码值和编码长度清零。图2(a)到图2(d)共经过4次循环操作，终究能够从图2(d)中读取出每个字符的编码值和编码长度，“0”编码值为0011，“1”编码值为1011，“2”编码值为111，“3”编码值为01，“4”编码值为0。
每次循环操作包括排序、选择、最小值和次小值求和、频数更新、字符移动、编码值更新及编码长度更新8步。其间前4步按次序完结，然后一起完结后4步。总循环次数由字符品种数操控。
排序操作功用是将每个节点池的频数从小到大进行排序，本文学习了参考文献[5]中的办法，硬件完结时经过构建比较器阵列将每两个数两两比较，再经过加法器对每个字符频数的比较成果求和。对一个字符频数，若它小于另一个字符的频数，则相应成果为0，否则为1。那么经过指定字符频数与其他字符频数的比较成果之和能够得知它的频数在一切频数中的方位。
选择操作是将排序操作中比较成果为0和1对应的字符频数选出，它们代表最小频数和次小频数，选择操作一起选择出这两个频数对应的字符池ID。硬件完结时构建多个比较器，将比较成果之和与0和1比较，再经过多路复用器从多个频数和字符池ID中精确选择出所需的值。例如在图2(b)中，选择出的两个频数为15和20，它们对应字符池ID为1和2。
接下来的最小值和次小值求和操作便是将选择操作选择出的最小频数和次小频数求和，然后输出。此过程硬件完结时需求一个多位加法器。例如在图2(b)中，求和值为15+20=35。
频数更新操作指依据选择操作选择出的成果进行字符池频数的更新。依照本文约好办法，将最小频数对应字符池的频数更新成无效值，无效值应大于一切或许的频数，它的意图是防止此字符池的频数被接下来的循环选择操作选择出。本文将次小频数对应字符池的频数以求和操作的加法成果代替。例如图2(c)中1号字符池频数变成100，2号字符池频数变成35。
字符移动操作指将特定字符从一个字符池移动到另一个字符池中。依照本文约好办法，将最小频数对应字符池的一切字符移动到次小频数对应字符池中。例如将图2(c)和图2(b)比照可发现1号字符池的字符“0”和“1”被移动到了2号字符池中。
编码值、编码长度更新操作中，按本文约好办法，将最小频数对应字符池的一切字符编码值左移1位并在终究一位补0，长度加1。将次小频数对应字符池的一切字符编码值左移1位并在终究一位补1，长度加1。将图2(c)和图2(b)比照可看出，字符“0”的编码值从0变成00，“1”编码值从1变成10，“2”编码值从无变成1。
一切循环完毕后编码表已生成，核算模块向输出模块发送核算完毕信号。
3.4 输出模块
输出模块担任从FIFO中读取出原始数据、从编码表中获取编码值，再经过并串转化以一位数据口首要输出各字符编码值，再输出字符串编码成果。
4 仿真和调试
本文运用vivado对顶层模块进行归纳完结，经过完结后仿真验证 成果正确性。
图3展现了模块输入时序。本文测验时以huf_in_start高电平脉冲标志数据输入开端，实践数据以4为并口输入，测验字符规模为“0”至“9”。
图4展现了模块输出时序。经过huf_out_start高电平脉冲标明输出开端。首要输出各字符编码序列，包括4bit编码长度和实践编码值，然后输出原始字符串的编码值。huf_out_end高电平脉冲标明输出完毕。
图5为vivado操控台输出，它展现了各字符编码值以及原始字符和testbench进行的解码字符比较，阐明模块正常运转。
5 定论
本文提出了一种新的在硬件上完结哈夫曼编码的办法，使用本文的字符池数据结构，对每次输入的数据实时生成哈夫曼编码表，从均匀码长视点确保了编码的最优，一起防止了生成完好的哈夫曼树，减少了资源占用，并防止了遍历哈夫曼树所需的额定操作，完结方便快捷。
参考文献：
[1]邓丽娟,田金文,柳健,等.哈夫曼编码器IP核的规划与完结[J].微电子学与核算机,2005(02):9-12.
[2]张颖超.依据FPGA的Huffman编码并行完结及高速存储体系规划[D].长安大学,2015.
[3]曾英,邓曙光.依据FPGA的Huffman编码器的规划[J].湖南城市学院学报(自然科学版), 2014(01):32-35.
[4]杨兰.依据C言语的哈夫曼编码的完结[J].软件导刊,2012(09):40-42.
[5]师廷伟,金长江.依据FPGA的并行全比较排序算法[J].数字技能与使用,2013(10):126-127.
本文来源于《电子产品世界》2017年第12期第40页，欢迎您写论文时引证，并注明出处。
