Content deleted Content added
Open access status updates in citations with OAbot #oabot |
Citation bot (talk | contribs) Added url. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 475/933 |
||
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|url= https://resolver.caltech.edu/CaltechAUTHORS:BERieeetit78 }}</ref> shown by reduction from [[3-dimensional matching]]. So assuming [[P versus NP problem|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. 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.
| |||