Low-density parity-check code

The codes today are widely used in applications ranging from wireless communications to flash-memory storage.

[1] Central to the performance of LDPC codes is their adaptability to the iterative belief propagation decoding algorithm.

Under this algorithm, they can be designed to approach theoretical limits (capacities) of many channels[2] at low computation costs.

For appropriately designed sequences, the decoding error under belief propagation can often be proven to be vanishingly small (approaches zero with the block length) at rates that are very close to the capacities of the channels.

Gallager devised the codes in his doctoral dissertation at the Massachusetts Institute of Technology in 1960.

[4][5] The codes were largely ignored at the time, as their iterative decoding algorithm (despite having linear complexity), was prohibitively computationally expensive for the hardware available.

Over the binary erasure channel, code sequences were designed at rates arbitrary close to channel capacity, with provably vanishing decoding error probability and linear decoding complexity.

[citation needed] In 2008, LDPC beat convolutional turbo codes as the forward error correction (FEC) system for the ITU-T G.hn standard.

[15] LDPC codes are also used for 10GBASE-T Ethernet, which sends data at 10 gigabits per second over twisted-pair cables.

[20][21] Although LDPC code has had its success in commercial hard disk drives, to fully exploit its error correction capability in SSDs demands unconventional fine-grained flash memory sensing, leading to an increased memory read latency.

Since then, LDPC has been widely adopted in commercial SSDs in both customer-grades and enterprise-grades by major storage venders.

A fast hard-decode (binary erasure) is first attempted, which can fall back into the slower but more powerful soft decoding.

This sparse matrix is often randomly generated, subject to the sparsity constraints—LDPC code construction is discussed later.

The bits of a valid message, when placed on the T's at the top of the graph, satisfy the graphical constraints.

This LDPC code fragment represents a three-bit message encoded as six bits.

A single copy of the original data (S0,K-1) is transmitted with the parity bits (P) to make up the code symbols.

The repeat and distribute operations perform the function of the interleaver in the turbo code.

As a practical matter, the hardware that forms the accumulators is reused during the encoding process.

So assuming P != NP, which is widely believed, then performing optimal decoding for an arbitrary code of any useful size is not practical.

However, sub-optimal techniques based on iterative belief propagation decoding give excellent results and can be practically implemented.

Each SPC code is decoded separately using soft-in-soft-out (SISO) techniques such as SOVA, BCJR, MAP, and other derivates thereof.

In contrast, belief propagation on the binary erasure channel is particularly simple where it consists of iterative constraint satisfaction.

For example, consider that the valid codeword, 101011, from the example above, is transmitted across a binary erasure channel and received with the first and fourth bit erased to yield ?01?11.

In order to proceed with decoding the message, constraints connecting to only one of the erased bits must be identified.

], there has also been a great deal of work spent studying the effects of alternative schedules for variable-node and constraint-node update.

Highly reliable nodes, whose log-likelihood ratio (LLR) magnitude is large and does not change significantly from one update to the next, do not require updates with the same frequency as other nodes, whose sign and magnitude fluctuate more widely.

[citation needed] These scheduling algorithms show greater speed of convergence and lower error floors than those that use flooding.

These lower error floors are achieved by the ability of the Informed Dynamic Scheduling (IDS)[25] algorithm to overcome trapping sets of near codewords.

[citation needed] For large block sizes, LDPC codes are commonly constructed by first studying the behaviour of decoders.

[citation needed] The construction of a specific LDPC code after this optimization falls into two main types of techniques:[citation needed] Construction by a pseudo-random approach builds on theoretical results that, for large block size, a random construction gives good decoding performance.