Low-density parity-check code: Difference between revisions

Revision as of 03:40, 5 December 2023

Revision as of 16:35, 5 December 2023

Line 150:

==Decoding==

{{Unreferenced section|date=May 2023}}

As with other codes, the [[maximum likelihood decoding]] of an LDPC code on the [[binary symmetric channel]] is an [[NP-complete]] problem.,<ref>{{cite journal |title=On the Inherent Intractability of Certain Coding Problems |author= Robert McEliece, [[Elwyn Berlekamp|E. R. Berlekamp]] and H. Van Tilborg |journal=IEEE Trans. Inf. Theory |year=1978 |pages=384–386 |publisher=IEEE |doi=10.1109/TIT.1978.1055873}}</ref> Performingshown by reduction from [[3-dimensional matching]]. So assuming [[P versus NP problem|P != NP]], which is widely believed, then performing optimal decoding for aan NP-completearbitrary 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. The sub-optimal decoding techniques view each parity check that makes up the LDPC as an independent single parity check (SPC) code. Each SPC code is decoded separately using [[Soft-in soft-out decoder|soft-in-soft-out]] (SISO) techniques such as [[Soft output Viterbi algorithm|SOVA]], [[BCJR algorithm|BCJR]], [[Maximum a posteriori estimation|MAP]], and other derivates thereof. The soft decision information from each SISO decoding is cross-checked and updated with other redundant SPC decodings of the same information bit. Each SPC code is then decoded again using the updated soft decision information. This process is iterated until a valid codeword is achieved or decoding is exhausted. This type of decoding is often referred to as sum-product decoding.