作者 / 黃傳 黃尚川 劉旭陽(yáng) 北京航空航天大學(xué) 電子信息工程學(xué)院(北京 100191)
*第一屆(2016-2017)全國(guó)大學(xué)生集成電路創(chuàng)新創(chuàng)業(yè)大賽全國(guó)總決賽FPGA設(shè)計(jì)方向獲獎(jiǎng)作品
Huffman編碼是一種可變字長(zhǎng)的無損壓縮編碼。根據(jù)字符出現(xiàn)的概率得到的可變字長(zhǎng)編碼表是Huffman編碼的核心。概率低的字符使用較短的編碼,概率高的字符使用的長(zhǎng)的編碼。
Huffman編碼的具體方法是將序列中的信源符號(hào)先按出現(xiàn)的頻次排序,把兩個(gè)最小的頻次相加,作為新的頻次和剩余的頻次重新排序,再把最小的兩個(gè)頻次相加,再重新排序,直到最后變成序列的總長(zhǎng)度。每次挑出的最小兩個(gè)頻次所對(duì)應(yīng)的信源符號(hào)或信源符號(hào)集構(gòu)成二叉樹的左右兩支,對(duì)這左右兩支賦予“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ú)熱碼”對(duì)符號(hào)進(jìn)行預(yù)編碼(信源符號(hào)“0”用0000000001編碼,信源符號(hào)“1”用0000000010編碼…),在合并符號(hào)集時(shí)對(duì)兩符號(hào)集的編碼進(jìn)行抑或,使新符號(hào)集的編碼能反映符號(hào)集中的元素。比如一個(gè)符號(hào)集的編碼是0000010011,按照之前的規(guī)定,這個(gè)符號(hào)集就含有“0”,“1”,“4”這三個(gè)信源符號(hào)。這樣做的好處就是能通過對(duì)檢測(cè)符號(hào)集編碼中“1”的位置得到符號(hào)集中元素,從而在對(duì)符號(hào)的哈夫曼編碼過程轉(zhuǎn)化為對(duì)一個(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)包含的元素,便可以在排序完成后立即得到所有元素的碼字。
對(duì)于碼字長(zhǎng)度最小方差問題,對(duì)幾個(gè)符號(hào)集頻次相同的情況,優(yōu)先合并符號(hào)集中所包含符號(hào)數(shù)量少的兩個(gè)符號(hào)集。算法選擇的下圖中第二種算法,碼長(zhǎng)方差最小。
圖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ì)使用簡(jiǎn)單的寄存器操作即可完成,具體不贅述。在統(tǒng)計(jì)過程中,使能移位寄存器信號(hào)為高,統(tǒng)計(jì)完成后,valid信號(hào)產(chǎn)生高電平脈沖,示意排序器開始工作,同時(shí)在輸出端將各個(gè)符號(hào)出現(xiàn)的頻次按時(shí)鐘節(jié)拍依次送入排序器。
3.2 排序模塊
圖6 排序模塊
為了便于描述,我們將排序器的操作對(duì)象定義為“節(jié)點(diǎn)”。一個(gè)“節(jié)點(diǎn)”中包含有一組待編碼的符號(hào),“節(jié)點(diǎn)”的頻次為這些符號(hào)的頻次之和。
該排序器的功能是輸出具有兩個(gè)最小頻次的節(jié)點(diǎn)信息。data_0表示最小頻次對(duì)應(yīng)的節(jié)點(diǎn)信息,data_1表示次小頻次對(duì)應(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所示,對(duì)于5個(gè)節(jié)點(diǎn)進(jìn)行排序的例子可以說明該排序器的工作原理。
表3 第一次排序之前
第一次輸出頻率最小的兩個(gè)符號(hào)的data,即A和E對(duì)應(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é)果
類似地,對(duì)于此項(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ù)最長(zhǎng)可能為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)行操作。對(duì)于data_0中的每一個(gè)符號(hào),為其增加一位編碼“0”;對(duì)于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ù)包含了霍夫曼編碼表,以及對(duì)輸入數(shù)據(jù)進(jìn)行編碼后的結(jié)果。
哈夫曼編碼表按順序存放了0~9的霍夫曼編碼。對(duì)于某特定的符號(hào),其哈夫曼編碼表示為:該符號(hào)的的碼字長(zhǎng)度(長(zhǎng)度為4比特),緊接著是該符號(hào)的碼字。
哈夫曼編碼表之后是輸入數(shù)據(jù)的編碼結(jié)果。具體的格式如下圖所示:
圖10 輸出序列示例
4結(jié)果
4.1電路功能
先通過MATLAB程序產(chǎn)生用來測(cè)試電路的256個(gè)數(shù)據(jù),這些數(shù)據(jù)根據(jù)一個(gè)概率向量p來生成,再利用Vivado仿真工具加載數(shù)據(jù)到電路輸入端,并把電路輸出的有效數(shù)據(jù)輸出到文件中。
利用MATLAB對(duì)輸出數(shù)據(jù)進(jìn)行解碼并和原始數(shù)據(jù)進(jìn)行比對(duì)(編碼正確性測(cè)試),還利用MATLAB內(nèi)置的哈夫曼編碼函數(shù)計(jì)算平均碼長(zhǎng)與電路得出的平均碼長(zhǎng)進(jìn)行對(duì)比(平均碼長(zhǎng)測(cè)試)。下表是在不同概率向量p下得到的測(cè)試結(jié)果如表9所示。
表9 功能測(cè)試
根據(jù)測(cè)試結(jié)果,可以證明電路功能的正確性。
4.2電路性能
4.2.1消耗時(shí)鐘周期數(shù)
對(duì)于不同的輸入序列有不同的編碼長(zhǎng)度,所以電路的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.
網(wǎng)站首頁(yè) |網(wǎng)站簡(jiǎn)介 | 關(guān)于我們 | 廣告業(yè)務(wù) | 投稿信箱
Copyright © 2000-2020 m.netfop.cn All Rights Reserved.
中國(guó)網(wǎng)絡(luò)消費(fèi)網(wǎng) 版權(quán)所有 未經(jīng)書面授權(quán) 不得復(fù)制或建立鏡像
聯(lián)系郵箱:920 891 263@qq.com