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

有效

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

1.一種結點可擴展的哈夫曼編碼的實現方法，其特征在于，步驟為：

S1：以統計好的n個權重值作為葉子結點的權重值，并對結點權重值按從小到大的順序排序；

S2：排序完成后開始生成哈夫曼樹，每次取出兩個權重值最小的結點，生成父結點，直到生成n-1個父結點；

S3：哈夫曼樹生成后采用自頂向下的方式對結點進行編碼，葉子結點編碼即為哈夫曼編碼；

在步驟S2中，采用一維數組結構來存儲哈夫曼樹，即采用一維數組來存儲各個樹結點的信息；對于n個葉子結點的哈夫曼編碼電路，該數組的深度為2n-1，數組前n個單元用于存儲n個葉子結點，后n-1個單元用于存儲父結點；經排序后葉子結點已按權重值由小到大的順序存放；每次構建父結點時，需要從權重值集合中選擇最小兩個權重結點，因此每次只需要從2個最小葉結點和2個最小父結點共4個結點中找到權重值最小的兩個結點來構建新的父結點；

所述哈夫曼樹通過哈夫曼樹構建單元生成，所述哈夫曼樹構建單元根據輸入的n個權重值生成n-1個父結點，通過設置兩個標記flagl和flagr，flagl記錄當前葉子結點中未使用的第一個葉子結點編號，flagr記錄當前父結點中未使用的第一個父結點編號；每次分別從flagl和flagr的編號位置開始，各取出兩個相鄰結點的權重值，對取出的4個結點的權重值進行比較找出權重值最小的兩個結點，分別作為左、右子結點生成新的父結點，父結點記錄左、右子結點編號，根據結點計數器的值將父結點信息存儲到數組對應位置，最后更新flag標記和計數器；控制器根據輸入的權重值的個數控制循環次數，發出生成父結點的相關控制信號，完成哈夫曼樹的構建。

2.根據權利要求1所述的結點可擴展的哈夫曼編碼的實現方法，其特征在于，在步驟S1中，將n個葉子結點分為p組，對n個權重值的排序分p站進行，其中p0，使得每站實現一組葉結點的并行全比較排序運算。

3.根據權利要求2所述的結點可擴展的哈夫曼編碼的實現方法，其特征在于，在步驟S1中，所有n個葉子結點權重值和除自身外的其余n-1個葉子結點權重值兩兩并行比較，分別將n-1個比較結果累加作為該結點權重的排序位置。

4.根據權利要求1或2或3所述的結點可擴展的哈夫曼編碼的實現方法，其特征在于，所述葉子結點的信息包括結點編號、結點權重值、結點編碼和編碼長度；每個父結點除了記錄以上這些信息外，還記錄其左、右子結點編號，子結點編號建立了父結點和子結點之間的聯系。

5.根據權利要求1或2或3所述的結點可擴展的哈夫曼編碼的實現方法，其特征在于，在步驟S3中，采用自頂向下的編碼方式對各結點進行編碼，通過自頂向下遍歷一次父結點就得到每個葉子結點的哈夫曼編碼。

6.一種結點可擴展的哈夫曼編碼的電路結構，其特征在于，包括：

葉子結點權重值排序單元，用來將統計好的n個權重值作為葉子結點的權重值，并對結點權重值按從小到大的順序排序；

哈夫曼樹構建單元，用來在排序完成后開始生成哈夫曼樹，每次取出兩個權重值最小的結點，生成父結點，直到生成n-1個父結點；

哈夫曼編碼單元，用來在哈夫曼樹生成后采用自頂向下的方式對結點進行編碼，葉子結點編碼即為哈夫曼編碼；

所述哈夫曼樹構建單元根據輸入的n個權重值生成n-1個父結點，通過設置兩個標記flagl和flagr，flagl記錄當前葉子結點中未使用的第一個葉子結點編號，flagr記錄當前父結點中未使用的第一個父結點編號；每次分別從flagl和flagr的編號位置開始，各取出兩個相鄰結點的權重值，對取出的4個結點的權重值進行比較找出權重值最小的兩個結點，分別作為左、右子結點生成新的父結點，父結點記錄左、右子結點編號，根據結點計數器的值將父結點信息存儲到數組對應位置，最后更新flag標記和計數器；控制器根據輸入的權重值的個數控制循環次數，發出生成父結點的相關控制信號，完成哈夫曼樹的構建。