Non-Asymptotic Bounds on Fixed Length Source Coding for Markov Chains

摘要

In this paper, we derive non-asymptotic bounds on the fixed length source coding with/without side-information at the decoder. Our bounds are efficiently computable in the sense that the computational complexity does not depend on the block length, and are also asymptotically optimal in the sense of the large deviation and/or the moderate deviation.