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

IEEE Communications Letters

Low-density parity check codes over GF(q)

Matthew C. Davey, David Mackay

Published Jun 1, 1998• 1,201 citations
Publisher

Abstract

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.

DOI
10.1109/4234.681360

Related papers

Low-Density Parity Check Codes over

Matthew C. Davey, David Mackay

Gallager's 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 for 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 at dB.

•Jan 1, 1998•68 citations

Low density parity check codes over GF(q)

Matthew C. Davey, David Mackay

Binary low density parity check (LDPC) codes have been shown to have near Shannon limit performance when decoded using a probabilistic decoding algorithm. The analogous codes defined over finite fields GF(q) of order q>2 show significantly improved performance. We present the results of Monte Carlo simulations of the decoding of infinite LDPC codes which can be used to obtain good constructions for finite codes. We also present empirical results for the Gaussian channel including a rate 1/4 code with bit error probability of 10/sup -4/ at E/sub b//N/sub 0/=-0.05 dB.

IEEE Information Theory Workshop (ITW)•Nov 27, 2002•182 citations

Good error-correcting codes based on very sparse matrices

David Mackay

We report theoretical and empirical properties of Gallager's (1963) low density parity check codes on Gaussian channels. It can be proved that, given an optimal decoder, these codes asymptotically approach the Shannon limit. With a practical 'belief propagation' decoder, performance substantially better than that of standard convolutional and concatenated codes can be achieved; indeed the performance is almost as close to the Shannon limit as that of turbo codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 22, 2002•175 citations

Improved low-density parity-check codes using irregular graphs

Michael G. Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi +1 more

We construct new families of error-correcting codes based on Gallager's (1973) low-density parity-check codes. We improve on Gallager's results by introducing irregular parity-check matrices and a new rigorous analysis of hard-decision decoding of these codes. We also provide efficient methods for finding good irregular structures for such decoding algorithms. Our rigorous analysis based on martingales, our methodology for constructing good irregular codes, and the demonstration that irregular structure improves performance constitute key points of our contribution. We also consider irregular codes under belief propagation. We report the results of experiments testing the efficacy of irregular codes on both binary-symmetric and Gaussian channels. For example, using belief propagation, for rate 1/4 codes on 16000 bits over a binary-symmetric channel, previous low-density parity-check codes can correct up to approximately 16% errors, while our codes correct over 17%. In some cases our results come very close to reported results for turbo codes, suggesting that variations of irregular low density parity-check codes may be able to match or beat turbo code performance.

IEEE Transactions on Information Theory•Jan 1, 2001•792 citations

Cycle Tanner-graph codes over GF(2/sup b/)

X.-Y. Hu, Evangelos S. Eleftheriou

The average Hamming weight spectrum function of the random ensemble of regular low-density parity-check (LDPC) codes over GF(2/sup b/) when used with binary-input channels is derived. This work confirms theoretically that the near-Shannon-limit performance of Gallager's binary LDPC codes can be significantly enhanced by moving to fields of higher order. We construct a family of error-correcting codes based on the binary representation of GF(2/sup b/) codes defined on a cycle Tanner graph, that appears to be good for both optimum decoding and iterative decoding over binary-input channels.

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2003•5 citations

Iterative decoding of generalized low-density parity-check codes

Michael Lentmaier, K.S. Ziganfirov

A generalization of Gallager's low-density parity-check codes is introduced, where as component codes single-error correcting Hamming codes are used instead of single-error detecting parity-check codes. Low-density (LD) parity-check codes were first introduced by Gallager in 1963. These codes are, in combination with iterative decoding, very promising for achieving low error probabilities at a reasonable cost. Results of computer simulations for long LD codes show, that a performance close to the Shannon capacity limit can be achieved. In this work, we consider a generalized version of low-density parity-check codes, where the decoding procedure can be based on the decoding of Hamming component codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•43 citations
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.
Binary low density parity check (LDPC) codes have been shown to have near Shannon limit performance when decoded using a probabilistic decoding algorithm. The analogous codes defined over finite fields GF(q) of order q>2 show significantly improved performance. We present the results of Monte Carlo simulations of the decoding of infinite LDPC codes which can be used to obtain good constructions for finite codes. We also present empirical results for the Gaussian channel including a rate 1/4 code with bit error probability of 10/sup -4/ at E/sub b//N/sub 0/=-0.05 dB.
We construct new families of error-correcting codes based on Gallager's (1973) low-density parity-check codes. We improve on Gallager's results by introducing irregular parity-check matrices and a new rigorous analysis of hard-decision decoding of these codes. We also provide efficient methods for finding good irregular structures for such decoding algorithms. Our rigorous analysis based on martingales, our methodology for constructing good irregular codes, and the demonstration that irregular structure improves performance constitute key points of our contribution. We also consider irregular codes under belief propagation. We report the results of experiments testing the efficacy of irregular codes on both binary-symmetric and Gaussian channels. For example, using belief propagation, for rate 1/4 codes on 16000 bits over a binary-symmetric channel, previous low-density parity-check codes can correct up to approximately 16% errors, while our codes correct over 17%. In some cases our results come very close to reported results for turbo codes, suggesting that variations of irregular low density parity-check codes may be able to match or beat turbo code performance.
The average Hamming weight spectrum function of the random ensemble of regular low-density parity-check (LDPC) codes over GF(2/sup b/) when used with binary-input channels is derived. This work confirms theoretically that the near-Shannon-limit performance of Gallager's binary LDPC codes can be significantly enhanced by moving to fields of higher order. We construct a family of error-correcting codes based on the binary representation of GF(2/sup b/) codes defined on a cycle Tanner graph, that appears to be good for both optimum decoding and iterative decoding over binary-input channels.
A generalization of Gallager's low-density parity-check codes is introduced, where as component codes single-error correcting Hamming codes are used instead of single-error detecting parity-check codes. Low-density (LD) parity-check codes were first introduced by Gallager in 1963. These codes are, in combination with iterative decoding, very promising for achieving low error probabilities at a reasonable cost. Results of computer simulations for long LD codes show, that a performance close to the Shannon capacity limit can be achieved. In this work, we consider a generalized version of low-density parity-check codes, where the decoding procedure can be based on the decoding of Hamming component codes.