Asymptotic Redundancy of the MTF Scheme for Staitonary Ergodic Sources

Mitsuharu Arimura and Hirosuke Yamamoto

IEEE Trans. on Information Theory, Vol. 51, No.11, pp.3742-3752, Nov. 2005

  • The Move-to-front (MTF) scheme is a data-compression method which converts each symbol of a source sequence to a positive integer sequentially, and encodes it to a binary codeword. The compression performance of this algorithm has been analyzed usually under the assumption of the so-called symbol extension. But, in this paper, upper and lower bounds are derived for the redundancy of the MTF scheme without the symbol extension for stationary ergodic sources and Markov sources. It is also proved that for the stationary ergodic first-order Markov sources, the MTF scheme can attain the entropy rate if and only if the transition matrix of the source is a kind of doubly stochastic matrix. Moreover, if the source is a$K$th-order Markov source$(K geq 2)$, the MTF scheme cannot attain the entropy rate of the source generally.
  • Index Terms\Asymptotic redundancy, double stochastic process, Markov sources, move-to-front (MTF) scheme, stationary ergodic sources.
  • DOI: 10.1109/TIT.2005.856941

ƒy[ƒW‚ฬƒgƒbƒv‚ึ