low-density parity-check code

In information theory, a low-density parity-check code (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 (2004). 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 code. 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 all values connecting to a

+

box must sum to zero modulo two. 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. 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. none Now that we have decoded the 4th bit, we realize that the 1st bit must be a 1 to satisfy the leftmost constraint. none Thus we are able to iteratively decode the message encoded with our LDPC code.

External links

Source code for encoding, decoding, and simulating LDPC codes is available from a variety of locations.

<< Previous

Word Browser

Next >>

gerald s. hawkins
philip livingston (1686 1749)
post office ltd
interstate 285
hillman
quebec general election, 1936
robert pastorelli
new brunswick highway 15
minced oath
michael snow
magic joe

silvio dante
holly short
quebec general election, 1935
nazca plate
chinese patriotic catholic association
paulie walnuts
quebec general election, 1931
mega zine
fluorescein
quebec general election, 1927
harbourfront

fluorescence spectroscopy
quebec general election, 1923
pinnacle systems
junior soprano
quebec general election, 1919
quebec general election, 1916
quebec general election, 1912
computer and video game genres
quebec general election, 1908
list of pinnacle systems products
chesterfield, new jersey

quebec general election, 1904
monochromator
adriana la cerva
quebec general election, 1900
setsubun
rayleigh quotient iteration
from the earth to the moon (hbo)
cinwave
quebec general election, 1897
minigame
list of bridges in canada