Source codes as random number generators

Karthik Visweswariah, Sanjeev R. Kulkarni, Sergio Verdú

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

A random number generator generates fair coin flips by processing deterministically an arbitrary source of nonideal randomness. An optimal random number generator generates asymptotically fair coin flips from a stationary ergodic source at a rate of bits per source symbol equal to the entropy rate of the source. Since optimal noiseless data compression codes produce incompressible outputs, it is natural to investigate their capabilities as optimal random number generators. In this paper we show under general conditions that optimal variable-length source codes asymptotically achieve optimal variable-length random bit generation in a rather strong sense. In particular, we show in what sense the Lempel-Ziv algorithm can be considered an optimal universal random bit generator from arbitrary stationary ergodic random sources with unknown distributions.

Original languageEnglish (US)
Pages (from-to)462-471
Number of pages10
JournalIEEE Transactions on Information Theory
Volume44
Issue number2
DOIs
StatePublished - 1998

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Data compression
  • Entropy
  • Lempel-Ziv algorithm
  • Random number generation
  • Universal source coding

Fingerprint Dive into the research topics of 'Source codes as random number generators'. Together they form a unique fingerprint.

Cite this