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

有效

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

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

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

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

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

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

一個碼字值緩存單元，用于存放每一個字符對應的Huffman編碼的值；

一個碼字長度緩存單元，用于存放每一個字符對應的Huffman編碼值所對應的碼字長度；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（9）數據打包單元在得到碼字值緩存單元及碼字長度緩存單元的控制權之后，開始對原始的數據進行Huffman編碼，并打包輸出；

（10）主控狀態機在進行對新的數據塊進行統計之前對頻率緩存單元的提前清空。

3.根據權利要求2所述的動態Huffman編碼硬件實現方法，其特征在于：

所述步驟（1）中字符快速統計通過加法器和頻率緩存單元完成。

4.根據權利要求2所述的動態Huffman編碼硬件實現方法，其特征在于：所述步驟（2）中最小堆緩存單元進行維護過程為把頻率緩存單元中的字符出現頻率依次順序的讀出，并加以判斷，如果不為0，就把該字符放進最小堆緩存單元中，一直到頻率緩存單元中所有的葉子節點都讀取并判斷完畢，如果為0就不放進最小堆緩存單元中，在把字符依次存進最小堆緩存單元中的同時記錄最小堆的長度，即最小堆緩存單元中有效的字符的數目，這些字符在邏輯關系上呈現二叉樹的形式；

從最小堆緩存單元中數據元素個數的一半開始一直到最小堆緩存單元的頂部依次調整這棵二叉樹，使得這課二叉樹中的每一個節點都滿足左節點和右節點都大于或者等于本節點，其中葉子節點除外。