Almost Instantaneous Fixed-to-Variable Length Codes

Hirosuke Yamamoto, Masato Tsuchihashi, and Junya Honda

IEEE Transactions on Information Theory, Vol. 61, No.12, pp.6432-6443, December 2015

We propose almost instantaneous fixed-to-variable-length (AIFV) codes such that two (resp.~$K-1$) code trees are used if code symbols are binary (resp.~$K$-ary for $K¥geq 3$), and source symbols are assigned to incomplete internal nodes in addition to leaves. Although the AIFV codes are not instantaneous codes, they are devised such that the decoding delay is at most two bits (resp. one code symbol) in the case of binary (resp. $K$-ary) code alphabet. The AIFV code can attain better average compression rate than the Huffman code at the expenses of a little decoding delay and a little large memory size to store multiple code trees. We also show for the binary and ternary AIFV codes that the optimal AIFV code can be obtained by solving 0-1 integer programming problems.

Index Terms : AIFV code, Huffman code, FV code, Code tree, Kraft inequality, Integer programming.

DOI: 10.1109/TIT.2015.2492961