Title :
Shuffled belief propagation decoding
Author :
Zhang, Juntan ; Fossorier, Marc
Author_Institution :
Dept. of Electr. Eng., Hawaii Univ. at Manoa, Honolulu, HI, USA
Abstract :
In this paper, we propose a shuffled version of the belief propagation (BP) algorithm for the decoding of low-density parity-check (LDPC) codes. We show that when the Tanner graph of the code is acyclic and connected, the proposed scheme is optimal in the sense of MAP decoding and converges faster (or at least no slower) than the standard BP algorithm. Interestingly, this new version keeps the computational advantages of the forward-backward implementations of BP decoding. Both serial and parallel implementations are considered. We show by simulation that the new schedule offers better performance/complexity trade-offs.
Keywords :
computational complexity; graph theory; maximum likelihood decoding; maximum likelihood estimation; parity check codes; BP algorithm; LDPC codes; MAP decoding; Tanner graph; computational complexity; forward-backward implementations; low-density parity-check codes; maximum a posteriori probability; parallel implementation; serial implementation; shuffled belief propagation decoding; Belief propagation; Code standards; Computational modeling; Concurrent computing; Iterative algorithms; Iterative decoding; Parallel processing; Parity check codes; Processor scheduling; Standards development;
Conference_Titel :
Signals, Systems and Computers, 2002. Conference Record of the Thirty-Sixth Asilomar Conference on
Conference_Location :
Pacific Grove, CA, USA
Print_ISBN :
0-7803-7576-9
DOI :
10.1109/ACSSC.2002.1197141