Skip to content

Low-density parity-check codes

Robert G. Gallager

IEEE Transactions on Information Theory · 1962 · 10,887 citationsOpen access

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Gallager, R. G. (1962). Low-density parity-check codes. IEEE Transactions on Information Theory, 8(1), 21–28. https://doi.org/10.1109/tit.1962.1057683

In text: (Gallager, 1962)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

Abstract

A low-density parity-check code is a code specified by a parity-check matrix with the following properties: each column contains a small fixed numberj \geq 3of l's and each row contains a small fixed numberk > jof l's. The typical minimum distance of these codes increases linearly with block length for a fixed rate and fixedj. When used with maximum likelihood decoding on a sufficiently quiet binary-input symmetric channel, the typical probability of decoding error decreases exponentially with block length for a fixed rate and fixedj. A simple but nonoptimum decoding scheme operating directly from the channel a posteriori probabilities is described. Both the equipment complexity and the data-handling capacity in bits per second of this decoder increase approximately linearly with block length. Forj > 3and a sufficiently low rate, the probability of error using this decoder on a binary symmetric channel is shown to decrease at least exponentially with a root of the block length. Some experimental results show that the actual probability of decoding error is much smaller than this theoretical bound.

  1. A Mathematical Theory of Communication1948
  2. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm1967
  3. Communication in the Presence of Noise1949
  4. Factor graphs and the sum-product algorithm2001
  5. The viterbi algorithm1973

Metadata from OpenAlex (CC0). Citations are generated from the published record.