Low-density Parity-check Code
In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel, and is constructed using a sparse bipartite graph. LDPC codes are capacity-approaching codes, which means that practical constructions exist that allow the noise threshold to be set very close (or even arbitrarily close on the BEC) to the theoretical maximum (the Shannon limit) for a symmetric memory-less channel. The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired. Using iterative belief propagation techniques, LDPC codes can be decoded in time linear to their block length.
LDPC codes are finding increasing use in applications requiring reliable and highly efficient information transfer over bandwidth or return channel–constrained links in the presence of data-corrupting noise. Although implementation of LDPC codes has lagged behind that of other codes, notably turbo codes, the absence of encumbering software patents has made LDPC attractive to some.
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.
Read more about Low-density Parity-check Code: History, Applications, Function, Decoding, Code Construction
Famous quotes containing the word code:
“Wise Draco comes, deep in the midnight roll
Of black artillery; he comes, though late;
In code corroborating Calvin’s creed
And cynic tyrannies of honest kings;
He comes, nor parlies; and the Town, redeemed,
Gives thanks devout; nor, being thankful, heeds
The grimy slur on the Republic’s faith implied,
Which holds that Man is naturally good,
And—more—is Nature’s Roman, never to be
scourged.”
—Herman Melville (1819–1891)