We present a theoretical method for a direct evaluation of the average error exponent in Gallager error-correcting codes using methods of statistical physics. Results for the binary symmetric channel(BSC)are presented for codes of both finite and infinite connectivity.
We review recent theoretical progress on the statistical mechanics of error correcting codes, focusing on low-density parity-check (LDPC) codes in general, and on Gallager and MacKay–Neal codes in particular. By exploiting the relation between LDPC codes and Ising spin systems with multi-spin interactions, one can carry out a statistical mechanics based analysis that determines the practical and theoretical limitations of various code constructions, corresponding to dynamical and thermodynamical transitions, respectively, as well as the behaviour of error-exponents averaged over the corresponding code ensemble as a function of channel noise. We also contrast the results obtained using methods of statistical mechanics with those derived in the information theory literature, and show how these methods can be generalized to include other channel types and related communication problems.
Abstract The error exponent of the regular graph-based binary low-density parity-check (LDPC) codes under the maximum likelihood (ML) decoding algorithm in the binary symmetric channel (BSC) is analyzed. Unlike most other papers where error exponents are considered for the case when the length of LDPC codes tends to infinity (asymptotic analysis), the finite length case (finite length analysis) is considered. In this paper, a method of deriving the lower bound on the error exponent for a regular graph-based LDPC code with finite length under ML decoding is described. Also we analyze Dependences of the error exponent on various LDPC code parameters are also analyzed. The numerical results obtained for the considered lower bound are represented and analyzed at the end of the paper.
Gallager's (1962) low-density binary parity check codes have been shown to have near-Shannon limit performance when decoded using a probabilistic decoding algorithm. We report the empirical results of error-correction using the analogous codes over GF(q) for q>2, with binary symmetric channels and binary Gaussian channels. We find a significant improvement over the performance of the binary codes, including a rate 1/4 code with bit error probability <10/sup -5/ at E/sub b//N/sub 0/=0.2 dB.