Title :
List-Message Passing Achieves Capacity on the q-ary Symmetric Channel for Large q
Author :
Zhang, Fan ; Pfister, Henry D.
Author_Institution :
Texas A&M Univ., College Station
Abstract :
We discuss and analyze a list-message-passing decoder with verification for low-density parity-check (LDPC) codes on the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, we pass lists of possible symbols and mark very likely symbols as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list-size is unbounded, then we find that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q-SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. The probability of false verification is considered for this case, and techniques are discussed to mitigate the problem. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.
Keywords :
channel capacity; channel coding; decoding; linear codes; message passing; optimisation; parity check codes; statistical distributions; LDPC code; binary erasure channel; degree distribution; density evolution equation; list-message-passing decoder; low-density parity-check; optimization; q-ary symmetric channel capacity; symbol probability; Constraint theory; Equations; Error correction codes; Galois fields; Iterative algorithms; Iterative decoding; Linear code; Parity check codes; Reed-Solomon codes; Tornadoes;
Conference_Titel :
Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE
Conference_Location :
Washington, DC
Print_ISBN :
978-1-4244-1042-2
Electronic_ISBN :
978-1-4244-1043-9
DOI :
10.1109/GLOCOM.2007.60