Low-density parity-check code: Difference between revisions

Revision as of 07:20, 26 March 2004

Revision as of 15:07, 9 July 2004

Line 1:

A '''Low-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

{{msg:stub}}

factor graph notation. A message is encoded by placing bits on the

'''T's''' at the top such that the graphical constraints are

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 [[modulo]] two.

[[Image:ldpc_code_fragment_factor_graph.png|none]]

If we ignore

constraints for lines going out of the picture, then there are 8

possible 6 bit strings which correspond to valid codewords: (i.e.,

000000, 011001, 110010, 111100, 101011, 100101, 001110, 010111). Thus

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

and received with the 1st and 4th bit erased to yield *01*11. We know

that the transmitted message must have satisfied the code constraints

which we can represent by writing the received message on the top of

the factor graph as shown below.

[[Image:ldpc_code_fragment_factor_graph_w_erasures.png|none]]

We can now solve for the missing bits using an algorithm which is

commonly referred to as [[belief propagation]]. In this case, the

first step of belief propagation is to realize that the 4th bit must

be 0 to satisfy the middle constraint.

[[Image:ldpc_code_fragment_factor_graph_w_erasures_decode_step_1.png|none]]

Now that we have decoded the 4th bit, we realize that the 1st bit must

be a 1 to satisfy the leftmost constraint.

[[Image:ldpc_code_fragment_factor_graph_w_erasures_decode_step_2.png|none]]

Thus we are able to iteratively decode the message encoded with our

LDPC code.

Source code for encoding, decoding, and simulating LDPC codes is

available from a variety of locations.

* http://freshmeat.net/projects/pycodes/ (LDPC Codes in Python and C)

* http://www.eccpage.com/ (Error Correcting Codes Home Page)