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

Tjalling J. Tjalkens, Frans M.J. Willems

Research output: Contribution to journalArticleAcademicpeer-review

20 Citations (Scopus)


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 languageEnglish
Pages (from-to)247-253
Number of pages7
JournalIEEE Transactions on Information Theory
Issue number2
Publication statusPublished - 1 Jan 1992


  • asymptotic redundancy
  • enumerative coding
  • Universal source coding
  • variable-to-fixed length codes


Dive into the research topics of 'A universal variable-to-fixed length source code based on lawrence's algorithm'. Together they form a unique fingerprint.

Cite this