The Supertree of the Compact Codes

Abstract
An instantaneous D-ary code which minimizes the average codeword length for an information source is called a compact code. It is known that
for a D-ary compact code with codeword lengths $\ell_1, \ell_2, ..., \ell_n$  (where $n$ is in the form of $n = k (D −1) +1$ for some positive integer $k$ ), we have $\sum D^{\ell_i}=1$ . Since construction of $n$ D-ary codewords given codeword lengths $\ell_1, \ell_2, ..., \ell_n$ is a straight-forward task, we generate all possible codeword length sequences. In this paper, we present an algorithm which gets all compact codes with $k(D −1) +1$ codewords and generates all compact codes with $(k +1)(D −1) +1$ codewords. Based on this algorithm, $ST_n (D)$ , the Supertree of all D-ary compact codes, is introduced. Any node in the $m$-th level of $ST_n (D)$ is associated with a unique compact code with $2D −1+ m(D −1)$ codewords. Following the proposed approach, any D-ary compact code with $n$ codewords can be represented by $⎡⎢(n −1) (D −1)⎤⎥ − 2$ bits.