2023/06/16 by Kengo Hashimoto, Hashimoto, Kengo, Iwata Ken-ichi +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Arithmetic #Block code #Class (philosophy) #Code (set theory) #Code word #Coding theory and cryptography #Computer science #Concatenated error correction code #DNA and Biological Computing #Data compression #Decoding methods #Discrete mathematics #Encoder #FOS: Computer and information sciences #Huffman coding #Information Theory (cs.IT) #Linear code #Luby transform code #Mathematics #Prefix code #Set (abstract data type) #Statistics
paper · pdf · doi:10.48550/arxiv.2306.09671
openalex publication_date 2023/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
AIFV (almost instantaneous fixed-to-variable length) codes are noiseless source codes that can attain a shorter average codeword length than Huffman codes by allowing a time-variant encoder with two code tables and a decoding delay of at most 2 bits. First, we consider a general class of noiseless source codes, called k-bit delay decodable codes, in which one allows a finite number of code tables and a decoding delay of at most k bits for k >= 0. Then we prove that AIFV codes achieve the optimal average codeword length in the 2-bit delay decodable codes class.