Renewal Theory and Source Coding

Renewal theory provides a way 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 ot 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.