Almost Instantaneous Fixed-to-Variable Length Codes

DOI10.1109/TIT.2015.2492961MaRDI QIDQ2977150zbMATH OpenOpenAlexFDO

Authors Hirosuke Yamamoto, Masato Tsuchihashi, Junya Honda

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.08733

Mathematics Subject Classification ID

Source coding (94A29) Linear codes (general theory) (94B05)

Abstract: 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 $Kgeq3$), 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.

Cited in

(6)

• Speeding up the AIFV-2 dynamic programs by two orders of magnitude using range minimum queries
• Fixed-Rate Maximum-Runlength-Limited Codes From Variable-Rate Bit Stuffing
• On a class of efficient error-limiting variable-length codes
• A universal variable-to-fixed length source code based on Lawrence's algorithm
• Streaming Codes for Variable-Size Messages
• Old and new results on alphabetic codes

This page was built for publication: Almost Instantaneous Fixed-to-Variable Length Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977150)