作者 / 黄传 黄尚川 刘旭阳 北京航空航天大学 电子信息工程学院（北京 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：256×4 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 第2次排序之前
相似上一次，第2次输出别离为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.
