A universal variable-to-fixed length source code based on lawrence's algorithm

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.