Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Information Theory Workshop (ITW)

Fast decoding algorithm for LDPC over GF(2/sup q/)

Loïc Barnault, David Declercq

Published Mar 2, 2004• 268 citations
Publisher

Abstract

We present a modification of belief propagation that enables us to decode LDPC codes defined on high order Galois fields with a complexity that scales as p log/sub 2/ (p), p being the field order. With this low complexity algorithm, we are able to decode GF(2/sup q/) LDPC codes up to a field order value of 256. We show by simulation that ultra-sparse regular LDPC codes in GF(64) and GF(256) exhibit very good performance.

DOI
10.1109/itw.2003.1216697

Related papers

Decoding Algorithms for Nonbinary LDPC Codes Over GF$(q)$

David Declercq, M.P.C. Fossorier

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

IEEE Transactions on Communications•Apr 1, 2007•724 citations

Modified fast Hadamard transform based belief propagation decoding algorithm

Xueqin Jiang, Moon Ho Lee

In this paper, we propose a new fast Hadamard transform based the belief-propagation (BP) decoding algorithm over GF (2p) with a modification of the permutations between the check nodes and variable nodes. This scheme is mathematically equivalent to the conventional BP decoding algorithm, but complexity of the proposed scheme is lower. We show by simulation that the non-binary regular and irregular LDPC codes in GF (2p) have good performance with our proposed modified BP decoding algorithm.

International Symposium on Communications and Information Technologies•Sep 1, 2009•0 citations

Hardware Implementation of ${\rm GF}(2^{m})$ LDPC Decoders

Christian Spagnol, Emmanuel Popovici, William Peter Marnane

Low density parity check (LDPC) codes over GF(2m) are an extension of binary LDPC codes with significantly higher performance. However, the computational complexity of the encoders/decoders for these codes is also higher. Hence there is a substantial lack of hardware implementations for LDPC over GF(2m) codes. This paper proposes a novel variation of the belief propagation algorithm for GF(2m) LDPC codes. The new algorithm results in a reduced hardware complexity when implemented in VLSI. The serial architecture of the novel decoding algorithm and two other algorithms for LDPC over GF(2m) are implemented on an FPGA. The results show that the proposed algorithm has substantial advantages over existing methods. We show that the implementation of LDPC over GF(2m) decoder is feasible for short to medium length codes. The additional complexity of the decoder is balanced by the superior performance of GF(2m) LDPC codes.

IEEE Transactions on Circuits and Systems I Regular Papers•Mar 10, 2009•69 citations

Hardware Implementation of GF(2 m ) LDPC Decoders.

Christian Spagnol, Emanuel Mihai Popovici, William Peter Marnane

Low Density Parity Check (LDPC) codes over GF(2) are an extension of binary LDPC codes with significantly higher performance. However, the computational complexity of the encoders/decoders for these codes is also higher. Hence there is a substantial lack of hardware implementations for LDPC over GF(2) codes. This paper proposes a novel variation of the belief propagation algorithm for GF(2) LDPC codes. The new algorithm results in a reduced hardware complexity when implemented in VLSI. The serial architecture of the novel decoding algorithm and two other algorithms for LDPC over GF(2) are implemented on an FPGA. The results show that the proposed algorithm has substantial advantages over existing methods. We show that the implementation of LDPC over GF(2) decoder is feasible for short to medium length codes. The additional complexity of the decoder is balanced by the superior performance of GF(2) LDPC codes.

IEEE Transactions on Circuits and Systems•Jan 1, 2009•47 citations

Structured LDPC codes over GF(2/sup m) and companion matrix based decoding

Vidya Kumar, Olgica Milenković, Bane V. Vasic

It is well known that random-like low-density parity-check (LDPC) codes over the extension fields GF(2/sup m/) of GF(2), for m>1, tend to outperform their binary counterparts of comparable length and rate. At the same time, structured LDPC codes offer the advantage of reduced implementation and storage complexity, so that it is of interest to investigate mathematical design methods for codes on graphs over fields of large order. We propose a new class of combinatorially developed codes obtained by properly combining Reed-Solomon (RS) type parity-check matrices and sparse parity-check matrices based on permutation matrices. The proposed codes have large girth and minimum distance. In order to further reduce the decoding complexity of the proposed scheme, we introduce a new decoding algorithm based on matrix representations of the underlying field, which trades performance for complexity. The particular field representation described in this abstract is based on a power basis generated by a companion matrix of a primitive polynomial of the field GF(2/sup m/). It is observed that the choice of the primitive polynomial influences the cycle distribution of the code graph.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•6 citations

Low density parity check codes over GF(q)

Matthew C. Davey, David Mackay

Binary low density parity check (LDPC) codes have been shown to have near Shannon limit performance when decoded using a probabilistic decoding algorithm. The analogous codes defined over finite fields GF(q) of order q>2 show significantly improved performance. We present the results of Monte Carlo simulations of the decoding of infinite LDPC codes which can be used to obtain good constructions for finite codes. We also present empirical results for the Gaussian channel including a rate 1/4 code with bit error probability of 10/sup -4/ at E/sub b//N/sub 0/=-0.05 dB.

IEEE Information Theory Workshop (ITW)•Nov 27, 2002•182 citations
We present a modification of belief propagation that enables us to decode LDPC codes defined on high order Galois fields with a complexity that scales as p log/sub 2/ (p), p being the field order. With this low complexity algorithm, we are able to decode GF(2/sup q/) LDPC codes up to a field order value of 256. We show by simulation that ultra-sparse regular LDPC codes in GF(64) and GF(256) exhibit very good performance.
Decoding Algorithms for Nonbinary LDPC Codes Over GF(q)(q)(q)
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
Hardware Implementation of GF(2m){\rm GF}(2^{m})GF(2m) LDPC Decoders
Low density parity check (LDPC) codes over GF(2m) are an extension of binary LDPC codes with significantly higher performance. However, the computational complexity of the encoders/decoders for these codes is also higher. Hence there is a substantial lack of hardware implementations for LDPC over GF(2m) codes. This paper proposes a novel variation of the belief propagation algorithm for GF(2m) LDPC codes. The new algorithm results in a reduced hardware complexity when implemented in VLSI. The serial architecture of the novel decoding algorithm and two other algorithms for LDPC over GF(2m) are implemented on an FPGA. The results show that the proposed algorithm has substantial advantages over existing methods. We show that the implementation of LDPC over GF(2m) decoder is feasible for short to medium length codes. The additional complexity of the decoder is balanced by the superior performance of GF(2m) LDPC codes.
Low Density Parity Check (LDPC) codes over GF(2) are an extension of binary LDPC codes with significantly higher performance. However, the computational complexity of the encoders/decoders for these codes is also higher. Hence there is a substantial lack of hardware implementations for LDPC over GF(2) codes. This paper proposes a novel variation of the belief propagation algorithm for GF(2) LDPC codes. The new algorithm results in a reduced hardware complexity when implemented in VLSI. The serial architecture of the novel decoding algorithm and two other algorithms for LDPC over GF(2) are implemented on an FPGA. The results show that the proposed algorithm has substantial advantages over existing methods. We show that the implementation of LDPC over GF(2) decoder is feasible for short to medium length codes. The additional complexity of the decoder is balanced by the superior performance of GF(2) LDPC codes.
It is well known that random-like low-density parity-check (LDPC) codes over the extension fields GF(2/sup m/) of GF(2), for m>1, tend to outperform their binary counterparts of comparable length and rate. At the same time, structured LDPC codes offer the advantage of reduced implementation and storage complexity, so that it is of interest to investigate mathematical design methods for codes on graphs over fields of large order. We propose a new class of combinatorially developed codes obtained by properly combining Reed-Solomon (RS) type parity-check matrices and sparse parity-check matrices based on permutation matrices. The proposed codes have large girth and minimum distance. In order to further reduce the decoding complexity of the proposed scheme, we introduce a new decoding algorithm based on matrix representations of the underlying field, which trades performance for complexity. The particular field representation described in this abstract is based on a power basis generated by a companion matrix of a primitive polynomial of the field GF(2/sup m/). It is observed that the choice of the primitive polynomial influences the cycle distribution of the code graph.
Binary low density parity check (LDPC) codes have been shown to have near Shannon limit performance when decoded using a probabilistic decoding algorithm. The analogous codes defined over finite fields GF(q) of order q>2 show significantly improved performance. We present the results of Monte Carlo simulations of the decoding of infinite LDPC codes which can be used to obtain good constructions for finite codes. We also present empirical results for the Gaussian channel including a rate 1/4 code with bit error probability of 10/sup -4/ at E/sub b//N/sub 0/=-0.05 dB.