一種動態Huffman編碼硬體實現系統的製作方法

2023-07-05 13:53:46

專利名稱：一種動態Huffman編碼硬體實現系統的製作方法
技術領域：
本實用新型涉及數據壓縮技術。尤其涉及一種動態Huffman編碼硬體實現系統及其實現方法。
背景技術：
在雲計算的海量數據處理中，數據的壓縮、解壓縮是非常重要的手段，可以大幅度的降低數據的存儲空間，提升數據傳輸的吞吐率。Huffman 一種基於統計模式的無損壓縮算法，主要包括以下幾個基本的步驟:a)統計字符的頻率。b)構造Huffman樹。c)創建Huffman表。d)編碼輸出。最終，在數據流中出現頻率最高的字符給予最短的編碼，而出現頻率最低的給予最長的編碼，這樣就可以得到壓縮的效果。使用軟體結構實現Huffman樹的過程中，需要採用二叉樹數據結構，因此，我們需要定義一個結構體去表示Huffman樹中的每一個節點,在硬體描述語言Verilog及VHDL中沒有數據結構。為了實現動態Huffman編碼的結構，因此這裡給出了 Huffman編碼的硬體實現系統並給出了 Huffman編碼硬體實現方法及加速方法。傳統的Huffman實現方式中，一般是基於軟體平臺的實現方式，編碼過程是串行處理的過程，而在Huffman編碼的硬體實現過程中，採用了快速的字符統計方法、頻率緩存單元提前清空等技術使得數據吞吐率有了明顯的提升。

實用新型內容本實用新型要解決的一個技術問題是提供了一種動態Huffman編碼硬體實現系統及其實現方法，能夠利用極少的組合邏輯、時序邏輯以及存儲器資源加以實現。本實用新型為實現上述目的，採用如下技術方案:一種動態Huffman編碼硬體實現系統，其特徵在於，所述系統包括:一個頻率緩存單元，用於存放數據流中每一個字符出現的頻率；一個最小堆緩存單元，用於維護頻率緩衝單元中出現頻率不為O的字符，使得這些字符在存儲方式上呈現連續的形式，而這些字符在邏輯關係上呈現二叉樹的形式，並且使得這棵二叉樹滿足:左節點和右節點都大於或者等於本節點，為輔助構造Huffman樹的過程做好準備，其中葉子節點除外；—個父親節點緩存單元,用於存放Huffman樹中每一個節點的父親節點；—個深度緩存單元,用於存放整個Huffman樹中每一個節點的深度,其中根節點的深度最大，葉子節點的深度是O ;一個碼字值緩存單元，用於存放Huffman樹中每一個葉子節點對應的Huffman編碼的值；一個碼字長度緩存單元，用於存放Huffman樹中每一個節點對應的Huffman編碼的碼字長度；[0015]一個乘法器單元，用於計算對待壓縮數據塊經過動態Huffman編碼之後數據塊的大小；一個數據統計單元，用於統計待壓縮數據流中每一個字符出現的頻率，並將統計的結果存放在頻率緩存單元中；一個主控狀態機部分，根據頻率緩存單元中存放的每一個字符的頻率，通過最小堆緩存單元、父親節點緩存單元、深度緩存單元來構造Huffman樹及Huffman表,分別存放在碼字值緩存單元及碼字長度緩存單元中；三個多路選擇器單元，分別用於控制頻率緩存單元在不同的工作階段由主控狀態機或者是由數據統計單元控制，和碼字值緩存單元、碼字長度緩存單元在不同的工作階段分別由主控狀態機或者是由數據打包輸出單元進行控制；一個數據打包輸出單元，得到每一個字符的Huffman編碼並打包輸出；一個加法器單元，用於快速的字符統計，統計結果存放在頻率緩存單元中。一種動態Huffman編碼硬體實現方法,包括下述步驟:( I)掃描待壓縮的原始數據，並快速統計每一個字符出現的頻率，依次存放在頻率緩存單元；(2)主控狀態機讀取頻率緩存單元的數據並把出現頻率不為O的字符順序的放進最小堆緩存單元進行維護；(3)利用最小堆緩存單元、父親節點緩存單元、深度緩存單元構造Huffman樹,其中Huffman樹的信息最終也是存放在最小堆緩存單元中；(4)遍歷Huffman樹,得到Huffman樹中每一個葉子節點的碼字長度；(5)統計每一個非O碼字長度字符的數目；(6)根據每一個非O碼字長度字符的數目去計算出每一個字符的Huffman碼字值；(7)統計數據塊經過Huffman編碼之後的數據塊的大小；(8)主控狀態機部分把碼字值緩存單元、碼字長度緩存單元控制權交給數據打包單元；(9)數據打包單元在得到碼字值緩存單元及碼字長度緩存單元的控制權之後，開始對原始的數據進行Huffman編碼，並打包輸出；( 10)主控狀態機在進行對新的數據塊進行統計之前對頻率緩存單元的提前清空。其進一步特徵在於:所述步驟(I)中字符快速統計通過加法器和頻率緩存單元完成。所述步驟(2)中最小堆緩存單元進行維護過程為把頻率緩存單元中的字符出現頻率依次順序的讀出，並加以判斷，如果不為0，就把該字符放進最小堆緩存單元中，一直到頻率緩存單元中所有的葉子節點都讀取並判斷完畢，如果為O就不放進最小堆緩存單元中，在把字符依次存進最小堆緩存單元中的同時記錄最小堆的長度，即最小堆緩存單元中有效的字符的數目，這些字符在邏輯關係上呈現二叉樹的形式；從最小堆緩存單元中數據元素個數的一半開始一直到最小堆緩存單元的頂部依次調整這棵二叉樹，使得這課二叉樹中的每一個節點都滿足左節點和右節點都大於或者等於本節點，其中葉子節點除外。[0036]所述步驟(3)中構造Huffman樹的過程中從最小堆緩存單元的頂部讀取第一個元素，並把這個元素存入最小堆緩存單元底部開始的第一個未被佔用的單元中，此時最小堆緩存單元的長度減1，並將最小堆緩存單元的最後一個元素放進最小堆緩存單元的第一個元素的位置上，從第一個元素位置開始調整這棵二叉樹，使得這棵二叉樹中的每一個節點都滿足左節點和右節點大於或者等於本節點，其中葉子節點除外；從最小堆緩存單元的頂部再讀取第一個元素並把這個元素存入最小堆緩存單元底部開始的第一個未被佔用的單元中，把最小堆緩存單元的長度減1，把從最小堆緩存單元中連續讀取的元素組合成一個新的節點，這個新的節點的權值為兩個連續讀取的元素的權值的和，這個的新節點在整個Huffman樹中的深度為兩個連續讀取元素中較大深度加1，並在父親節點緩存單元中設置好兩個連續讀取的葉子節點的父親節點為這個新得到的節
佔.[0038]把新得到的節點放入最小堆緩存單元的頂部，並把最小堆緩存單元的長度加1，從最小堆緩存單元的頂部開始依次調整最小堆中二叉樹的節點，使得這棵二叉樹滿足左節點和右節點大於或者等於本節點，其中葉子節點除外；判斷最小堆緩存單元的長度是否為0，若不為0，表示Huffman樹未建好，繼續Huffman樹的建立；若為O,表示Huffman樹已經全部建好,把讀取的最後一個節點存入最小堆緩存單元底部開始第一個未被佔用的單元中。所述步驟(4)遍歷Huffman樹,得到Huffman樹中每一個葉子節點的碼字長度過程中Huffman樹已經建好，並存放在最小堆緩存單元中，從最小堆緩存單元中最新存入的那個單元開始，並在碼字長度緩存單元中設置其對應的碼字長度為0，並從Huffman樹的根節點開始，依次遍歷最小堆緩存單元中存放的Huffman樹中剩餘的每一個節點，依次設置好每一個葉子節點的碼字長度，依次對應存放在碼字長度緩存單元中。所述步驟(5)統計每一個非O碼字長度字符的數目過程中在遍歷Huffman樹，得到每一個節點的碼字長度時，主控狀態機會同時統計出每一個碼字長度的節點的個數，為計算Huffman編碼的值作好準備。所述步驟(6)根據每一個非O碼字長度字符的數目去計算出每一個字符的Huffman碼字值的過程是為了得出Huffman樹中每一個節點的碼字值,統計出了每一個非O碼字長度的個數，從Huffman樹的最頂層依次向下進行推出Huffman樹中每一個節點的碼字值，並將葉子節點的碼字值保存在碼字值緩存單元中。所述步驟(7)統計數據塊經過Huffman編碼之後的數據塊的大小過程是為了在得到每一個葉子節點碼字長度的過程中，同時讀取對應的頻率緩存單元中對應字符的頻率信息，通過乘法器單元計算出對頻率緩存單元中字符進行Huffman編碼之後的長度，同時計算出累計Huffman編碼的長度；在得出每一個Huffman葉子節點的碼字長度之後，也就得到了固定長度的數據塊經過Huffman編碼之後總大小。所述步驟(10) Huffman編碼統計之前對頻率緩存單元的提前清空過程為數據打包單元啟動，開始編碼輸出，同時主控狀態機開始把頻率緩存單元開始清空處理，為下一個數據塊的Huffman編碼開始做好準備。本實用新型通過硬體實現了 Huffman編碼,並在Huffman編碼的硬體實現過程中，採用了快速的字符統計方法、頻率緩存單元提前清空等技術使得數據吞吐率有了明顯的提 升。

圖1給出了一種動態Huffman編碼硬體實現系統的結構示意圖。圖2給出了一種動態Huffman編碼硬體實現方法的狀態轉換圖。
具體實施方式
下面參照附圖用本實用新型的示例性實施例對本實用新型進行更全面的描述和說明。如圖1所示，一種動態Huffman編碼硬體實現系統的結構示意圖包括:數據打包單元100，數據選擇器單元101，頻率緩存單元102，數據選擇器單元103，碼字長度緩存單元104，數據選擇器單元105，碼字值緩存單元106，主控狀態機107，父親節點緩存單元108，深度緩存單元109，最小堆緩存單元110，數據統計單元111。數據打包單元100，用於把待壓縮的數據通過查詢碼字長度緩存單元104及碼字值緩存單元106得到每一個字符的Huffman編碼並打包輸出。數據選擇器單元101，用於選擇頻率緩存單元的控制權，在Huffman編碼之前，數據選擇器單元101選擇數據統計單元111去控制頻率緩存單元102 ;在構造Huffman編碼過程中，數據選擇器單元101選擇主控狀態機單元107去控制頻率緩存單元102的控制權。頻率緩存單元102,用於存放Huffman樹中每一個葉子節點的頻率。數據選擇器單元103，用於控制碼字長度緩存單元104的控制權，在得到Huffman樹中每一個葉子節點的碼字長度及碼字值之前，數據選擇器單元103選擇主控狀態機單元107去控制碼字長度緩存單元104 ;在得到Huffman樹中每一個葉子節點的碼字長度及碼字值之後，數據選擇器單元103選擇數據打包單元100去控制碼字長度緩存單元104的控制權。碼字長度緩存單元104,用於存放Huffman樹中每一個葉子節點的碼字長度。數據選擇單元105，用於控制碼字值緩存單元106的控制權，在得到Huffman樹中每一個葉子節點的碼字長度及碼字值之前，數據選擇器單元105選擇主控狀態機單元107去控制碼字值緩存單元106 ;在得到Huffman樹中每一個葉子節點的碼字長度及碼字值之後，數據選擇單元105選擇數據打包單元100去控制碼字值緩存單元106。主控狀態機單元107，通過藉助父親節點緩存單元108，深度緩存單元109，最小堆緩存單元110,去構建Huffman樹,通過遍歷Huffman樹,得到Huffman樹中每一個節點的碼字長度，再根據碼字長度去計算Huffman樹中所有的葉子節點的碼字值存放在碼字值緩存單元106中，對應的葉子節點的碼字長度存放於碼字長度緩存單元104中。父親節點緩存單元108,用於存放Huffman樹中每一個節點的父親節點,根節點除外。深度緩存單元109,用於存放Huffman樹中每一個節點的深度,其中葉子節點的深度是0，根節點的深度最大。最小堆緩存單元110,用於維護Huffman樹中所有的節點，使得這些節點在邏輯上構成一棵二叉樹，並且滿足左節點和右節點大於或者等於本節點，其中葉子節點除外。[0060]數據統計單元111,在Huffman主控狀態機構造Huffman樹之前，由數據統計單元111去統計每一個葉子節點出現的頻率，並把這個統計的每一個字符的頻率信息存放在頻率緩存單元102中。如圖2所示，一種動態Huffman編碼硬體實現方法的狀態轉換圖，主要狀態包括:狀態000(Γ狀態0010在狀態0000，圖1中主控狀態機單元107通過數據選擇單元101獲得頻率緩存單元102的控制權，並把頻率緩存單元中每一個數據存儲單元都清空為0，為數據統計做好準備，並進入狀態0001。在狀態0001，圖1中主控狀態機單元107通過數據選擇單元101開始釋放頻率緩存單元102的控制權，此時頻率緩存單元102的控制權交給數據統計單元111並進入狀態0002。在狀態0002，圖1中數據統計單元111開始對掃描待壓縮的原始數據，並統計每一個字符出現的頻率，依次存放在頻率緩存單元102中，當原始數據塊掃描完畢時，主控狀態機單元107通過數據選擇單元101回收頻率緩存單元102的控制權，並開始進入狀態0003。在狀態0003，主控狀態機單元開始從頻率緩存單元102中依次順序的讀取數據，並把出現頻率不為O的字符順序的放進最小堆緩存單元110中，每存放一個元素最小堆的長度就加1，一直到把頻率緩存單元中的數據讀取完畢為止，在讀取的過程中會進行判斷如果一個字符沒有出現，那麼該字符的碼字長度為0，此時主控狀態機單元107開始把碼字長度緩存單元104中對應的單元填寫為O ;如果出現了那麼該字符定是葉子節點其深度為0，此時主控狀態機單元開始把深度緩存單元109中對應的單元設置為0，重複執行狀態0003，直到所有的節點讀取完畢，並開始進入狀態0004。在狀態0004，主控狀`態機開始處理最小堆緩存單元110中存放的每一個字符，使得這些字符物理上呈現順序存放，在邏輯上又構成了一棵二叉樹，並且這棵二叉樹滿足:左節點和右節點大於或者等於本節點，其中葉子節點除外。在狀態0004重複處理這個過程，直到最小堆中所有的葉子節點都滿足:左節點和右節點大於或者等於本節點，葉子節點除夕卜，最小堆緩存單元110中的數據處理好了之後，主控狀態機單元開始進入狀態0005。在狀態0005，主控狀態機開始從最小堆的頂部讀取一個字符，此時最小堆緩存單元的長度減I，主控狀態機單元107把這個字符從最小堆緩存單元110的底部開始順序的向頂部存放，並把最小堆的有效字符的最後一個字符放進最小堆的頂部，此時最小堆的長度加1，並開始調整最小堆緩存單元110中的元素，使得最小堆緩存單元110中的每一個元素都滿足::左節點和右節點大於或者等於本節點，葉子節點除外，調整好之後，主控狀態機單元107再從最小堆緩存單元110中讀取一個元素，此時最小堆的長度再次減1，主控狀態機單元107再把這個新讀取的字符從最小堆緩存單元110的底部順序的向最小堆的頂部順序的存放，並把兩個連續讀取的元素構成一個新的Huffman節點，即中間節點，並開始設置頻率緩存單元102中這個新的節點的權值為連續讀取的兩個元素的權值之和，在深度緩存單元109中開始設置這個新節點的深度為連續讀取的兩個元素的深度最大值加1，主控狀態機單元107此時還會在父親節點緩存單元中設置之前連續讀取元素的父親節點為這個新得到的節點，處理完之後主控狀態機單元107開始判斷最小堆的長度是否為0，如果為O就表示Huffman樹已經建好並順序的從最小堆的底部向最小堆的頂部存放,並開始準備進入狀態0006，否則就繼續進入狀態0005重複執行上述過程。在狀態0006中，主控狀態機單元107把最後一個存進最小堆緩存單元110中的節點讀取出來，設置其碼字長度為0，進入狀態0007。在狀態0007中，繼續從最小堆緩存單元110中讀取出一個元素，並在碼字長度緩存單元104中設置其碼字長度為其父親節點的碼字長度加1，每設置好一個節點的碼字長度的同時主控狀態機單元107會判斷該節點是不是Huffman樹中的葉子節點，如果是葉子節點主控狀態機單元107就從頻率緩存單元102中把該節點對應的頻率讀取出來，利用乘法器單元計算出採用Huffman編碼待壓縮數據塊中所有的該節點最後總得長度是多長，重複執行步驟0007，在重複執行的過程中主控狀態機單元107同時會統計出每一種碼字長度所對應的節點的個數，當設置好Huffman樹中所有節點的碼字長度後就進入狀態0008。在狀態0008中，主控狀態機單元107根據在狀態0007中得出的每一種碼字長度的個數去計算出所有節點的碼字值，並分別存放在碼字值緩存單元106中，並開始進入狀態0009。在狀態0009中，主控狀態機單元107就通過數據選擇單元103、105釋放對碼字長度緩存單元104及碼字值緩存單元106的控制權，並把碼字長度緩存單元104、碼字值緩存單元106的控制權交給數據打包單元100，進入狀態0010。在狀態0010中，數據打包單元100開始工作，並依次讀取原始待壓縮數據塊中的每一個字符，通過查詢圖1中碼字長度緩存單元104及碼字值緩存單元106開始輸出壓縮之後的數據。在狀態0010中，數據打包單元開始工作的同時，主控狀態機單元107也把頻率緩存單元102中的每一個存儲單元給清除。如果編碼輸出完成並且頻率緩存單元102中的每一個單元都被清除那麼，主控狀態機就通過圖1中數據選擇單元103、105去獲得圖1中碼字長度緩存單元104、碼字值緩存單元106的控制權，並進入狀態0000。在實用新型中，數據存儲及數據控制部分構成的一個完成的系統，結構清晰，利於分析和設計，Huffman樹及Huffman表的構造過程是由主控狀態機去控制存放在各個數據緩存單元中的數據進行的，狀態轉換過程清晰。儘管本實用新型此處具體化一些特定的例子示出和描述，然而本實用新型不限制於所示出的細節，因為在不偏離本實用新型的精神以及在權利要求的範圍和等同範圍內，可以作出多種改進和結構變化。因此，寬範圍地並且如權利要求中所闡明的在某種意義上與本實用新型的範圍一致地解釋附加的權利要求是適當的。
權利要求1.種動態Huffman編碼硬體實現系統，其特徵在於，所述系統包括: 一個頻率緩存單元，用於存放數據流中每一個字符出現的頻率； 一個最小堆緩存單元，用於維護頻率緩衝單元中頻率不為O的字符，； 一個父親節點緩存單元，用於存放Huffman樹中除根節點外的每一個節點的父親節佔.一個深度緩存單元，用於存放整個Huffman樹中每一個節點的深度； 一個碼字值緩存單元，用於存放每一個字符對應的Huffman編碼的值； 一個碼字長度緩存單元，用於存放每一個字符對應的Huffman編碼值所對應的碼字長度； 一個乘法器單元，用於計算對待壓縮數據塊採用動態Huffman編碼之後數據塊的大小; 一個數據統計單元，用於統計待壓縮數據流中每一個字符出現的頻率，並將統計的結果存放在頻率緩存單元中； 一個主控狀態機部分，用於構造Huffman樹及Huffman表,分別存放在碼字值緩存單元及碼字長度緩存單元中； 三個多路選擇器單元，分別用於控制頻率緩存單元在不同的工作階段由主控狀態機或者是由數據統計單元控制，和碼字值緩存單元、碼字長度緩存單元在不同的工作階段分別由主控狀態機或者是由數據打包輸出單元進行控制； 一個數據打包輸出單元，得到每一個字符的Huffman編碼並打包輸出； 一個加法器單元，用於快速的字符統計，統計結果存放在頻率緩存單元中。
專利摘要本實用新型公布了一種動態Huffman編碼硬體實現系統，該系統包括數據打包單元，頻率緩存單元，碼字長度緩存單元，三個數據選擇器單元，碼字值緩存單元，主控狀態機，父親節點緩存單元，深度緩存單元，最小堆緩存單元，數據統計單元，加法器單元和乘法器單元。動態Huffman編碼硬體實現方法，包括快速的字符統計；建立Huffman樹；建立Huffman表；編碼輸出；頻率緩存單元的提前清空等步驟。本實用新型通過硬體實現了Huffman編碼，並在Huffman編碼的硬體實現過程中，採用了快速的字符統計方法、頻率緩存單元提前清空等技術使得數據吞吐率有了明顯的提升。
文檔編號H03M7/40GK202931291SQ201220598299
公開日2013年5月8日 申請日期2012年11月14日 優先權日2012年11月14日
發明者湯曉東, 郭彥鋒, 李冰 申請人:無錫芯響電子科技有限公司