Title :
Renewal theory and source coding
Author :
Savari, Serap A.
Author_Institution :
Lucent Technol. Bell Labs., Murray Hill, NJ, USA
Abstract :
Renewal theory provides a wavy to derive fundamental results about source coding and is useful in the analysis and design of many lossless data compression algorithms. We consider two very different applications of renewal theory to source coding. The first one results in a variable-length counterpart to the asymptotic equipartition property for unifilar Markov sources. The second application leads to the first analysis of variable-to-fixed length codes with plurally parsable dictionaries.
Keywords :
Markov processes; data compression; source coding; variable length codes; asymptotic equipartition property; lossless data compression algorithms; plurally parsable dictionaries; renewal theory; source coding; unifilar Markov sources; variable-length counterpart; variable-to-fixed length codes; Algorithm design and analysis; Application software; Data compression; Dictionaries; Entropy; Industrial engineering; Operations research; Source coding; Steady-state; Stochastic processes;
Journal_Title :
Proceedings of the IEEE
