Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:cond-mat/9906011 · Physical Review Letters

Error-Correcting Codes That Nearly Saturate Shannon's Bound

Ido Kanter, David Saad

Published Sep 27, 1999• 55 citations
arXivHTMLPDF

Abstract

Gallager-type error-correcting codes that nearly saturate Shannon's bound are constructed using insight gained from mapping the problem onto that of an Ising spin system. The performance of the suggested codes is evaluated for different code rates for both finite and infinite message lengths.
DOI
10.1103/physrevlett.83.2660

Related papers

Class of quantum error-correcting codes saturating the quantum Hamming bound

Daniel Gottesman

I develop methods for analyzing quantum error-correcting codes, and use these methods to construct an infinite class of codes saturating the quantum Hamming bound. These codes encode k=n-j-2 quantum bits (qubits) in n=${2}^{\mathit{j}}$ qubits and correct t=1 error. \textcopyright{} 1996 The American Physical Society.

arXiv:quant-ph/9604038•Physical Review A•Sep 1, 1996•1,266 citations

Finite-size effects and error-free communication in Gaussian channels

Ido Kanter, David Saad

The efficacy of a specially constructed Gallager-type error-correcting code to communication in a Gaussian channel is being examined. The construction is based on the introduction of complex matrices, used in both encoding and decoding, which comprise sub-matrices of cascading connection values. The finite size effects are estimated for comparing the results to the bounds set by Shannon. The critical noise level achieved for certain code-rates and infinitely large systems nearly saturates the bounds set by Shannon even when the connectivity used is low.

arXiv:cond-mat/9907424•Journal of Physics A Mathematical and General•Feb 22, 2000•17 citations

On the Hamming bound for nonbinary localized-error-correcting codes

Leonid Alexandrovich Bassalygo, M.S. Pinsker, Rudolf Ahlswede

Problems of Information Transmission•Jan 1, 1999•5 citations

Belief revision and small loops in Gallager-type error-correcting codes

Doubez, M.

Gallager-type error-correcting codes are low density parity check codes (LDPC) which may in specific case nearly saturate Shannon’s bound. They are based on the construction of two very sparse matrices, various structures of which have been studied in recent years. We will mainly focus here on constructions that have recently been studied by Kanter and Saad. The aim of this project is to examine the performance of two different decoding LDPC algorithms, belief propagation and belief revision within this framework, as well as that of different coding methods (MN vs. Gallager codes).We will also look at the effect of removing small loops in the matrices on the code’s performance.

•Jan 1, 2000•0 citations

Construction of some new entanglement-assisted quantum error-correcting codes of large lengths

Meng Cao, Fuchuan Wei

Discrete Mathematics•Mar 19, 2024•8 citations

Tighter decoding reliability bound for Gallager’s error-correcting code

Yoshiyuki Kabashima, Naoya Sazuka A, Kazutaka Nakamura +1 more

Statistical physics is employed to evaluate the performance of error-correcting codes in the case of finite message length for an ensemble of Gallager's error correcting codes. We follow Gallager's approach of upper bounding the average decoding error rate, but invoke the replica method to reproduce the tightest general bound to date, and to improve on the most accurate zero-error noise level threshold reported in the literature. The relation between the methods used and those presented in the information theory literature are explored.

arXiv:cond-mat/0010173•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Sep 21, 2001•26 citations
I develop methods for analyzing quantum error-correcting codes, and use these methods to construct an infinite class of codes saturating the quantum Hamming bound. These codes encode k=n-j-2 quantum bits (qubits) in n=2j{2}^{\mathit{j}}2j qubits and correct t=1 error. \textcopyright{} 1996 The American Physical Society.
The efficacy of a specially constructed Gallager-type error-correcting code to communication in a Gaussian channel is being examined. The construction is based on the introduction of complex matrices, used in both encoding and decoding, which comprise sub-matrices of cascading connection values. The finite size effects are estimated for comparing the results to the bounds set by Shannon. The critical noise level achieved for certain code-rates and infinitely large systems nearly saturates the bounds set by Shannon even when the connectivity used is low.
Gallager-type error-correcting codes are low density parity check codes (LDPC) which may in specific case nearly saturate Shannon’s bound. They are based on the construction of two very sparse matrices, various structures of which have been studied in recent years. We will mainly focus here on constructions that have recently been studied by Kanter and Saad. The aim of this project is to examine the performance of two different decoding LDPC algorithms, belief propagation and belief revision within this framework, as well as that of different coding methods (MN vs. Gallager codes).We will also look at the effect of removing small loops in the matrices on the code’s performance.
Statistical physics is employed to evaluate the performance of error-correcting codes in the case of finite message length for an ensemble of Gallager's error correcting codes. We follow Gallager's approach of upper bounding the average decoding error rate, but invoke the replica method to reproduce the tightest general bound to date, and to improve on the most accurate zero-error noise level threshold reported in the literature. The relation between the methods used and those presented in the information theory literature are explored.