Efficient Message Passing Decoding Using Vector-based Messages


  • Grimnell Mikael
  • Tjäder Mats

Publish date: 2006-01-01

Report number: FOI-R--1963--SE

Pages: 98

Written in: English


Low-Density Parity-Check (LDPC) codes provide strong error correction capability. Early LDPC-work concentrated on the binary Galois Field, GF(2), but here we consider higher order alphabets, GF(q). The code symbols from GF(q) are mapped to M-ary Phase Shift Keying (M-PSK) signals to yield higher spectral efficiency. LDPC codes are commonly decoded using the Message Passing (MP) algorithm, which is an iterative algorithm that passes messages between nodes in a graph representation of the code. Unfortunately, the computational complexity of the optimal MP decoder, the Belief Propagation (BP) decoder, scales as the square of the order of the used Galois Field. To reduce complexity, we investigate a number of simplified MP decoders. Since the information of a PSK signal is found in the phase angle, geometrical vectors and angles are used as messages in the decoders. A promising simplification is the Table Vector Decoder, which approximates the check node operation of a BP decoder by table lookup. The complexity of table-based decoders is unaffected by size of the used Galois Field. For well-designed tables, the table-based decoders suffer only minor losses compared to the optimal Belief Propagation (BP) decoders. We also investigate the theoretical decoding properties using Density Evolution analysis.