2005/06/10 by Marco Dalai, Dalai, Marco, Riccardo Leonardi +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Cellular Automata and Applications #DNA and Biological Computing #E.4 #FOS: Computer and information sciences #H.1.1 #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0506036
5 pages, 3 figures. To be presented at the 2005 IEEE International Symposium on Information Theory
arxiv created 2005/06/10 · openalex publication_date 2005/06/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we consider the use of variable length non prefix-free codes for coding constrained sequences of symbols. We suppose to have a Markov source where some state transitions are impossible, i.e. the stochastic matrix associated with the Markov chain has some null entries. We show that classic Kraft inequality is not a necessary condition, in general, for unique decodability under the above hypothesis and we propose a relaxed necessary inequality condition. This allows, in some cases, the use of non prefix-free codes that can give very good performance, both in terms of compression and computational efficiency. Some considerations are made on the relation between the proposed approach and other existing coding paradigms.