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

*集成電路創(chuàng)新創(chuàng)業(yè)大賽三等獎(jiǎng)

孟歡(1991-)，女，碩士生，研究方向：數(shù)字系統(tǒng)設(shè)計(jì)。

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

引言

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

本文是完全在硬件條件下實(shí)現(xiàn)哈夫曼編碼設(shè)計(jì)的，在排序部分采用流水線結(jié)構(gòu)，通過流水線實(shí)現(xiàn)對(duì)數(shù)據(jù)頻數(shù)比較，控制數(shù)據(jù)按照頻數(shù)大小由小到大排序。在編碼模塊創(chuàng)新性地采用自頂而下的查找方式，由狀態(tài)機(jī)尋址得到父節(jié)點(diǎn)的哈夫曼編碼，進(jìn)而得到左右子節(jié)點(diǎn)的哈夫曼編碼結(jié)果。在輸出模塊中通過4個(gè)寄存器對(duì)編碼結(jié)果進(jìn)行緩存，控制寄存器讀寫指針進(jìn)行編碼結(jié)果的緩存與輸出，保證數(shù)據(jù)輸出的連續(xù)性。

1 電路總體結(jié)構(gòu)功能框圖

利用vivado的設(shè)計(jì)平臺(tái)^[1]，以xc7a100tcg324-1作為目標(biāo)芯片，對(duì)輸入的數(shù)據(jù)序列進(jìn)行哈夫曼編碼及輸出，設(shè)計(jì)電路。電路的接口時(shí)序如圖1所示。

1)復(fù)位結(jié)束，在開始信號(hào)start產(chǎn)生后，將一段數(shù)字序列(256個(gè)0~9的數(shù)據(jù)元素)輸入電路進(jìn)行哈夫曼編碼，data_in的數(shù)據(jù)寬度為4，輸入需要256個(gè)時(shí)鐘周期。

2)在編碼完成后，產(chǎn)生output_start信號(hào)，開始串行輸出結(jié)果output_data。

3)output_data數(shù)據(jù)包含2個(gè)部分。先輸出0~9元素對(duì)應(yīng)的編碼結(jié)果，接著輸出數(shù)據(jù)序列的哈夫曼編碼，輸出完畢后產(chǎn)生output_done信號(hào)。

整體結(jié)構(gòu)框圖如圖2所示。電路主要包括：

do_cnt：對(duì)輸入數(shù)據(jù)進(jìn)行統(tǒng)計(jì)和存儲(chǔ)，輸出各元素的頻數(shù)。

hfm_build：完成元素排序。根據(jù)輸入的頻數(shù)大小，輸出各節(jié)點(diǎn)元素的排序結(jié)果。

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

hfm_out：編碼輸出模塊。對(duì)編碼結(jié)果進(jìn)行單比特的連續(xù)輸出。

output_data：數(shù)據(jù)輸出格式。使用brk信號(hào)作為0~9元素的編碼輸出和序列編碼輸出的分隔，此時(shí)輸出為0，之后輸出數(shù)據(jù)序列對(duì)應(yīng)的編碼即圖中ram_data_out信號(hào)，也就是序列對(duì)應(yīng)的編碼。所有的編碼結(jié)果都是先輸出低位再輸出高位。

1.1 數(shù)據(jù)排序模塊

統(tǒng)計(jì)部分結(jié)束之后需要對(duì)數(shù)據(jù)進(jìn)行排序，根據(jù)輸入數(shù)據(jù)各元素的頻次大小，對(duì)數(shù)據(jù)進(jìn)行排序。該部分主要采用流水線的設(shè)計(jì)思路，當(dāng)數(shù)據(jù)和頻次進(jìn)入排序模塊之后，與模塊內(nèi)已經(jīng)進(jìn)來的所有數(shù)據(jù)的頻次進(jìn)行比較，輸出頻數(shù)較大的數(shù)據(jù)，寄存頻數(shù)較小的數(shù)據(jù)。流水線單級(jí)結(jié)構(gòu)RTL級(jí)電路^[2]設(shè)計(jì)如圖3所示。in_count和in_data為頻數(shù)和對(duì)應(yīng)元素的輸入端，out_count和out_data分別對(duì)應(yīng)頻數(shù)和對(duì)應(yīng)元素的輸出端。

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

1.2 數(shù)據(jù)編碼模塊

該部分設(shè)計(jì)主要包括編碼FSM、狀態(tài)控制模塊、計(jì)數(shù)模塊、數(shù)據(jù)編碼模塊和流水線譯碼輸出模塊，其中zero_flag為數(shù)據(jù)頻數(shù)為0的標(biāo)志信號(hào)。數(shù)據(jù)編碼模塊結(jié)構(gòu)框圖如圖4所示。

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

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

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

1.3 哈夫曼編碼輸出

在輸出階段，先輸出0~9對(duì)應(yīng)的哈夫曼編碼，接著輸出數(shù)字序列對(duì)應(yīng)的哈夫曼編碼。考慮到哈夫曼編碼變字長(zhǎng)輸出的特性，那么，編碼輸出的連續(xù)是本模塊設(shè)計(jì)的難點(diǎn)，為了使編碼在輸出端連續(xù)輸出，在編碼的階段，進(jìn)行了每個(gè)數(shù)據(jù)元素編碼長(zhǎng)度的統(tǒng)計(jì)，同時(shí)配合4個(gè)緩沖寄存器，來實(shí)現(xiàn)輸出的連續(xù)性。哈夫曼輸出模塊的結(jié)構(gòu)圖如圖6所示。

輸入的數(shù)據(jù)序列，在統(tǒng)計(jì)頻數(shù)后存入ram中，在還沒開始輸出的時(shí)候，從ram中一次讀出4個(gè)數(shù)據(jù)，并將對(duì)應(yīng)的編碼存入4個(gè)緩存寄存器中。當(dāng)0~9數(shù)據(jù)元素的編碼輸出完以后，這時(shí)，開始輸出reg1中的值，每輸出1位，編碼長(zhǎng)度length減1，同時(shí)編碼結(jié)果code右移1位進(jìn)行輸出。當(dāng)length為1時(shí)，讀出ram下一地址的數(shù)據(jù)，并將對(duì)應(yīng)的編碼結(jié)果寫入reg1中，同時(shí)開始輸出reg2中的編碼值，這樣讀寫在四個(gè)reg中的輪流切換，實(shí)現(xiàn)了數(shù)據(jù)的連續(xù)輸出。

2 設(shè)計(jì)驗(yàn)證

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

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

測(cè)試結(jié)果如圖7所示。其中error信號(hào)保持為低電平，表明哈夫曼編碼正確。

3 電路的工作參數(shù)總結(jié)

3.1 最高頻率

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

3.2 編碼周期

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

參考文獻(xiàn)：

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

[2]張穎超.基于FPGA的Huffman編碼并行實(shí)現(xiàn)及高速存儲(chǔ)系統(tǒng)設(shè)計(jì)[D].西安:長(zhǎng)安大學(xué),2015.

[3]steve kilts著,孟憲元譯,高級(jí)FPGA設(shè)計(jì)-結(jié)構(gòu)、實(shí)現(xiàn)和優(yōu)化[M].北京:機(jī)械工業(yè)出版社,2009.

[4]何濱.Xilinx FPGA權(quán)威設(shè)計(jì)指南-Vivado 2014集成開發(fā)環(huán)境[M].北京:電子工業(yè)出版社, 2015.

本文來源于《電子產(chǎn)品世界》2017年第11期第51頁(yè)，歡迎您寫論文時(shí)引用，并注明出處。