Xilinx哈夫曼編碼系統設計　

作者 孟歡 包海燕 潘飛 電子科技大學 微電子與固體電子學院(四川 成都 610054)

*集成電路創新創業大賽三等獎

孟歡(1991-)，女，碩士生，研究方向：數字系統設計。

摘要：在圖像處理、文件傳真、視頻壓縮編碼中，哈夫曼編碼是最常用的一種編碼方式。本文設計并實現了對一段數字序列進行哈夫曼編碼并將編碼結果串行輸出的電路模塊，電路由輸入數據的排序、數據的哈夫曼編碼、數據序列編碼的結果輸出三個核心模塊組成，在Xilinx平臺上通過硬件描述語言實現該電路。仿真結果表明，該電路編碼正確，并具有較高的工作頻率和編碼效率。

引言

　　哈夫曼編碼是一種可變字長的無損編碼方式。對于出現概率大的元素編以短字長的碼，對于出現概率小的元素編以長字長的碼，來實現平均碼長最短。多媒體技術的廣泛應用導致數據量的迅速增大，對哈夫曼編碼在速度上有了更高的需求。利用硬件設計的大流量和并行性處理的優勢，可以大大地提高編碼效率和傳輸速度。哈夫曼編碼的核心即建立最優二叉樹，各元素的路徑就是它所對應的編碼結果。主要內容包括數據的排序和元素的編碼兩個方面。

　　本文是完全在硬件條件下實現哈夫曼編碼設計的，在排序部分采用流水線結構，通過流水線實現對數據頻數比較，控制數據按照頻數大小由小到大排序。在編碼模塊創新性地采用自頂而下的查找方式，由狀態機尋址得到父節點的哈夫曼編碼，進而得到左右子節點的哈夫曼編碼結果。在輸出模塊中通過4個寄存器對編碼結果進行緩存，控制寄存器讀寫指針進行編碼結果的緩存與輸出，保證數據輸出的連續性。

1 電路總體結構功能框圖

　　利用vivado的設計平臺^[1]，以xc7a100tcg324-1作為目標芯片，對輸入的數據序列進行哈夫曼編碼及輸出，設計電路。電路的接口時序如圖1所示。

　　1)復位結束，在開始信號start產生后，將一段數字序列(256個0~9的數據元素)輸入電路進行哈夫曼編碼，data_in的數據寬度為4，輸入需要256個時鐘周期。

　　2)在編碼完成后，產生output_start信號，開始串行輸出結果output_data。

　　3)output_data數據包含2個部分。先輸出0~9元素對應的編碼結果，接著輸出數據序列的哈夫曼編碼，輸出完畢后產生output_done信號。

　　整體結構框圖如圖2所示。電路主要包括：

　　do_cnt：對輸入數據進行統計和存儲，輸出各元素的頻數。

　　hfm_build：完成元素排序。根據輸入的頻數大小，輸出各節點元素的排序結果。

　　hfm_code：數據編碼模塊。根據hfm_build輸出的元素排序結果，自頂向下完成0到9這10個元素的哈夫曼編碼。

　　hfm_out：編碼輸出模塊。對編碼結果進行單比特的連續輸出。

　　output_data：數據輸出格式。使用brk信號作為0~9元素的編碼輸出和序列編碼輸出的分隔，此時輸出為0，之后輸出數據序列對應的編碼即圖中ram_data_out信號，也就是序列對應的編碼。所有的編碼結果都是先輸出低位再輸出高位。

1.1 數據排序模塊

　　統計部分結束之后需要對數據進行排序，根據輸入數據各元素的頻次大小，對數據進行排序。該部分主要采用流水線的設計思路，當數據和頻次進入排序模塊之后，與模塊內已經進來的所有數據的頻次進行比較，輸出頻數較大的數據，寄存頻數較小的數據。流水線單級結構RTL級電路^[2]設計如圖3所示。in_count和in_data為頻數和對應元素的輸入端，out_count和out_data分別對應頻數和對應元素的輸出端。

　　10個元素對應18個子節點，要完成對二叉樹18個子節點的排序，則總的排序電路由18個單級排序結構組成，根據哈夫曼編碼的性質，本設計將每次排序得到的最小兩個元素的頻數相加作為新元素的頻數。例如頻數最小的兩個元素為9和5，作為左右子節點，父節點對應的頻數為9和5的頻數之和，其對應的元素為10，生成的父節點依次為11、12....17，新生成的父結點與剩下的元素進行新一輪的排序，而已經比較出兩個最小頻數的元素，不再參與排序。排序結構的各級輸入通過計數器來控制。排序完以后，取每級寄存器中的元素bit0~bit17，即18個節點按照頻數由小到大排序的元素序列，輸出給編碼模塊。

1.2 數據編碼模塊

　　該部分設計主要包括編碼FSM、狀態控制模塊、計數模塊、數據編碼模塊和流水線譯碼輸出模塊，其中zero_flag為數據頻數為0的標志信號。數據編碼模塊結構框圖如圖4所示。

　　根據排序模塊的規律，bit0和bit1的父節點是元素10，bit2和bit3的父節點是元素11，bit4和bit5的父節點是元素12，bit6和bit7的父節點是元素13，bit8和bit9的父節點是元素14，bit10和bit11的父節點是元素15，bit12和bit13的父節點是元素16，bit14和bit15的父節點是元素17，bit16和bit17的父節點是根節點。根據哈夫曼樹的特點，父節點的編碼為xxxxxxxxx，則左節點的哈夫曼編碼為xxxxxxxx0，右節點的哈夫曼編碼為xxxxxxxx1。

　　編碼FSM依次控制輸出父節點17至父節點10，首先當輸出父節點17時，它為根節點的左節點或右節點，通過查找到排序結果中的對應位置bit16或者bit17，假定bit16的編碼為0，bit17的編碼為1，則父節點17的編碼可以確定，那么它左節點bit14，右節點bit15的編碼也就確定了。當編碼FSM輸出父節點10時，通過查找確定元素10的編碼，那么bit0和bit1作為元素10的左右節點，編碼結果同樣也可以確定。至此，數據0~17對應的code0~code17都已確定。

　　本文設計了流水線比較輸出電路來確定數據0-9對應的哈夫曼編碼。流水線比較的單級結構如圖5所示，要確定0~9這10個元素對應的編碼，那么需要級聯10級流水線比較的單級結構。其中code0~code17依次送入in_bit端，第i級的Cmp_bit為i，當In_bit[i]和Cmp_bit[i]相同時，那么In_code[i]即為元素i對應的哈夫曼編碼，輸出為code[i]。如果In_bit[i]和Cmp_bit[i]不相同時，將Out_bit[i]和Out_code[i]輸出給下一級繼續比較。當10級電路都參與比較以后，每級比較結構對應的輸出端code[i]為0-9對應的哈夫曼編碼(i=0....9)。

1.3 哈夫曼編碼輸出

　　在輸出階段，先輸出0~9對應的哈夫曼編碼，接著輸出數字序列對應的哈夫曼編碼。考慮到哈夫曼編碼變字長輸出的特性，那么，編碼輸出的連續是本模塊設計的難點，為了使編碼在輸出端連續輸出，在編碼的階段，進行了每個數據元素編碼長度的統計，同時配合4個緩沖寄存器，來實現輸出的連續性。哈夫曼輸出模塊的結構圖如圖6所示。

　　輸入的數據序列，在統計頻數后存入ram中，在還沒開始輸出的時候，從ram中一次讀出4個數據，并將對應的編碼存入4個緩存寄存器中。當0~9數據元素的編碼輸出完以后，這時，開始輸出reg1中的值，每輸出1位，編碼長度length減1，同時編碼結果code右移1位進行輸出。當length為1時，讀出ram下一地址的數據，并將對應的編碼結果寫入reg1中，同時開始輸出reg2中的編碼值，這樣讀寫在四個reg中的輪流切換，實現了數據的連續輸出。

2 設計驗證

　　為了直接明了判斷設計的正確性，本文設計的測試方案是：將一組隨機數據序列存入rand_bin.txt中，先采用C語言完成哈夫曼編碼的軟件設計^[3]，按照統一的格式存入hafuman.txt文件中，與本設計結果進行比較。

　　創建激勵文件test_bench，首先在start信號之后，將rand_bin.txt文件里的數據讀出并送給data_in信號，在output_start信號之后，將hafuman.txt文件里的數讀出來送給soft_result信號，作為軟件編碼的結果，將硬件編碼結果output_data與軟件編碼結果soft_result比較，如果相同，那么error信號為低，如果其中有數據不相同，則error變高，提示此次編碼有誤。

　　測試結果如圖7所示。其中error信號保持為低電平，表明哈夫曼編碼正確。

3 電路的工作參數總結

3.1 最高頻率

　　電路功能正確實現后，對工作時鐘進行了約束^[4]，將pll倍頻到245M時，如圖8所示，觀察到電路中各觸發器的建立時間余量為正，表明時序通過。

3.2 編碼周期

　　在設置好合適的綜合策略后^[5]，對電路進行后防真如圖9，在某一組隨機數據下，本設計需要的工作周期數(start信號到output_start的時鐘周期)為316個，其中數據輸入的時鐘周期數為256，編碼生成到編碼開始輸出的時鐘周期數為60。由于哈夫曼編碼是變字長的，所以數據序列的編碼長度根據輸入數據的不同而有所差異，即output_start到output_done之間的時鐘周期數在不同的輸入數據下結果不同。

　　參考文獻：

　　[1]高亞軍.vivado入門與提高.http://xilinx.eetop.cn/viewnews-2698.

　　[2]張穎超.基于FPGA的Huffman編碼并行實現及高速存儲系統設計[D].西安:長安大學,2015.

　　[3]steve kilts著,孟憲元譯,高級FPGA設計-結構、實現和優化[M].北京:機械工業出版社,2009.

　　[4]何濱.Xilinx FPGA權威設計指南-Vivado 2014集成開發環境[M].北京:電子工業出版社, 2015.

　　本文來源于《電子產品世界》2017年第11期第51頁，歡迎您寫論文時引用，并注明出處。