基于FPGA的快速哈夫曼編碼設(shè)計

陸哲敏 易慶陽 楊一凡 蔣劍飛

摘要：針對不同的應(yīng)用場景，給出兩種方案，一種用碼表實現(xiàn)，另一種用靜態(tài)編碼實現(xiàn)。碼表方式將題目與實際應(yīng)用結(jié)合起來，針對不同場景給出不同的碼表快速編碼；不過考慮到無規(guī)律信號的編碼，所以通過靜態(tài)編碼使我們的作品更加具有普適性，我們還采用三位范式編碼的方式，縮短輸出周期；同時在數(shù)據(jù)輸入結(jié)束之前開始排序，減少編碼實際占用的時間。

關(guān)鍵詞：哈夫曼編碼；靜態(tài)編碼；碼表；范式；應(yīng)用

0 引言

哈夫曼編碼是基于帶權(quán)路徑最小的最優(yōu)二叉樹啥夫曼樹的一種平均碼長最短的編碼方式。哈夫曼編碼常用于數(shù)據(jù)的無損壓縮，尤其在衛(wèi)星探測、醫(yī)學(xué)圖像處理、雷達測試系統(tǒng)等領(lǐng)域有著廣泛應(yīng)用[1]。

以對一段長度為256的0-9的數(shù)據(jù)進行編碼為例，如果采用定長編碼，則需要4位表示一個0-9的數(shù)字，一共需要4*256=1024位實現(xiàn)編碼，而如果采用哈夫曼編碼可以大大降低需要的位數(shù)。

1算法設(shè)計

在開始設(shè)計前，我們先對目前主流啥夫曼方案作簡單分析：

1.靜態(tài)編碼：編碼速度與資源占用方面都在合理范圍內(nèi)，雖然編碼速度比碼表慢，但是通用性要比碼表好：

2.動態(tài)編碼：動態(tài)編碼依據(jù)的是一棵動態(tài)變化的哈夫曼樹，每個數(shù)據(jù)的編碼都是由它前面所有數(shù)據(jù)組成的哈夫曼樹決定的，雖然可以同步輸出編碼序列，但是對資源占用較大；

3.碼表方案：碼表只針對特定分布的數(shù)據(jù)可以獲得良好壓縮率，但是有著其極小的資源占用和無需復(fù)雜運算的優(yōu)點?！?br>