Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

This journal is archived by the American Mathematical Society. The master copy is available at http://www.ams.org/era/

For a positive integer $n$, let $X^n$ be the vector formed by the first $n$ samples of a stationary ergodic finite alphabet process. The vector $X^n$ is hierarchically represented via a finite rooted acyclic directed graph $G_n$. Each terminal vertex of $G_n$ carries a label from the process alphabet, and $X^n$ can be reconstituted as the sequence of labels at the ends of the paths from root vertex to terminal vertex in $G_n$. The entropy $H(G_n)$ of the graph $G_n$ is defined as a nonnegative real number computed in terms of the number of incident edges to each vertex of $G_n$. An algorithm is given which assigns to $G_n$ a binary codeword from which $G_n$ can be reconstructed, such that the length of the codeword is approximately equal to $H(G_n)$. It is shown that if the number of edges of $G_n$ is $o(n)$, then the sequence $\{H(G_n)/n\}$ converges almost surely to the entropy of the process.

Copyright 1997 American Mathematical Society

TeX source (21K)
DVI (29K)
PostScript (128K)

Article Info

• ERA Amer. Math. Soc. 03 (1997), pp. 11-16
• Publisher Identifier: S 1079-6762(97)00018-8
• 1991 Mathematics Subject Classification. Primary 28D99; Secondary 60G10, 94A15
• Key words and phrases. Graphs, entropy, compression, stationary ergodic process
• Received by the editors December 12, 1996
• Posted on March 12, 1997
• Communicated by Douglas Lind
• Comments (When Available)

John Kieffer

Department of Electrical Engineering, University of Minnesota, 200 Union Street SE, Minneapolis, MN 55455

E-mail address: kieffer@ee.umn.edu

En-hui Yang

Department of Mathematics, Nankai University, Tianjin 300071, P. R. China

E-mail address: ehyang@irving.usc.edu

This work was supported in part by the National Science Foundation under Grants NCR-9304984 and NCR-9627965