[發明專利]一種結點可擴展的哈夫曼編碼的實現方法及電路結構

有效

• 申請號: 201710649560.3
• 申請日: 2017-08-01
• 公開（公告）號: CN107565973B
• 公開（公告）日: 2020-07-14
• 發明（設計）人: 陳海燕;吳健虢;劉勝;郭陽;雷元武;陳俊杰;安天樂;黃成龍
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: H03M7/40
• 分類號: H03M7/40
• 代理公司: 湖南兆弘專利事務所(普通合伙) 43008
• 代理人: 周長清

本發明公開了一種結點可擴展的哈夫曼編碼的實現方法及電路結構，該方法的步驟為：S1：以統計好的n個權重值作為葉子結點的權重值，并對結點權重值按從小到大的順序排序；S2：排序完成后開始生成哈夫曼樹，每次取出兩個權重值最小的結點，生成父結點，直到生成n?1個父結點；S3：哈夫曼樹生成后采用自頂向下的方式對結點進行編碼，葉子結點編碼即為哈夫曼編碼。該電路結構用來實現上述方法。本發明具有結點可擴展、易于硬件實現且編碼效率高等優點。

技術領域

本發明主要涉及到數字信號處理領域，具體涉及一種結點可擴展的哈夫曼編碼的實現方法及電路結構。

背景技術

隨著互聯網、移動計算等應用需求的急劇增長，全世界的數據信息量約每20個月就會增加1倍。在無線通信中常需傳輸大量音頻、視頻等流媒體數據，尤其在遠程通信中，海量數據的傳輸和實時處理需求，與通訊線路的傳輸延遲和帶寬形成了尖銳的矛盾。解決這一矛盾的有效方法就是使用數據壓縮處理技術。

數據壓縮是一種通過去除數據冗余信息以減少數據存儲空間的技術，被廣泛用于文件存儲、圖像處理和數字通信當中。數據壓縮技術的方法多種多樣，本質無非有兩種：一種以信息論為基礎的冗余位消除法；一種是引進某些特殊算法，像哈夫曼算法、正交變換等。冗余位消除法由于誤差限制，總要丟失一部分信息，而特殊算法采用全信息的壓縮方式，能夠保證信息的完整性。

哈夫曼編碼(Huffman Coding)由David Huffman在1952年提出，是一種基于概率統計原理的變長無損壓縮編碼，其軟件實現一直是研究熱點。有學者提出了一種快速自適應哈夫曼編碼算法，對傳輸數據進行處理，提高了編碼效率。Schwartz在1964年提出了一種改進的范式哈夫曼編碼，該編碼有助于降低編碼過程中的存儲空間開銷。還有研究者提出用一維數組來建立哈夫曼樹各結點之間的關系，使得任何編程語言都可實現哈夫曼編碼。吳晨輝等人提出了一種自頂向下的哈夫曼編碼方法，編碼時對哈夫曼樹的每個結點進行一次掃描，就可得到各葉子結點的哈夫曼編碼，解決了原編碼過程中大量指針移動的問題。但以上研究都是基于軟件方法實現的，其運算速度慢，難以滿足日益增長的數字信號處理需求，采用硬件電路實現則能明顯提高哈夫曼編碼的性能。

對于一組確定權重的葉子結點，構造出的不同二叉樹的帶權路徑長度各不相同，把具有最短帶權路徑長度的二叉樹稱為最優二叉樹，最優二叉樹也稱哈夫曼樹。根據哈夫曼樹的定義，要使二叉樹的帶權路徑長度最短，必須使權重值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。根據這一思想構造最優樹的算法，即哈夫曼算法，原理及過程如下：

(1)根據n個統計權重值{w₁，w₂，...w_n}構造包含n個二叉樹的集合F＝{T₁，T₂，...T_n}，其中每棵二叉樹T_i只包含權重為w_i的結點，且其左、右子樹為空。

(2)從集合F中選兩棵根結點權重值最小的二叉樹T_i和T_j作為左、右子樹構造一棵新的二叉樹T_k，新二叉樹T_k根結點權重值為其左、右子樹根結點權重值之和。

(3)從集合F中刪除新二叉樹的左、右子樹，將新的二叉樹T_k加入F。

(4)重復(2)和(3)，直到F中只有一棵樹為止，這棵樹即為哈夫曼樹。

(5)對哈夫曼樹的各分支編碼，左、右分支可分別用0、1編碼，根結點到所有葉子結點路徑的二進制編碼即為各葉子結點的哈夫曼編碼。

發明內容

本發明要解決的技術問題就在于：針對現有技術存在的技術問題，本發明提供一種結點可擴展、易于硬件實現且編碼效率高的結點可擴展的哈夫曼編碼的實現方法及電路結構。