Decoding Algorithms for Nonbinary LDPC Codes Over GF$(q)$
David Declercq, M.P.C. Fossorier · IEEE Transactions on Communications · 2007
In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes
Cited by 724 works. doi:10.1109/tcomm.2007.894088
Authors
References
- Low-density parity-check codes
- Low-Density Parity-Check Codes
- Factor graphs and the sum-product algorithm
- Design of capacity-approaching irregular low-density parity-check codes
- The capacity of low-density parity-check codes under message-passing decoding
- A recursive approach to low complexity codes
- Probability of Error for Optimal Codes in a Gaussian Channel
- Codes and Decoding on General Graphs
- Efficient erasure correcting codes
- On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit