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. An LDPC is constructed using a sparse
bipartite graph. LDPC codes are , 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 memoryless 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.