哈夫曼編碼的HDL實(shí)現(xiàn)

作者 / 黃傳 黃尚川 劉旭陽 北京航空航天大學(xué) 電子信息工程學(xué)院（北京 100191）

*第一屆（2016－2017）全國大學(xué)生集成電路創(chuàng)新創(chuàng)業(yè)大賽全國總決賽FPGA設(shè)計(jì)方向獲獎(jiǎng)作品

　　Huffman編碼是一種可變字長的無損壓縮編碼。根據(jù)字符出現(xiàn)的概率得到的可變字長編碼表是Huffman編碼的核心。概率低的字符使用較短的編碼，概率高的字符使用的長的編碼。

　　Huffman編碼的具體方法是將序列中的信源符號(hào)先按出現(xiàn)的頻次排序，把兩個(gè)最小的頻次相加，作為新的頻次和剩余的頻次重新排序，再把最小的兩個(gè)頻次相加，再重新排序，直到最后變成序列的總長度。每次挑出的最小兩個(gè)頻次所對應(yīng)的信源符號(hào)或信源符號(hào)集構(gòu)成二叉樹的左右兩支，對這左右兩支賦予“0”和“1”的權(quán)重。符號(hào)的編碼從樹的根部開始一直到達(dá)符號(hào)所在的葉節(jié)點(diǎn)， 將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號(hào)的哈夫曼編碼。

　　編碼示例如表 1和圖1所示。

　　表1 編碼示例1

　　圖1哈夫曼編碼示例

　　2設(shè)計(jì)

　　2.1算法

　　算法核心思想就是利用哈夫曼編碼過程中需要合并頻次最小的兩個(gè)符號(hào)集并且每次合并符號(hào)集不相交的特點(diǎn)，先用“獨(dú)熱碼”對符號(hào)進(jìn)行預(yù)編碼(信源符號(hào)“0”用0000000001編碼,信源符號(hào)“1”用0000000010編碼…)，在合并符號(hào)集時(shí)對兩符號(hào)集的編碼進(jìn)行抑或，使新符號(hào)集的編碼能反映符號(hào)集中的元素。比如一個(gè)符號(hào)集的編碼是0000010011，按照之前的規(guī)定，這個(gè)符號(hào)集就含有“0”,“1”,“4”這三個(gè)信源符號(hào)。這樣做的好處就是能通過對檢測符號(hào)集編碼中“1”的位置得到符號(hào)集中元素，從而在對符號(hào)的哈夫曼編碼過程轉(zhuǎn)化為對一個(gè)個(gè)符號(hào)集整體編碼。

　　編碼示例如表2和圖2所示。

　　表2 編碼示例2

　　圖2 硬件編碼示例

　　注意到每個(gè)符號(hào)集被合并時(shí)都會(huì)將參與合并的兩個(gè)符號(hào)集的預(yù)編碼相異或，并將結(jié)果作為新符號(hào)集的預(yù)編碼。并行化處理就體現(xiàn)在這排序和編碼可以同時(shí)進(jìn)行。

　　在每次參與合并的兩個(gè)符號(hào)集上都帶有其相應(yīng)的預(yù)編碼，預(yù)編碼不為0的位體現(xiàn)了這個(gè)符號(hào)集包含的信源符號(hào)。在每次排序完成后，將0和1分別賦予這兩個(gè)符號(hào)集內(nèi)包含的元素，便可以在排序完成后立即得到所有元素的碼字。

　　對于碼字長度最小方差問題，對幾個(gè)符號(hào)集頻次相同的情況，優(yōu)先合并符號(hào)集中所包含符號(hào)數(shù)量少的兩個(gè)符號(hào)集。算法選擇的下圖中第二種算法，碼長方差最小。

　　圖3 兩種哈夫曼編碼

　　2.2硬件設(shè)計(jì)

　　圖4 頂層模塊

　　頂層模塊為Huffman Coding，其中包含五個(gè)子模塊，分別為：

　　1)Receiver：統(tǒng)計(jì)頻次信息，并控制shift register緩存這些信息，統(tǒng)計(jì)完成后輸出頻次信息;

　　2)Sorter：根據(jù)頻次信息進(jìn)行9次排序，每次排序輸出相應(yīng)的數(shù)據(jù)到code_gen;

　　3)Code gen：根據(jù)sorter數(shù)據(jù)生成編碼表，并輸出到encoder;

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

　　5)Encoder：控制移位寄存器輸出并根據(jù)編碼表輸出數(shù)據(jù)。

　　3實(shí)現(xiàn)

　3.1 接收模塊

　　圖5 接收模塊

　　功能：統(tǒng)計(jì)各個(gè)符號(hào)出現(xiàn)的頻次，并控制移位寄存器保存輸入序列，統(tǒng)計(jì)完成后，在輸出端口串行輸出信息。

　　頻次的統(tǒng)計(jì)使用簡單的寄存器操作即可完成，具體不贅述。在統(tǒng)計(jì)過程中，使能移位寄存器信號(hào)為高，統(tǒng)計(jì)完成后，valid信號(hào)產(chǎn)生高電平脈沖，示意排序器開始工作，同時(shí)在輸出端將各個(gè)符號(hào)出現(xiàn)的頻次按時(shí)鐘節(jié)拍依次送入排序器。

　　3.2 排序模塊

　　圖6 排序模塊

　　為了便于描述，我們將排序器的操作對象定義為“節(jié)點(diǎn)”。一個(gè)“節(jié)點(diǎn)”中包含有一組待編碼的符號(hào)，“節(jié)點(diǎn)”的頻次為這些符號(hào)的頻次之和。

　　該排序器的功能是輸出具有兩個(gè)最小頻次的節(jié)點(diǎn)信息。data_0表示最小頻次對應(yīng)的節(jié)點(diǎn)信息，data_1表示次小頻次對應(yīng)的節(jié)點(diǎn)信息。

　　初始時(shí)，每個(gè)節(jié)點(diǎn)中僅有一個(gè)符號(hào)。排序器每次將具有最小頻次的兩個(gè)節(jié)點(diǎn)的信息輸出(為data_0和data_1)，然后將這兩個(gè)節(jié)點(diǎn)合并成一個(gè)新的節(jié)點(diǎn)。如表3所示，對于5個(gè)節(jié)點(diǎn)進(jìn)行排序的例子可以說明該排序器的工作原理。

　　表3 第一次排序之前

　　第一次輸出頻率最小的兩個(gè)符號(hào)的data，即A和E對應(yīng)的data，分別為00001和10000;然后這兩組符號(hào)被合并為同一個(gè)節(jié)點(diǎn)，即有表4結(jié)果。

　　表4 第二次排序之前

　　類似上一次，第二次輸出分別為10001和00010，然后這兩組符號(hào)被合并，即有表5結(jié)果。

　　表5 第三次排序之前

　　類似上一步，第三次輸出分別為10011和01000，仍然將它們合并，即有表6結(jié)果。

　　表6 第四次排序之前

　　則第四次輸出為00100和11011。這也是最后一次輸出。所以輸出結(jié)果如表7所示。

　　表7 data輸出結(jié)果

　　類似地，對于此項(xiàng)目中10個(gè)符號(hào)的情況，只要用10位二進(jìn)制數(shù)來表示相應(yīng)的節(jié)點(diǎn)信息即可。

　　3.3 編碼生成模塊

　　圖7 產(chǎn)生編碼模塊

　　功能是根據(jù)排序器排序模塊輸出的數(shù)組生成編碼表。

　　在本工程中，根據(jù)設(shè)計(jì)需求，可以算出，每個(gè)字符的編碼位數(shù)最長可能為9位，最短為1位。所以存儲(chǔ)編碼表的寄存器應(yīng)該至少有9位，每一位的可能狀態(tài)有三種：“0”，“1”，“-”，分別表示“該位編碼為0”、“該位編碼為1”和“該位沒有存儲(chǔ)編碼信息”。因此，我們使用兩個(gè)比特來表示一位編碼。

　　編碼是根據(jù)data_0和data_1生成的，初始時(shí)，所有位都被置為“-”，然后根據(jù)data_0和data_1進(jìn)行操作。對于data_0中的每一個(gè)符號(hào)，為其增加一位編碼“0”;對于data_0中的每一個(gè)符號(hào)，為其增加一位編碼“1”。表8為圖1中的數(shù)據(jù)生成編碼的過程。

　　表8 生成編碼示例

　　3.4 移位寄存器

　　圖8 產(chǎn)生編碼表模塊

　　功能是一個(gè)移位寄存器，在CE為高時(shí)工作。

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

　　3.5 編碼模塊

　　圖9 編碼模塊

　　功能是把編碼表和輸入序列的編碼串行輸出。

　　輸出格式：在output_start置高電平后、output_done置高電平前，output_data端為有效的輸出數(shù)據(jù)。這些數(shù)據(jù)包含了霍夫曼編碼表，以及對輸入數(shù)據(jù)進(jìn)行編碼后的結(jié)果。

　　哈夫曼編碼表按順序存放了0～9的霍夫曼編碼。對于某特定的符號(hào)，其哈夫曼編碼表示為：該符號(hào)的的碼字長度(長度為4比特)，緊接著是該符號(hào)的碼字。

　　哈夫曼編碼表之后是輸入數(shù)據(jù)的編碼結(jié)果。具體的格式如下圖所示：

　　圖10 輸出序列示例

　　4結(jié)果

　　4.1電路功能

　　先通過MATLAB程序產(chǎn)生用來測試電路的256個(gè)數(shù)據(jù)，這些數(shù)據(jù)根據(jù)一個(gè)概率向量p來生成，再利用Vivado仿真工具加載數(shù)據(jù)到電路輸入端，并把電路輸出的有效數(shù)據(jù)輸出到文件中。

　　利用MATLAB對輸出數(shù)據(jù)進(jìn)行解碼并和原始數(shù)據(jù)進(jìn)行比對(編碼正確性測試)，還利用MATLAB內(nèi)置的哈夫曼編碼函數(shù)計(jì)算平均碼長與電路得出的平均碼長進(jìn)行對比(平均碼長測試)。下表是在不同概率向量p下得到的測試結(jié)果如表9所示。

　　表9 功能測試

　　根據(jù)測試結(jié)果，可以證明電路功能的正確性。

　　4.2電路性能

　　4.2.1消耗時(shí)鐘周期數(shù)

　　對于不同的輸入序列有不同的編碼長度，所以電路的Total Cycle是不確定的。但是從start到output_start的周期間隔是確定的，為272個(gè)時(shí)鐘周期，如下圖所示。

　　圖11 輸出波形示例

　　4.2.2資源占用

　　在選擇目標(biāo)器件為xc7a100tcsg324-1進(jìn)行綜合、布線之后，資源消耗情況如表10所示。

　　表10 資源占用

　　4.2.3最高時(shí)鐘頻率

　　經(jīng)過時(shí)序約束后，在時(shí)鐘頻率為125M的情況，滿足約束條件。

　　參考文獻(xiàn)：

[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].北京;電子工業(yè)出版社，2017.　               [5]Donald E. Thomas, Philip R. Moorby. The Verilog? Hardware Description Language,Fifth Edition. Kluwer Academic Publishers; 2002.