Low-density parity-check code: Difference between revisions

Revision as of 15:07, 9 July 2004

Revision as of 17:52, 23 July 2004

Line 1:

A '''Lowlow-density parity-check code''' or LDPC code is a code that uses a sparse parity-check matrix. This sparse matrix is randomly generated subject to the sparsity constraints. These codes are among the state of the art codes. Decoding them is an [[NP-complete]] problem, but there are good approximate decoders. These codes were first designed by [[Robert G. Gallager|Gallager]] in 1962.

See [[Sparse graph codes]].

Below is a graph fragment of an example LDPC code using Forney's

Line 8 ⟶ 7:

satisfied. Specifically, all lines connecting to an <math>=</math>

box have the same value and the sum of all values connecting to a

<math>+</math> box must sum to zero [[modular arithmetic|modulo]] two.

[[Image:ldpc_code_fragment_factor_graph.png|none]]

If we ignore

Line 16 ⟶ 15:

this LPDC code fragment represents a 3-bit message with 6 bits. The

purpose of this redudnancy is to aid in recovering from channel errors.

Imagine that the 5th message, 101011, is transmitted across a channel