No label defined (Q4242277)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1285526
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1285526 |
Statements
10 May 1999
0 references
Markov source
0 references
redundancy
0 references
low entropy
0 references
data compression
0 references
0 references
0 references
0.92615974
0 references
0.8756038
0 references
0.8739992
0 references
0.87321115
0 references
0.8691722
0 references
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)].
0 references
