Abstract
The Lawrence algorithm is a universal binary variable-to-fixed length source coding algorithm. Here, a modified version of this algorithm is introduced and its asymptotic performance is investigated. For M (the segment set cardinality) large enough, it is shown that the rate Rθ as a function of the source parameter 0 satisfies Rθ ≈h(θ). (1 +log log M// 2log M), for 0 < θ < 1. Here h(•) is the binary entropy function. In addition to this, it is proven that no codes exist that have a better asymptotic performance, thereby establishing the asymptotic optimality of our modified Lawrence code. The asymptotic bounds show that universal variable-to-fixed length codes can have a significantly lower redundancy than universal fixed-to-variable length codes with the same number of codewords.
Original language | English |
---|---|
Pages (from-to) | 247-253 |
Number of pages | 7 |
Journal | IEEE Transactions on Information Theory |
Volume | 38 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Jan 1992 |
Keywords
- asymptotic redundancy
- enumerative coding
- Universal source coding
- variable-to-fixed length codes