2022/09/19 by Kengo Hashimoto, Hashimoto, Kengo, Iwata Ken-ichi +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Medicine · #Algorithms and Data Compression #Blood groups and transfusion #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2209.08874
openalex publication_date 2022/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a given independent and identically distributed (i.i.d.) source, Huffman code achieves the optimal average codeword length in the class of instantaneous code 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, . . .. 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.