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 Gallager in 1962.
See Sparse graph codes.
Below is a graph fragment of an example LDPC code using Forney's
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
box have the same value and the sum of all values connecting to a
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.
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.
Now that we have decoded the 4th bit, we realize that the 1st bit must
be a 1 to satisfy the leftmost constraint.
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.
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.
We can now solve for the missing bits using an algorithm which is
commonly referred to as 
Now that we have decoded the 4th bit, we realize that the 1st bit must
be a 1 to satisfy the leftmost constraint.
Thus we are able to iteratively decode the message encoded with our
LDPC code.