Monday, October 30, 2006

Low-density parity-check code

A low-density parity-check code (LDPC code) is an error correcting code, a method of transmitting a message over a noisy transmission channel[1][2]. While LDPC and other error correcting codes cannot guarantee perfect transmission, the probability of lost information can be made as small as desired. LDPC was the first code to allow data transmission rates close to the theoretical maximum, the Shannon Limit. Impractical to implement when developed in 1963, LDPC codes were forgotten[3]. 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.

LDPC codes are also known as Gallager codes, in honor of Robert G. Gallager, who developed the LDPC concept in his doctoral dissertation at MIT in 1960.