哈夫曼编码的HDL实现

作者 / 黄传 黄尚川 刘旭阳 北京航空航天大学 电子信息工程学院（北京 100191）

*第一届（2016－2017）全国大学生集成电路创新创业大赛全国总决赛FPGA设计方向获奖作品

　　Huffman编码是一种可变字长的无损压缩编码。根据字符出现的概率得到的可变字长编码表是Huffman编码的核心。概率低的字符使用较短的编码，概率高的字符使用的长的编码。

　　Huffman编码的具体方法是将序列中的信源符号先按出现的频次排序，把两个最小的频次相加，作为新的频次和剩余的频次重新排序，再把最小的两个频次相加，再重新排序，直到最后变成序列的总长度。每次挑出的最小两个频次所对应的信源符号或信源符号集构成二叉树的左右两支，对这左右两支赋予“0”和“1”的权重。符号的编码从树的根部开始一直到达符号所在的叶节点， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的哈夫曼编码。

　　编码示例如表 1和图1所示。

　　表1 编码示例1

　　图1哈夫曼编码示例

　　2设计

　　2.1算法

　　算法核心思想就是利用哈夫曼编码过程中需要合并频次最小的两个符号集并且每次合并符号集不相交的特点，先用“独热码”对符号进行预编码(信源符号“0”用0000000001编码,信源符号“1”用0000000010编码…)，在合并符号集时对两符号集的编码进行抑或，使新符号集的编码能反映符号集中的元素。比如一个符号集的编码是0000010011，按照之前的规定，这个符号集就含有“0”,“1”,“4”这三个信源符号。这样做的好处就是能通过对检测符号集编码中“1”的位置得到符号集中元素，从而在对符号的哈夫曼编码过程转化为对一个个符号集整体编码。

　　编码示例如表2和图2所示。

　　表2 编码示例2

　　图2 硬件编码示例

　　注意到每个符号集被合并时都会将参与合并的两个符号集的预编码相异或，并将结果作为新符号集的预编码。并行化处理就体现在这排序和编码可以同时进行。

　　在每次参与合并的两个符号集上都带有其相应的预编码，预编码不为0的位体现了这个符号集包含的信源符号。在每次排序完成后，将0和1分别赋予这两个符号集内包含的元素，便可以在排序完成后立即得到所有元素的码字。

　　对于码字长度最小方差问题，对几个符号集频次相同的情况，优先合并符号集中所包含符号数量少的两个符号集。算法选择的下图中第二种算法，码长方差最小。

　　图3 两种哈夫曼编码

　　2.2硬件设计

　　图4 顶层模块

　　顶层模块为Huffman Coding，其中包含五个子模块，分别为：

　　1)Receiver：统计频次信息，并控制shift register缓存这些信息，统计完成后输出频次信息;

　　2)Sorter：根据频次信息进行9次排序，每次排序输出相应的数据到code_gen;

　　3)Code gen：根据sorter数据生成编码表，并输出到encoder;

　　4)Shift register：256x4 bit的移位寄存器。(此模块为Xilinx IP 核);

　　5)Encoder：控制移位寄存器输出并根据编码表输出数据。

　　3实现

　3.1 接收模块

　　图5 接收模块

　　功能：统计各个符号出现的频次，并控制移位寄存器保存输入序列，统计完成后，在输出端口串行输出信息。

　　频次的统计使用简单的寄存器操作即可完成，具体不赘述。在统计过程中，使能移位寄存器信号为高，统计完成后，valid信号产生高电平脉冲，示意排序器开始工作，同时在输出端将各个符号出现的频次按时钟节拍依次送入排序器。

　　3.2 排序模块

　　图6 排序模块

　　为了便于描述，我们将排序器的操作对象定义为“节点”。一个“节点”中包含有一组待编码的符号，“节点”的频次为这些符号的频次之和。

　　该排序器的功能是输出具有两个最小频次的节点信息。data_0表示最小频次对应的节点信息，data_1表示次小频次对应的节点信息。

　　初始时，每个节点中仅有一个符号。排序器每次将具有最小频次的两个节点的信息输出(为data_0和data_1)，然后将这两个节点合并成一个新的节点。如表3所示，对于5个节点进行排序的例子可以说明该排序器的工作原理。

　　表3 第一次排序之前

　　第一次输出频率最小的两个符号的data，即A和E对应的data，分别为00001和10000;然后这两组符号被合并为同一个节点，即有表4结果。

　　表4 第二次排序之前

　　类似上一次，第二次输出分别为10001和00010，然后这两组符号被合并，即有表5结果。

　　表5 第三次排序之前

　　类似上一步，第三次输出分别为10011和01000，仍然将它们合并，即有表6结果。

　　表6 第四次排序之前

　　则第四次输出为00100和11011。这也是最后一次输出。所以输出结果如表7所示。

　　表7 data输出结果

　　类似地，对于此项目中10个符号的情况，只要用10位二进制数来表示相应的节点信息即可。

　　3.3 编码生成模块

　　图7 产生编码模块

　　功能是根据排序器排序模块输出的数组生成编码表。

　　在本工程中，根据设计需求，可以算出，每个字符的编码位数最长可能为9位，最短为1位。所以存储编码表的寄存器应该至少有9位，每一位的可能状态有三种：“0”，“1”，“-”，分别表示“该位编码为0”、“该位编码为1”和“该位没有存储编码信息”。因此，我们使用两个比特来表示一位编码。

　　编码是根据data_0和data_1生成的，初始时，所有位都被置为“-”，然后根据data_0和data_1进行操作。对于data_0中的每一个符号，为其增加一位编码“0”;对于data_0中的每一个符号，为其增加一位编码“1”。表8为图1中的数据生成编码的过程。

　　表8 生成编码示例

　　3.4 移位寄存器

　　图8 产生编码表模块

　　功能是一个移位寄存器，在CE为高时工作。

　　注：此模块采用Xilinx IP核——RAM-based Shift Register。

　　3.5 编码模块

　　图9 编码模块

　　功能是把编码表和输入序列的编码串行输出。

　　输出格式：在output_start置高电平后、output_done置高电平前，output_data端为有效的输出数据。这些数据包含了霍夫曼编码表，以及对输入数据进行编码后的结果。

　　哈夫曼编码表按顺序存放了0～9的霍夫曼编码。对于某特定的符号，其哈夫曼编码表示为：该符号的的码字长度(长度为4比特)，紧接着是该符号的码字。

　　哈夫曼编码表之后是输入数据的编码结果。具体的格式如下图所示：

　　图10 输出序列示例

　　4结果

　　4.1电路功能

　　先通过MATLAB程序产生用来测试电路的256个数据，这些数据根据一个概率向量p来生成，再利用Vivado仿真工具加载数据到电路输入端，并把电路输出的有效数据输出到文件中。

　　利用MATLAB对输出数据进行解码并和原始数据进行比对(编码正确性测试)，还利用MATLAB内置的哈夫曼编码函数计算平均码长与电路得出的平均码长进行对比(平均码长测试)。下表是在不同概率向量p下得到的测试结果如表9所示。

　　表9 功能测试

　　根据测试结果，可以证明电路功能的正确性。

　　4.2电路性能

　　4.2.1消耗时钟周期数

　　对于不同的输入序列有不同的编码长度，所以电路的Total Cycle是不确定的。但是从start到output_start的周期间隔是确定的，为272个时钟周期，如下图所示。

　　图11 输出波形示例

　　4.2.2资源占用

　　在选择目标器件为xc7a100tcsg324-1进行综合、布线之后，资源消耗情况如表10所示。

　　表10 资源占用

　　4.2.3最高时钟频率

　　经过时序约束后，在时钟频率为125M的情况，满足约束条件。

　　参考文献：

[1]David A. Huffman. A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE. 40(9): 1098–1101. doi:10.1109/JRPROC.1952.273898

[2]Sutherland, Stuart, Davidmann, Simon, Flake, Peter. SystemVerilog for Design Second Edition. Springer US: 2006

[3]Joshua Vasquez.(January 20,2016)“SORT FASTER WITH FPGAS”, http://hackaday.com/2016/01/20/a-linear-time-sorting-algorithm-for-fpgas/

[4]高亚军.Vivado从此开始[M].北京;电子工业出版社，2017.　               [5]Donald E. Thomas, Philip R. Moorby. The Verilog® Hardware Description Language,Fifth Edition. Kluwer Academic Publishers; 2002.