Analysis of a Block Arithmetic Coding: Discrete divide and conquer recurrences
Michael Drmota, Wojciech Szpankowski · 2011
In 1993 Boncelet introduced a block arithmetic scheme for entropy coding that combines advantages of stream arithmetic coding 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.