[發明專利]構建碼表的方法和裝置，編碼、解碼方法和裝置

有效

• 申請號: 201210573145.1
• 申請日: 2012-12-25
• 公開（公告）號: CN103905054A
• 公開（公告）日: 2014-07-02
• 發明（設計）人: 王森;林福輝;羅小偉
• 申請（專利權）人: 展訊通信(上海)有限公司
• 主分類號: H03M7/42
• 分類號: H03M7/42
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 駱蘇華

技術領域

本發明涉及編解碼技術領域，特別涉及一種構建碼表的方法和裝置、編碼方法和裝置，基于碼表的解碼方法和裝置。

背景技術

哈夫曼編碼（Huffman?Coding）是一種變長的無損數據壓縮方法，利用信號源符號的概率分布來確定符號編碼的信息量，對出現概率高的符號，采用短的碼字描述，對于出現概率低的符號，采用長的碼字來描述。

在多媒體壓縮領域，哈夫曼編碼是一種被廣泛應用的算法。根據應用環境的不同，對哈夫曼解碼的速度和解碼時需要儲存的碼表大小有不同的要求。如在高清視頻解碼時，由于碼率很高，解碼速度要求很高；并且，由于碼表一般儲存在片上，對碼表大小也有一定要求。

現有的解碼方法包括線性搜索法、直接查表法、級別比較解析法和分步查表法等。

線性搜索法，按碼字非減的順序將碼本排成一個表，每次讀進一個比特，然后看排序的表中是否有完全匹配，如有則找到索引，沒有則繼續查找。這種方法的優點是所用的表比較小，但是讀取每一位后都進行檢索，解碼速度太慢。

直接查表法，基于碼字建立一張完備碼長碼表，這個完備碼長碼表的每項索引以哈夫曼碼字為前綴，按一定規則擴展到最大碼長長度，其索引值為相應哈夫曼前綴碼碼長。解碼時，以最大碼字長度截取碼流，并將這個截取出的碼流值作為索引，在碼長碼表中檢索，得到碼字碼長。這種方法每解析一個碼字只需一次查表，但對于最大碼字長度為n的碼表，需要2ⁿ個表項，當n比較大時，其碼表的空間開銷過大。

級別比較解析法，由于哈夫曼碼字樹并不一定每一級都有葉子，級別比較解析在線性搜索法的基礎上，用一個葉子檢索表來指示最近下一級存在哈夫曼碼字的級別，并將同一級上最小碼字作為前綴位，其余位補0，擴充到最大碼長長度，用這個碼建成一張定長碼字檢索表。解碼時，將碼流中取出的最大碼字長度的數值與定長碼字檢索表里的碼字從頭開始逐步比較，直到碼流數值小于定長碼字檢索表的碼字，此時葉子檢索表里當前級別數和碼字長度相同。級別比較解析法相比線性搜索法能減少一定的檢索次數，但這種減少依賴于哈夫曼碼字樹本身的結構，如果哈夫曼樹有葉子節點的級別很多，則這種算法帶來的效果改善就很小，其速度可能無法滿足要求。

分步查表法，在碼表中加入索引來指明下一次查表的位置，這樣查表工作就被分為若干次完成，每次讀入固定的比特數，如果命中則輸出解碼值，否則根據當前位置索引值去碼表進行下一步搜索。分步查表法將查表過程分為多步，在一定程度上取得解碼速度與碼表大小的平衡，但每一步讀取固定長度碼流，使得碼表中存在著大量冗余表項，增大了不必要的碼表大小。

發明內容

本發明技術方案要解決的技術問題是現有的解碼方法難以很好的滿足解碼速度和碼表大小的要求。

為解決上述技術問題，本發明技術方案提供一種構建碼表的方法，包括：

將變長編碼的所有碼字按高位對齊后進行排序；

對排序后的每個碼字簇執行至少一步表項構造處理直至所有碼字對應的標識信息均為葉子節點，所述碼字簇為具有相同前綴的碼字，所述前綴的比特數為第一步要讀取的比特數；

所述表項構造處理包括：

為所述碼字簇確定下一步要讀取的比特數；

當所述碼字簇中的碼字的碼長小于或等于已讀取的比特數總和，則對應構造第一信息為對應該碼字的信息、第二信息為當前讀取的比特數中有效的比特數以及標識信息為葉子節點的表項；

當所述碼字簇中的碼字的碼長大于已讀取的比特數總和，則對應構造第一信息為對應該碼字的下一表項的位置信息、第二信息為下一步要讀取的比特數以及標識信息為中間節點的表項。

可選的，所述排序為從小到大排序。

可選的，在所述表項構造處理中，若碼字簇中連續多個碼字的碼長均大于已讀取的比特數總和，則僅對其中第一個碼字構造對應的表項。

可選的，在所述表項構造處理中，當碼字的碼長小于已讀取的比特數總和，還構造與該碼字對應的表項相同的冗余表項。

可選的，所述前綴的比特數滿足：碼字簇的數量小于或等于2^L0，其中L0為前綴的比特數。

可選的，所述下一步要讀取的比特數滿足：下一步讀取到的Li比特的碼字數據在[0,2^Li-1]的范圍內，其中Li為下一步要讀取的比特數。

可選的，所述下一步要讀取的比特數滿足：下一步讀取到的Li比特的碼字數據盡量多地覆蓋[0,2^Li-1]的范圍。

可選的，所述變長編碼為哈夫曼編碼。