Low-density parity-check code: Difference between revisions

Revision as of 17:27, 23 July 2005

Revision as of 20:44, 12 August 2005

Line 1:

A '''low-density parity-check code (LDPC code)''' is an [[error correcting code]], a method of transmitting message over a [[signal noise|noisy]] transmission channel. 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 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 (2005).

of [[information theory]] failed to produce anything one-third as effective and LDPC remains, in theory, the most effective developed to date (2005). The explosive growth in information technology has produced a corresponding increase of commercial interest 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.

of [[information theory]] failed to produce anything one-third as effective and LDPC remains, in theory, the most effective developed to date (2005). The explosive growth in information technology has produced a corresponding increase of commercial interest 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.

==Function==

LDPC 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 [[Robert G. Gallager|Gallager]] in 1962.

Line 40 ⟶ 41:

==External links==

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

available from a variety of locations.

* [http://www.eccpage.com/ The Error Correcting Codes (ECC) Page]