Information compression and Varshamov-Gilbert bound (Q1099128)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Information compression and Varshamov-Gilbert bound |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Information compression and Varshamov-Gilbert bound |
scientific article |
Statements
Information compression and Varshamov-Gilbert bound (English)
0 references
1987
0 references
The program complexity to enumerate a finite set of words is found. The complexity is either an exponential or a linear function of the word length depending on whether the redundancy is either less or more than 100 \%. A corollary: the Varshamov-Gilbert bound of the group error correcting code cardinality is tight for almost any channel with additive noise. The proofs are based on the concept of the collision index.
0 references
combinatorial source
0 references
program complexity to enumerate a finite set of words
0 references
Varshamov-Gilbert bound of the group error correcting code cardinality
0 references
channel with additive noise
0 references
collision index
0 references
