2013/10/08 by Ryo Nomura, Nomura, Ryo
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Cellular Automata and Applications #Code word #Coding (social sciences) #DNA and Biological Computing #Data compression #Decoding methods #Discrete mathematics #FOS: Computer and information sciences #Infimum and supremum #Information Theory (cs.IT) #Lossless compression #Mathematics #Parity-check matrix #Probability of error #Statistics #Variable (mathematics) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1310.2001
arxiv created 2013/10/08 · openalex publication_date 2013/10/08 · arxiv updated 2013/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Lossless variable-length source coding with codeword cost is considered for general sources. The problem setting, where we impose on unequal costs on code symbols, is called the variable-length coding with codeword cost. In this problem, the infimum of average codeword cost have been determined for general sources. On the other hand, overflow probability, which is defined as the probability of codeword cost being above a threshold, have not been considered yet. In this paper, we determine the infimum of achievable threshold in the first-order sense and the second-order sense for general sources and compute it for some special sources such as i.i.d. sources and mixed sources. A relationship between the overflow probability of variable-length coding and the error probability of fixed-length coding is also revealed. Our analysis is based on the information-spectrum methods.