| Low-density Parity-check Code |
Website Links For Code |
Information AboutLow-density Parity-check Code |
| CATEGORIES ABOUT LOW-DENSITY PARITY-CHECK CODE | |
| error detection and correction | |
|
Impractical to implement when developed in 1963, LDPC was forgotten. The next 30 or so years of Information Theory failed to produce anything one-third as effective and LDPC remains, in theory, the most effective developed to date (2006). The explosive growth in information technology has produced a corresponding increase of commercial interest in the development of highly efficient data transmission codes as such codes impact everything from signal quality to battery life. Although implementation of LDPC codes has lagged that of other codes, notably the Turbo Code , the absence of encumbering Software Patents has made LDPC attractive to some and LDPC codes are positioned to become a standard in the developing market for highly efficient data transmission methods. In 2003 an LDPC code beat six turbo codes to become the new standard for the satellite transmission of Digital Television . FUNCTION LDPC uses a sparse Parity-check Matrix . This Sparse Matrix is randomly generated, subject to the Sparsity constraints. 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 (i.e. must sum to an even number). 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 LDPC code fragment represents a 3-bit message with 6 bits. The purpose of this redundancy is to aid in recovering from channel errors. Imagine that the 5th message, 101011, is transmitted across a channel
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. REFERENCES
EXTERNAL LINKS
Source code for encoding, decoding, and simulating LDPC codes is available from a variety of locations.
|
|
|