Word-valued sources: An ergodic theorem, an AEP, and the conservation of entropy

Roy Timo; Kim Blackmore; Leif Hanlen

doi:10.1109/TIT.2010.2046251

Word-valued sources: An ergodic theorem, an AEP, and the conservation of entropy

Roy Timo^*, Kim Blackmore, Leif Hanlen

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

A word-valued source Y = Y₁,Y₂,̇ ̇ ̇ is discrete random process that is formed by sequentially encoding the symbols of a random process ${\bf X} = X₁,X₂ ̇ ̇ ̇ with codewords from a codebook. These processes appear frequently in information theory (in particular, in the analysis of source-coding algorithms), so it is of interest to give conditions on X and for which Y will satisfy an ergodic theorem and possess an asymptotic equipartition property (AEP). In this paper, we prove the following: 1) if X is asymptotically mean stationary (AMS), then Y will satisfy a pointwise ergodic theorem and possess an AEP; and 2) if the codebook is prefix-free, then the entropy rate of Y is equal to the entropy rate of X normalized by the average codeword length.

Original language	English
Article number	5484984
Pages (from-to)	3139-3148
Number of pages	10
Journal	IEEE Transactions on Information Theory
Volume	56
Issue number	7
DOIs	https://doi.org/10.1109/TIT.2010.2046251
Publication status	Published - Jul 2010

Access to Document

10.1109/TIT.2010.2046251

Cite this

@article{19b647c5ff8b47338b18d129de889052,

title = "Word-valued sources: An ergodic theorem, an AEP, and the conservation of entropy",

abstract = "A word-valued source Y = Y1,Y2{\.,}{\. }{\. } is discrete random process that is formed by sequentially encoding the symbols of a random process ${\bf X} = X1,X2{\. }{\. }{\. } with codewords from a codebook. These processes appear frequently in information theory (in particular, in the analysis of source-coding algorithms), so it is of interest to give conditions on X and for which Y will satisfy an ergodic theorem and possess an asymptotic equipartition property (AEP). In this paper, we prove the following: 1) if X is asymptotically mean stationary (AMS), then Y will satisfy a pointwise ergodic theorem and possess an AEP; and 2) if the codebook is prefix-free, then the entropy rate of Y is equal to the entropy rate of X normalized by the average codeword length.",

keywords = "Asymptotic equipartition property (AEP), Asymptotically mean stationary (AMS), Ergodic theorem",

author = "Roy Timo and Kim Blackmore and Leif Hanlen",

year = "2010",

month = jul,

doi = "10.1109/TIT.2010.2046251",

language = "English",

volume = "56",

pages = "3139--3148",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "7",

}

TY - JOUR

T1 - Word-valued sources

T2 - An ergodic theorem, an AEP, and the conservation of entropy

AU - Timo, Roy

AU - Blackmore, Kim

AU - Hanlen, Leif

PY - 2010/7

Y1 - 2010/7

N2 - A word-valued source Y = Y1,Y2,̇ ̇ ̇ is discrete random process that is formed by sequentially encoding the symbols of a random process ${\bf X} = X1,X2 ̇ ̇ ̇ with codewords from a codebook. These processes appear frequently in information theory (in particular, in the analysis of source-coding algorithms), so it is of interest to give conditions on X and for which Y will satisfy an ergodic theorem and possess an asymptotic equipartition property (AEP). In this paper, we prove the following: 1) if X is asymptotically mean stationary (AMS), then Y will satisfy a pointwise ergodic theorem and possess an AEP; and 2) if the codebook is prefix-free, then the entropy rate of Y is equal to the entropy rate of X normalized by the average codeword length.

AB - A word-valued source Y = Y1,Y2,̇ ̇ ̇ is discrete random process that is formed by sequentially encoding the symbols of a random process ${\bf X} = X1,X2 ̇ ̇ ̇ with codewords from a codebook. These processes appear frequently in information theory (in particular, in the analysis of source-coding algorithms), so it is of interest to give conditions on X and for which Y will satisfy an ergodic theorem and possess an asymptotic equipartition property (AEP). In this paper, we prove the following: 1) if X is asymptotically mean stationary (AMS), then Y will satisfy a pointwise ergodic theorem and possess an AEP; and 2) if the codebook is prefix-free, then the entropy rate of Y is equal to the entropy rate of X normalized by the average codeword length.

KW - Asymptotic equipartition property (AEP)

KW - Asymptotically mean stationary (AMS)

KW - Ergodic theorem

UR - http://www.scopus.com/inward/record.url?scp=77953788015&partnerID=8YFLogxK

U2 - 10.1109/TIT.2010.2046251

DO - 10.1109/TIT.2010.2046251

M3 - Article

SN - 0018-9448

VL - 56

SP - 3139

EP - 3148

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 7

M1 - 5484984

ER -

Word-valued sources: An ergodic theorem, an AEP, and the conservation of entropy

Abstract

Access to Document

Other files and links

Fingerprint

Cite this