2024/09/20 by Kengo Hashimoto, Hashimoto, Kengo, Iwata Ken-ichi +1
Computer Science · #Advanced Data Storage Technologies #Coding theory and cryptography #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2409.13287
openalex publication_date 2024/09/20 · openalex created_date 2024/10/26 · openalex updated_date 2026/07/28
A k-bit delay decodable code-tuple is a lossless source code that can achieve a smaller average codeword length than Huffman codes by using a finite number of code tables and allowing at most k-bit delay for decoding. It is known that there exists a k-bit delay decodable code-tuple with at most 2(2k) code tables that attains the optimal average codeword length among all the k-bit delay decodable code-tuples for any given i.i.d. source distribution. Namely, it suffices to consider only the code-tuples with at most 2(2k) code tables to accomplish optimality. In this paper, we propose a method to dramatically reduce the number of code tables to be considered in the theoretical analysis, code construction, and coding process.