scientific article; zbMATH DE number 1285527

From MaRDI portal
Publication:4242278





The problem of coding a binary Markov source with unknown statistics is studied. An effective scheme of low-entropy source coding is proposed. A finite-state Markov source has low entropy if \( p'=\max\limits_{s\in S}p(1\mid{}s)\) is small, where \(S\) is the set of states. The method of coding provides an arbitrary prescribed redundancy \(r>0\). The average time of encoding and decoding per one symbol is equal to \[ O\Bigl(\frac{p'}{\sqrt{p(1)}}\log^3\frac{1}{r}\log\log\frac{1}{r}\Bigr) \] bit-operations. This method uses the sliding window of length \(2/r\) and is based on a fast code by \textit{B. Ya. Ryabko} [IEEE Trans. Inf. Theory 40, No. 1, 96-99 (1994; Zbl 0803.94007)].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4242278)