Information compression and Varshamov-Gilbert bound

DOI10.1016/0890-5401(87)90008-3MaRDI QIDQ1099128zbMATH OpenOpenAlexFDO

Authors Rafail E. Krichevsky

Publication date 1987

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(87)90008-3

zbMATH Keywords

channel with additive noisecollision indexcombinatorial sourceprogram complexity to enumerate a finite set of wordsVarshamov-Gilbert bound of the group error correcting code cardinality

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding theorems (Shannon theory) (94A24)

Review text

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.

Recommendations

• Any code of which we cannot think is good
• scientific article; zbMATH DE number 4023193
• Kolmogorov complexity and the asymptotic bound for error-correcting codes
• A generalized Gilbert-Varshamov bound derived via analysis of a code-search algorithm
• scientific article; zbMATH DE number 3463524

Cites work

• Enumerative source encoding
• Fredman–Komlós bounds and information theory
• scientific article; zbMATH DE number 3934391 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3496008 (Why is no real title available?)
• scientific article; zbMATH DE number 3550176 (Why is no real title available?)
• scientific article; zbMATH DE number 3328173 (Why is no real title available?)
• scientific article; zbMATH DE number 3414194 (Why is no real title available?)
• Information compression and Varshamov-Gilbert bound
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Optimal hashing
• Storing a sparse table
• Storing a Sparse Table with 0 (1) Worst Case Access Time

Cited in

(8)

• Information compression and Varshamov-Gilbert bound
• Entropy compression versus Lovász local lemma
• Kolmogorov complexity and the asymptotic bound for error-correcting codes
• The data compression theorem for ergodic quantum information sources
• Compression of quantum information
• Compression and hadamard power inequalities
• Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression
• Effective entropies and data compression

This page was built for publication: Information compression and Varshamov-Gilbert bound

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