TY - JOUR
T1 - Source codes as random number generators
AU - Visweswariah, Karthik
AU - Kulkarni, Sanjeev R.
AU - Verdú, Sergio
N1 - Funding Information:
Manuscript received July 3, 1996; revised August 25, 1997. This work was supported in part by the National Science Foundation under Grants NYI Award IRI-9457645 and NCR 9523805. The authors are with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: [email protected]). Publisher Item Identifier S 0018-9448(98)00839-6.
PY - 1998
Y1 - 1998
N2 - 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.
AB - 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.
KW - Data compression
KW - Entropy
KW - Lempel-Ziv algorithm
KW - Random number generation
KW - Universal source coding
UR - http://www.scopus.com/inward/record.url?scp=0032028938&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032028938&partnerID=8YFLogxK
U2 - 10.1109/18.661497
DO - 10.1109/18.661497
M3 - Article
AN - SCOPUS:0032028938
SN - 0018-9448
VL - 44
SP - 462
EP - 471
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 2
ER -