哈夫曼编码系统优化设计及其FPGA硬件实现
李东泽
【期刊名称】《《电子测试》》
【年(卷),期】2019(000)014
【总页数】3页(P84-85,79)
【关键词】哈夫曼编码; FPGA硬件实现; 数据压缩
【作 者】李东泽
【作者单位】沈阳师范大学科信软件学院 辽宁沈阳 110034
【正文语种】中 文
1 哈夫曼编码算法的优化设计与系统实现
面向FPGA硬件实现的改进哈夫曼编码系统包括输入、排序、编码、输出和存储等模块，下面通过功能仿真和时序验证来评价其预期编码功能（编码效率）和所有性能指标（系统稳定性和时序问题）。
快速排序python实现1.1 系统框架
核心模块为排序模块与编码模块，排序模块产生每个编码周期中频数最小与次小节点的地址（标号），将结果送入编码模块，并将编码后的节点进行合并；编码模块根据排序模块送来的结果对相应符号进行编码。此外，系统还包括输入统计、输出及存储等其他功能模块。
哈夫曼编码系统实现过程包括输入、编码、0-9编码输出、测试数据编码输出和停机操作。初始系统处于输入状态，在start信号作用下输入一个脉冲，开始读取256个数据，随后进入编码状态。在编码过程中，排序模块与编码模块同步工作，其工作流程通过Top模块中产生的addrcount与encode_phase信号控制。编码过程共包含9个编码周期（每个编码周期由7个时钟周期组成），编码周期结束后，系统进入0-9编码输出过程与数据编码输出过程。一旦数据全部输出完毕，系统进入停机模式。
1.2 排序模块
哈夫曼编码算法编码速度取决于排序算法。无论是快速排序还是插入排序，传统排序算法均针对串行工作的器件而设计；若采用并行工作特点的FPGA进行硬件实现，将面临时钟周期数多、逻辑复杂且难以优化等问题。鉴于此，本文针对FPGA 并行处理结构设计一个并行排序算法。若不考虑时序问题，仅采用组合逻辑实现，这种算法在一个时钟周期内即可给出排序结果，且组合逻辑单元的数量尚可。此外，根据需要拆分逻辑层数，插入多级流水线，使时序满足要求，时序优化处理相当灵活。
图1 哈夫曼编码系统流程图
并行排序原理如表1所示，若干个输入数据相互比较，将每个数据与其它数据的比较结果相加，得到每个数据在所有数据中的排名。排名为0和1的两个数据分别为最小值和次小值，表1中对应为D和B。输入：10个8bit数，为输入的10个符号的频数。1个5bit数，为当前编码周期将要产生的新节点的地址（从10000开始，每个编码周期加1）。
输出：2个5bit数，每个编码周期中的最小值和次小值节点所对应的地址。
每个节点由地址与频数组成，地址是10个5bit的rank寄存器。
表1 排序原理?
1.3 编码模块
传统哈夫曼编码算法先通过排序结果建立二叉树，再自顶而下遍历树来获取每个符号的编码，不仅占用大量的空间存储二叉树，而且耗费大量额外的时钟周期来对树进行遍历，不符合FPGA并行工作的特点。因此，本文把编码顺序改为从后向前，在排序模块产生每个周期结果，将对应符号同时进行编码。由于排序与编码并行执行且彼此独立，便于FPGA硬件实现。每个编码周期为7个时钟周期，每个周期完成的工作如下：
步骤0:10个输入数据分为0-4和5-9两组，在组内进行两两比较，得到两个5数据组中数据的组内排名。
步骤1:根据排名，分别得出两组数据中的最小值和次小值。
步骤2:将两组最小值和次小值所对应的数据和地址装入下一级寄存器。
步骤3:4个数据进行两两比较，并得到排名。
步骤4:根据排名得到4个数据中的最小值和次小值（对应原来10个数据中的最小值和次小值）。
步骤5:将最小值与次小值对应的地址装入输出寄存器。
步骤6:将最小值对应节点置为无效（频数置为FF），将次小值对应节点的频数置为最小值与次小值频数之和，地址置为当前编码周期的新节点地址。
改进后哈夫曼编码系统的基本原理显示如下：
第1个周期内，8为频数最小节点（左节点），4为频数次小节点（右节点），给8和4的最后一位分别编码为0和1。此时，8和4的父节点编码为10。
第2个周期内，2为左节点，10为右节点。给2的最后一位编码为0，给10的所有子叶节点的最后一位（已被编码的位不算）编码为1。此时，2、8、4的父节点编码为11。
以此类推，最后一个编码周期，16为左节点，17为右节点。此时给7、2、8、4、3最后一
位编码为0，给9、0、5、6、1最后一位编码为1。
9个编码周期即可完成编码。显然，改进后的编码方式简单高效。采用FPGA平台对编码算法进行硬件实现，简化了逻辑结构，减少了不必要的资源占用，避免了复杂逻辑导致的时序问题。
2 哈夫曼编码的系统仿真与性能验证
2.1 编码算法的实现与仿真
燕尾箭头指示对应符号在当前编码周期完成后的编码结果；加粗方框代表Parent_Addr与当前编码周期产生的min2addr相同的符号，即当前编码周期中末尾被追加1的符号；深粗方框代表Parent_Addr与当前编码周期产生的min1addr相同的符号，即当前编码周期中末尾被追加0的符号。
输入：两个5bit数，为每个编码周期最小值与次小值节点的地址，分别是o_min1addr与o_min2addr。1 个5bit 数，为当前编码周期将要产生的新节点地址（从10000开始，每个编码周期加1）。
输出：10个10bit数，为每个符号的编码。10个10bit数，为每个符号编码末尾（从后向前的末尾）的指针。
功能：每个编码周期末尾，读取最小值与次小值节点的地址（标志），并在对应符号的末尾进行编码。9个编码周期末所有符号编码完成。
指针：为10bit的one-hot码，起始值为000000001，用于指示编码的末尾，其Hot位指向当前编码末尾的下一位（即待编码的位）。每次在末尾追加编码时，会左移一位。
父节点地址：节点所属的当前已编码最高节点的地址。
具体工作流程：需要两个时钟周期，在编码周期的步骤6和步骤0进行。
步骤6：读取最小值与次小值节点地址，判断需要在末尾追加编码的符号（父节点地址等于最小值或次小值节点地址的符号）。
步骤0：根据判断结果，在所有对应符号的编码的末尾（指针的hot位）进行追加（最小值追加0，次小值追加1），并将这些符号的指针左移一位，父节点地址置为当前编码周期产生的新节点地址。
2.2 编码系统的稳定性测试
为了确保在各种输入数据下编码算法均能正确输出编码结果，需要哈夫曼编码系统进行稳定性测试，测试程序采用python编写，随机生成测试数据，运行仿真，将编码输出结果与软件编码结果进行比对，对解码后输出结果与输入数据进行比对，将所有结果记录到文件，使用脚本令计算机反复自动执行上述过程。
测试时，若直接生成256个0-9随机数据，则0-9频数接近均匀分布，不利于验证系统测试在输入数据各种频数分布下的稳定性。因此，需要确保数据的随机性。本方案先随机地产生数据分布的频数，再根据频数生成测试数据，保证稳定性测试全面覆盖所有情况下的输入数据。测试5000组随机数据的编码正确率为100%，说明编码系统功能正常、性能稳定。
3 结论
为了提高数据压缩效率并降低系统成本，本文突破了传统哈夫曼编码规则和算法流程，提出了面向FPGA平台的哈夫曼编码系统优化设计框架和硬件实现方案，利用动态可重构计算技术有效提高编码效率和存储资源，通过大量仿真测试与性能验证对该编码系统进行全
面评估。在编码过程中，排序模块采取并行排序方式，充分兼顾FPGA并行工作特点，减少时钟周期数；编码模块避免传统二叉树建立过程，简化逻辑结构，提高了硬件资源利用率，减少了面积开销，完全避免由复杂逻辑导致的一系列时序问题。该哈夫曼编码系统实现了预期编码功能和所有性能指标，完全满足时钟周期数少、频率高、资源占用少等设计需求。
参考文献
【相关文献】
[1]张红军，徐超.基于改进哈夫曼编码的数据压缩方法研究[J].唐山师范学院学报，2014年第36卷第5期.
[2]刘方明，潘晓中，杨晓元.数字图像DCT变换的FPGA实现 [J].计算机工程与应用 ，2012，48(6)：65-68.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。