## 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