Average-sense optimality and competitive optimality for almost instantaneous VF codes
Hirosuke Yamamoto and Hidetoshi Yokoo
IEEE Trans. on Information Theory, vol.47, no.6, pp.2174-2184, Sep. 2001
- One-shot coding and repeated coding are considered for the class of almost instantaneous variable-to-fixed length (AIVF) codes, $\cC_{AIVF}$, which includes some nonproper VF codes in addition to the class of proper VF codes, $\cC_{PVF}$. An algorithm is given to construct the average-sense optimal (a-optimal) AIVF code in one-shot coding that attains the maximum average parse length in $\cC_{AIVF}$. The algorithm can also be used to obtain an AIVF code with multiple parse trees, which can attain good performance for repeated coding. Generally, the a-optimal code for one-shot coding and the good code for repeated coding are more efficient than the Tunstall code in $A$-ary cases if $A\geq 3$ although they coincide with the Tunstall code in the binary case. The competitively optimal (c-optimal) VF code is also considered for one-shot coding, and it is shown that the c-optimal code does not always exist in $\cC_{PVF}$ and in $\cC_{AIVF}$. Furthermore, whenever the c-optimal code exists, the Tunstall code is c-optimal in $\cC_{PVF}$ and the a-optimal code obtained by our algorithm is c-optimal in $\cC_{AIVF}$ if $A= 2$ or $3$, but the a-optimal code is not always c-optimal in $\cC_{AIVF}$ if $A\geq 4$.
- Index Terms: Almost instantaneous variable-to-fixed length (AIVF) code, competitive optimality, Tunstall code, variable-to-fixed length (VF) code
- DOI: 10.1109/18.945241