scientific article; zbMATH DE number 1285526

MaRDI QIDQ4242277zbMATH OpenFDO

Authors M. P. Sharova

Publication date 10 May 1999

zbMATH Keywords

data compressionlow entropyMarkov sourceredundancy

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Statistical aspects of information-theoretic topics (62B10) Information storage and retrieval of data (68P20) Source coding (94A29)

Review text

The author suggests a method of coding of a finite-state Markov source which provides an arbitrary prescribed redundancy. This coding is efficient for a Markov source with a low but positive entropy. A binary finite-state Markov source has a low entropy if \( p=\max\limits_{s\in S}\min\bigl(p(1\mid{}s),p(0\mid{}s)\bigr)\) is small. Here \(S\) is the set of states. The average time of encoding and decoding per one symbol is equal to \[ O\Bigl(\sqrt{p} \log^3\tfrac{1}{r}\log\log\tfrac{1}{r}\Bigr) \] bit-operations, where \(r>0\) is a given redundancy. A similar method is also proposed for a Bernoulli source with a finite alphabet. This method is based on a fast code proposed by \textit{B. Ya. Ryabko} [IEEE Trans. Inf. Theory 40, No. 1, 96-99 (1994; Zbl 0803.94007)].

Recommendations

• Fast coding of low-entropy sources
• Fast encoding of low-entropy sources
• Coding low-entropy Markov sources with unknown statistics
• scientific article; zbMATH DE number 1285527
• Noiseless coding of binary finite-order Markov sources (Corresp.)
• Entropy preservation under Markov coding.
• Universal coding algorithm for a family of context Markov sources
• scientific article; zbMATH DE number 5941301
• Variable to fixed-length codes for Markov sources
• On asymptotically optimal methods of prediction and adaptive coding for Markov sources

Cited in

(16)

• Fast encoding of low-entropy sources
• On asymptotically optimal methods of prediction and adaptive coding for Markov sources
• An effective method for encoding information sources using the fast multiplication algorithm
• Noiseless coding of binary finite-order Markov sources (Corresp.)
• Asymptotic Redundancy of the MTF Scheme for Stationary Ergodic Sources
• Efficient Source Decoding Over Memoryless Noisy Channels Using Higher Order Markov Models
• Symbol-Based Modeling and Coding of Block Markov Sources
• Über die implementierung redundanzfreier Codes zur datenverschlüsselung
• Source matching problems revisited
• scientific article; zbMATH DE number 1285527 (Why is no real title available?)
• Fast and efficient coding of information sources
• scientific article; zbMATH DE number 1498788 (Why is no real title available?)
• Fast coding of low-entropy sources
• Data Compression for a Source with Markov Characteristics
• scientific article; zbMATH DE number 6460053 (Why is no real title available?)
• Entropy preservation under Markov coding.

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 Q4242277)