Low-density parity-check code: Difference between revisions

Revision as of 19:10, 12 June 2005

Revision as of 17:10, 23 July 2005

Line 1:

In [[information theory]], aA '''low-density parity-check code (LDPC code)''' is aan [[error correcting code|code]], thata usesmethod aof sparsetransmitting [[parity-checkmessage matrix]].over Thisa [[sparsesignal matrixnoise|noisy]] istransmission randomlychannel. generated, subjectWhile toLDPC theand [[sparsity]]other constraints.error Thesecorrecting codes arecannot amongguarantee perfect transmission, the stateprobability of thelost artinformation codescan (2004)be made as small as desired. Decoding them isLDPC anwas [[NP-complete]]the problem,first butcode thereto areallow gooddata approximatetransmission decoders.rates Theseclose codesto werethe firsttheoretical designedmaximum, bythe [[RobertShannon G. Gallager|GallagerLimit]] in 1962.

Impractical to implement when developed, 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). 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.

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.

See [[sparse graph code]].