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

Europhysics Letters (EPL)

Statistical mechanics of error-correcting codes

Yoshiyuki Kabashima, David Saad

Published Jan 1, 1999• 161 citations
Publisher

Abstract

We investigate the performance of error-correcting codes, where the code word comprises products of K bits selected from the original message and decoding is carried out utilizing a connectivity tensor with C connections per index. Shannon's bound for the channel capacity is recovered for large K and zero temperature when the code rate K / C is finite. Close to optimal error-correcting capability is obtained for finite K and C . We examine the finite-temperature case to assess the use of simulated annealing for decoding and extend the analysis to accommodate other types of noisy channels.

DOI
10.1209/epl/i1999-00137-2

Related papers

Simple Gallager Codes for BSC

Yoshiyuki Kabashima, David Saad

We investigate the performance of Gallager type error- correcting codes for Binary Symmetric Channels, where the code word comprises products of K bits selected from the original message and decoding is carried out utilizing a connectivity tensor with C connections per index. Shannon's bound for the channel capacity is recovered for large K and zero temperature when the code rate K/C is finite. Close to optimal error-correcting capability, with improved decoding properties is obtained for finite K and C.

•Jun 1, 1999•0 citations

Typical Performance of Gallager-Type Error-Correcting Codes

Yoshiyuki Kabashima, Tatsuto Murayama, David Saad

The performance of Gallager's error-correcting code is investigated via methods of statistical physics. In this approach, the transmitted codeword comprises products of the original message bits selected by two randomly constructed sparse matrices; the number of nonzero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity is saturated for many of the codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the Thouless-Anderson-Palmer approach which is identical to the commonly used belief-propagation-based decoding.

arXiv:cond-mat/9908104•Physical Review Letters•Feb 7, 2000•108 citations

Regular and Irregular Gallager-zype Error-Correcting Codes

Yoshiyuki Kabashima, Tatsuto Murayama, David Saad +1 more

The performance of regular and irregular Gallager-type error-correcting code is investigated via methods of statistical physics. The transmitted codeword comprises products of the original message bits selected by two randomly-constructed sparse matrices; the number of non-zero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity may be saturated in equilibrium for many of the regular codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the TAP approach which is identical to the commonly used belief-propagation-based decoding. We show that irregular codes may saturate Shannon's capacity but with improved dynamical properties.

neural information processing systems•Nov 29, 1999•1 citation

Finite temperature error-correcting codes

Pál Ruján

The correspondence between error-correcting convolution codes and gauge invariant spin-glass models is used to show that the optimal way to recover the original message is by decoding at a finite temperature ${\mathit{T}}_{\mathit{N}}$(p)>0, where p is the strength of the channel noise and ${\mathit{T}}_{\mathit{N}}$(p) the Nishimori temperature. This improves upon the retrieval performance of the T=0 maximal likelihood Viterbi decoding algorithm without increasing its computational complexity. Numerical simulations support the theory.

Physical Review Letters•May 10, 1993•130 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•18 citations

Statistical physics of regular low-density parity-check error-correcting codes

Tatsuto Murayama, Yoshiyuki Kabashima, David Saad +1 more

A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.

arXiv:cond-mat/0003121•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Aug 1, 2000•92 citations
We investigate the performance of error-correcting codes, where the code word comprises products of K bits selected from the original message and decoding is carried out utilizing a connectivity tensor with C connections per index. Shannon's bound for the channel capacity is recovered for large K and zero temperature when the code rate K / C is finite. Close to optimal error-correcting capability is obtained for finite K and C . We examine the finite-temperature case to assess the use of simulated annealing for decoding and extend the analysis to accommodate other types of noisy channels.
We investigate the performance of Gallager type error- correcting codes for Binary Symmetric Channels, where the code word comprises products of K bits selected from the original message and decoding is carried out utilizing a connectivity tensor with C connections per index. Shannon's bound for the channel capacity is recovered for large K and zero temperature when the code rate K/C is finite. Close to optimal error-correcting capability, with improved decoding properties is obtained for finite K and C.
The performance of Gallager's error-correcting code is investigated via methods of statistical physics. In this approach, the transmitted codeword comprises products of the original message bits selected by two randomly constructed sparse matrices; the number of nonzero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity is saturated for many of the codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the Thouless-Anderson-Palmer approach which is identical to the commonly used belief-propagation-based decoding.
The performance of regular and irregular Gallager-type error-correcting code is investigated via methods of statistical physics. The transmitted codeword comprises products of the original message bits selected by two randomly-constructed sparse matrices; the number of non-zero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity may be saturated in equilibrium for many of the regular codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the TAP approach which is identical to the commonly used belief-propagation-based decoding. We show that irregular codes may saturate Shannon's capacity but with improved dynamical properties.
The correspondence between error-correcting convolution codes and gauge invariant spin-glass models is used to show that the optimal way to recover the original message is by decoding at a finite temperature TN{\mathit{T}}_{\mathit{N}}TN​(p)>0, where p is the strength of the channel noise and TN{\mathit{T}}_{\mathit{N}}TN​(p) the Nishimori temperature. This improves upon the retrieval performance of the T=0 maximal likelihood Viterbi decoding algorithm without increasing its computational complexity. Numerical simulations support the theory.
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.
A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.