Optimal Codes in the Class of 2-Bit Delay Decodable Codes
Kengo Hashimoto, Ken‐ichi Iwata · IEEE Transactions on Information Theory · 2024
For an integer$k \geq 0$, k-bit delay decodable code-tuples are source codes that use a finite number of code tables and allow a decoding delay of at most k bits. It is known that the class of k-bit delay decodable code-tuples can achieve a better average codeword length than Huffman codes for$k \geq 2$. However, it is generally challenging to find an optimal k-bit delay decodable code-tuple (i.e., a k-bit delay decodable code-tuple achieving the optimal average codeword length among all k-bit delay decodable code-tuples) because the class of k-bit delay decodable code-tuples is a comprehensive and flexible class containing a variety of source code consisting of any finite number of code tables. AIFV (almost instantaneous fixed-to-variable length) codes are 2-bit delay decodable code-tuples consisting of two code tables satisfying certain constraints. This paper proves that the class of AIFV codes always contains an optimal 2-bit delay decodable code-tuple for any given source distribution. Thus, we can find an optimal 2-bit delay decodable code-tuple in the class of 2-bit delay decodable code-tuples by considering only the class of AIFV codes, which is a very restricted subclass compared to the whole class of 2-bit delay decodable code-tuples.