Asymptotic optimality of a universal variable-to-fixed length binary source coding algorithm

Summary form only given. The asymptotic performance of the modified Lawrence algorithm, a universal binary variable-to-fixed-length source coding algorithm has been investigated. For M (the segment set cardinality) large enough, it has been shown that the rate R(p) as a function of the source parameter p satisfies R(p) ≤ h(p)(1 + (log log M)/(2 log M)) for 0 < p < 1, where h(p) is the binary entropy function. It has also been proved that there exist no codes that have a better asymptotic performance, thereby establishing the asymptotic optimality of the 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 code words.