[發明專利]一種動態Huffman編碼硬件實現系統及其實現方法

有效

• 申請號: 201210458012.X
• 申請日: 2012-11-14
• 公開（公告）號: CN102983866A
• 公開（公告）日: 2013-03-20
• 發明（設計）人: 湯曉東;郭彥鋒;李冰
• 申請（專利權）人: 無錫芯響電子科技有限公司
• 主分類號: H03M7/40
• 分類號: H03M7/40
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 樓高潮

技術領域

本發明涉及數據壓縮技術。尤其涉及一種動態Huffman編碼硬件實現系統及其實現方法。

背景技術

在云計算的海量數據處理中，數據的壓縮、解壓縮是非常重要的手段，可以大幅度的降低數據的存儲空間，提升數據傳輸的吞吐率。

Huffman一種基于統計模式的無損壓縮算法，主要包括以下幾個基本的步驟：a)統計字符的頻率。b)構造Huffman樹。c)?創建Huffman表。d)編碼輸出。最終，在數據流中出現頻率最高的字符給予最短的編碼，而出現頻率最低的給予最長的編碼，這樣就可以得到壓縮的效果。

使用軟件結構實現Huffman樹的過程中，需要采用二叉樹數據結構，因此，我們需要定義一個結構體去表示Huffman?樹中的每一個節點，在硬件描述語言Verilog及VHDL中沒有數據結構。為了實現動態Huffman編碼的結構，因此這里給出了Huffman編碼的硬件實現系統并給出了Huffman編碼硬件實現方法及加速方法。

傳統的Huffman實現方式中，一般是基于軟件平臺的實現方式，編碼過程是串行處理的過程，而在Huffman編碼的硬件實現過程中，采用了快速的字符統計方法、頻率緩存單元提前清空等技術使得數據吞吐率有了明顯的提升。

發明內容

本發明要解決的一個技術問題是提供了一種動態Huffman編碼硬件實現系統及其實現方法，能夠利用極少的組合邏輯、時序邏輯以及存儲器資源加以實現。

本發明為實現上述目的，采用如下技術方案：

一種動態Huffman編碼硬件實現系統，其特征在于，所述系統包括：

一個頻率緩存單元，用于存放數據流中每一個字符出現的頻率；

一個最小堆緩存單元，用于維護頻率緩沖單元中出現頻率不為0的字符，使得這些字符在存儲方式上呈現連續的形式，而這些字符在邏輯關系上呈現二叉樹的形式，并且使得這棵二叉樹滿足：左節點和右節點都大于或者等于本節點，為輔助構造Huffman樹的過程做好準備，其中葉子節點除外；

一個父親節點緩存單元，用于存放Huffman樹中每一個節點的父親節點；

一個深度緩存單元，用于存放整個Huffman樹中每一個節點的深度，其中根節點的深度最大，葉子節點的深度是0；

一個碼字值緩存單元，用于存放Huffman樹中每一個葉子節點對應的Huffman編碼的值；

一個碼字長度緩存單元，用于存放Huffman樹中每一個節點對應的Huffman編碼的碼字長度；

一個乘法器單元，用于計算對待壓縮數據塊經過動態Huffman編碼之后數據塊的大小；

一個數據統計單元，用于統計待壓縮數據流中每一個字符出現的頻率，并將統計的結果存放在頻率緩存單元中；

一個主控狀態機部分，根據頻率緩存單元中存放的每一個字符的頻率，通過最小堆緩存單元、父親節點緩存單元、深度緩存單元來構造Huffman樹及Huffman表，分別存放在碼字值緩存單元及碼字長度緩存單元中；

三個多路選擇器單元，分別用于控制頻率緩存單元在不同的工作階段由主控狀態機或者是由數據統計單元控制，和碼字值緩存單元、碼字長度緩存單元在不同的工作階段分別由主控狀態機或者是由數據打包輸出單元進行控制；

一個數據打包輸出單元，用于查詢待編碼的數據塊中每一個字符查詢碼字值緩存單元及碼字長度緩存單元得到每一個字符的Huffman編碼并打包輸出；

一個加法器單元，用于快速的字符統計，統計結果存放在頻率緩存單元中。

一種動態Huffman編碼硬件實現方法，包括下述步驟：

（1）掃描待壓縮的原始數據，并快速統計每一個字符出現的頻率，依次存放在頻率緩存單元；

（2）主控狀態機讀取頻率緩存單元的數據并把出現頻率不為0的字符順序的放進最小堆緩存單元進行維護；

（3）利用最小堆緩存單元、父親節點緩存單元、深度緩存單元構造Huffman樹，其中Huffman樹的信息最終也是存放在最小堆緩存單元中；

（4）遍歷Huffman樹，得到Huffman樹中每一個葉子節點的碼字長度；

（5）統計每一個非0碼字長度字符的數目；

（6）根據每一個非0碼字長度字符的數目去計算出每一個字符的Huffman碼字值；

（7）統計數據塊經過Huffman編碼之后的數據塊的大小；

（8）主控狀態機部分把碼字值緩存單元、碼字長度緩存單元控制權交給數據打包單元；