In 1993 Boncelet introduced a blockarithmetic scheme for entropy coding that combines advantages of stream arithmeticcoding with algorithmic simplicity. It is a variable-to-fixed length encoding in which the source ...
详细信息
ISBN:
(纸本)9781457705953
In 1993 Boncelet introduced a blockarithmetic scheme for entropy coding that combines advantages of stream arithmeticcoding with algorithmic simplicity. It is a variable-to-fixed length encoding in which the source sequence is partitioned into variable length phrases that are encoded by a fixed length dictionary pointer. The parsing is accomplished through a complete parsing tree whose leaves represent phrases. This tree, in its suboptimal heuristic version, is constructed by a simple divide and conquer algorithm, whose analysis is the subject of this paper. For a memoryless source, we first derive the average redundancy and compare it to the (asymptotically) optimal Tunstall's algorithm. Then we prove a central limit theorem for the phrase length. To establish these results, we apply powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara.
暂无评论