Low-density parity-check code: Difference between revisions

Revision as of 07:17, 19 December 2024

Revision as of 07:18, 19 December 2024

Line 5:

LDPC codes are a class of [[Error correction code|error correction codes]] which (together with the closely-related [[Turbo code|turbo codes]]) have gained prominence in [[coding theory]] and [[information theory]] in the late 1990s. The codes today are widely used in applications ranging from wireless communications to flash-memory storage. Together with turbo codes, they sparked a revolution in coding theory, achieving order-of-magnitude improvements in performance compared to traditional error correction codes<ref>{{Cite web |title=Turbo Codes Explained: History, Examples, and Applications - IEEE Spectrum |url=https://spectrum.ieee.org/turbo-codes |access-date=2024-12-18 |website=spectrum.ieee.org |language=en}}</ref>.

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 ([[Channel capacity|capacities]]) of many channels<ref>{{Cite web |title=Design of capacity-approaching irregular low-density parity-check codes |url=https://ieeexplore.ieee.org/document/910578 |archive-url=http://web.archive.org/web/20240909161749/https://ieeexplore.ieee.org/document/910578/ |archive-date=2024-09-09 |access-date=2024-12-18 |website=ieeexplore.ieee.org |language=en-US}}</ref> at low computation costs.

Theoretically, analysis of the codes focuses on sequences of LDPC codes of fixed [[code rate]] and increasing [[block length]]. These sequences are typically tailored to a set of channels. 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. Furthermore, this can be achieved at a complexity that is linear in the block length.

This theoretical performance is made possible using a flexible design method that is based on sparse [[Tanner graph|Tanner graphs]] (specialized [[bipartite graph|bipartite graphs]]).<ref>{{citation |author=Amin Shokrollahi |url=http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf |title=LDPC Codes: An Introduction |archive-url=https://web.archive.org/web/20170517034849/http://www.ics.uci.edu/~welling/teaching/ICS279/LPCD.pdf |archive-date=2017-05-17}}</ref>