Optimality of Huffman Code in the Class of 1-Bit Delay Decodable Codes
Kengo Hashimoto, Ken‐ichi Iwata · IEEE Journal on Selected Areas in Information Theory · 2022
For a given independent and identically distributed (i.i.d.) source, Huffman code achieves the optimal average codeword length in the class of instantaneous codes with a single code table. However, it is known that there exist time-variant encoders, which achieve a shorter average codeword length than the Huffman code, using multiple code tables and allowing at most$k$-bit decoding delay for$k = 2, 3, 4, \ldots $. On the other hand, it is not known whether there exists a 1-bit delay decodable code, which achieves a shorter average length than the Huffman code. This paper proves that for a given i.i.d. source, a Huffman code achieves the optimal average codeword length in the class of 1-bit delay decodable codes with a finite number of code tables.