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

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

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

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

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

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

　　表1 編碼示例1

　　圖1哈夫曼編碼示例

　　2設(shè)計(jì)

　　2.1算法

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

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

　　表2 編碼示例2

　　圖2 硬件編碼示例

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

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

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

　　圖3 兩種哈夫曼編碼

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

　　圖4 頂層模塊

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

　　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ì)各個符號出現(xiàn)的頻次，并控制移位寄存器保存輸入序列，統(tǒng)計(jì)完成后，在輸出端口串行輸出信息。

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

　　3.2 排序模塊

　　圖6 排序模塊

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

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

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

　　表3 第一次排序之前

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

　　表4 第二次排序之前

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

　　表5 第三次排序之前

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

　　表6 第四次排序之前

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

　　表7 data輸出結(jié)果

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

　　3.3 編碼生成模塊

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

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

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

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

　　表8 生成編碼示例

　　3.4 移位寄存器

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

　　功能是一個移位寄存器，在CE為高時工作。

　　注：此模塊采用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的霍夫曼編碼。對于某特定的符號，其哈夫曼編碼表示為：該符號的的碼字長度(長度為4比特)，緊接著是該符號的碼字。

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

　　圖10 輸出序列示例

　　4結(jié)果

　　4.1電路功能

　　先通過MATLAB程序產(chǎn)生用來測試電路的256個數(shù)據(jù)，這些數(shù)據(jù)根據(jù)一個概率向量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ù)

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

　　圖11 輸出波形示例

　　4.2.2資源占用

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

　　表10 資源占用

　　4.2.3最高時鐘頻率

　　經(jīng)過時序約束后，在時鐘頻率為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.