Shuffled belief propagation decoding

Author

Zhang, Juntan ; Fossorier, Marc

Author_Institution

Dept. of Electr. Eng., Hawaii Univ. at Manoa, Honolulu, HI, USA

Volume

1

fYear

2002

fDate

3-6 Nov. 2002

Firstpage

8

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Signals, Systems and Computers, 2002. Conference Record of the Thirty-Sixth Asilomar Conference on

Conference_Location

Pacific Grove, CA, USA

ISSN

1058-6393

Print_ISBN

0-7803-7576-9

Type

conf

DOI

10.1109/ACSSC.2002.1197141

Filename

1197141