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 International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)

Fast and Reduced-Complexity Decoding Rule for qary LDPC Codes by Using the Duality Properties

Alaa Ghaith, Joseph J. Boutros, Yi Yuan-Wu

Published Sep 22, 2006• 2 citations
Publisher

Abstract

The paper studies symbol-by-symbol maximum a posteriori (MAP) decoding algorithms for non binary codes over an extension field GF(q). This decoding rule minimizes the probability of symbol error over a time-discrete memory less channel by employing the dual code. It is shown that these algorithms meet all requirements needed for iterative decoding as the output of the decoder can be split into three independent estimates: soft channel value, a priori term and extrinsic value. It represents a better form of coding for the q-ary LDPC codes, which have been shown to outperform binary LDPC codes and Reed-Solomon codes on the AWGN channel and it gives us a new fast and reduced-complexity decoding algorithm. The complexity of this rule varies inversely with code rate, making the technique particularly attractive for high rate codes. Finally, we see that complexity is reduced by using the dual code, and the algorithm is accelerated by using the fast Hadamard transform (FHT). Examples are given for both single parity check (non iterative case) and LDPC (iterative case) non binary codes

DOI
10.1109/wimob.2006.1696346

Related papers

Reduced complexity and improved performance decoding algorithm for nonbinary LDPC codes over GF(q)

Xin Chen, Aidong Men

Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.

IEEE International Conference on Communication Technology (ICCT)•Nov 1, 2008•6 citations

Low Complexity Bit Reliability and Predication Based Symbol Value Selection Decoding Algorithms for Non-Binary LDPC Codes

Waheed Ullah, Ling Cheng, Fambirai Takawira

The main challenge for hardware implementation of non-binary LDPC decoding is the high computational complexity and large memory requirement. To address this challenge, five new low complexity LDPC decoding algorithms are proposed in this paper. The proposed algorithms are developed specifically towards the low complexity, yet effective, decoding of the NB LDPC codes. The proposed decoding algorithms update, iteratively, the hard decision received vector to search for the valid codeword in the vector space of Galois field ${(GF)}$ . The selection criterion for least reliable symbol positions is based on the information from the failed checks and the reliability information from the Galois field structure as well as from the received channel soft information. To choose the correct value for the candidate symbol, two methods are used. The first method is based on the prediction of the error symbol from the set of Galois field symbols which maximize an objective function. In the second method, individual bits are flipped based on the reliability information obtained from the channel. Algorithms 1 and 2 flip a single symbol per iteration whilst the other three algorithms 3, 4 and 5 flip multiple symbols in each iteration. The proposed voting based Algorithms 1, 2 and 5 first short list the unreliable positions using a majority voting scheme and then choose the candidate symbol value from the set of the symbols in ${GF(q)}$ while not violating the field order ${q}$ . These methods simplify the decoding complexity in terms of computation and memory. Results and analysis of these algorithms show an appealing tradeoff between computational complexity and bit error rate performance for NB LDPC codes.

IEEE Access•Jan 1, 2020•13 citations

Design of Low Complexity Non-Binary LDPC Codes with an Approximated Performance-Complexity Tradeoff

Yang Yu, Wen Chen

By presenting an approximated performance-complexity tradeoff (PCT) algorithm, a low-complexity non-binary low density parity check (LDPC) code over q-ary-input symmetric-output channel is designed in this manuscript which converges faster than the threshold-optimized non-binary LDPC codes in the low error rate regime. We examine our algorithm by both hard and soft decision decoders. Moreover, simulation shows that the approximated PCT algorithm has accelerated the convergence process by 30% regarding the number of the decoding iterations.

arXiv:2003.00714•IEEE Communications Letters•Feb 22, 2012•9 citations

Fast Fourier Transform simplified soft-distance decoding algorithm for decoding non-binary LDPC codes

Leonardo J. Arnone, Carlos Arturo Gayoso, C. M. Gonzalez +3 more

Non-Binary Low-Density Parity-Check (NB-LDPC) codes have been shown to outperform equivalent LDPC codes defined over the binary field, especially when they are designed in high order Galois fields GF(q). This however leads to an increased decoding complexity.

Argentine School of Micro-Nanoelectronics, Technology and Applications•Jul 1, 2014•2 citations

Scheduling Strategies for Non-Binary LDPC Codes

Orange Labs

Non-binary LDPC codes are promising error cor- recting codes for short and moderate block lengths. These codes demonstrate interesting performances in high order fields, though are more complex to decode. As for binary LDPC codes, decoding scheduling can be optimized to improve performance. In this paper, a simulation-based approach is used for different scheduling policies in the non-binary case in order to point out possible performance gains for these codes. An optimization of decoding scheduling is also proposed and exhibits about 20% complexity reduction in error-floor region, thus promising interesting gains if combined with advanced dynamic scheduling strategies. I. INTRODUCTION Channel coding has seen important developments over the last two decades. Thanks to the introduction of advanced error- correcting codes, initiated by Turbo-codes in the early 90's, and to the use of iterative decoding techniques, Shannnon- limit performance has been closely approached. Low-Density Parity-Check (LDPC) codes, first introduced by Gallager (1) in the 60's, were rediscovered by Mackay and Neal (2) in 1996. Excellent error-correcting performance for long block lengths (3) position LDPC codes as an important candidate for advanced communication systems, already adopted in different standards, such as DVB-S2, IEEE 802.16 and 802.11n. How- ever, as codewords become shorter, LDPC performance gains are generally less satisfying. Non-binary LDPC codes, though more complex, proved to significantly improve performance for moderate and short blocklengths (4), (5). The use of a high order alphabet also suggests matching it with the modulation alphabet: LDPC codes over a 16�elements Galois field for example can be naturally mapped in 16�QAM modulated symbols. This would avoid the bit-to-symbol performance loss, especially when having a frequency selective channel, as non- binary encoding can reduce channel memory effect (6). This use of non-binary LDPC codes is thus very promising for high data rate communications, especially when complexity reduc- tion techniques are adopted, either for decoding update rules or scheduling policy. Previous work on scheduling strategies for the binary case can be found in (7). In this paper, we will first address a brief overview of decoding techniques for LDPC codes over high order extension fields. Then, scheduling strategies and effects will be compared for the non-binary case. A simulation-based approach will also be detailed to suggest new scheduling policies, and results from an optimized scheduling will be presented. The paper will be concluded by some remarks and suggestions towards future works.

•Jan 1, 2009•0 citations

FFT based sum product decoding algorithm of LDPC coder for GF(q)

Jigisha N. Patel, Neeta Chapatwala, Mrugesh Patel

Low Density Parity Check (LDPC) codes have excellent error correcting performance. LDPC codes are one of the block coding techniques and it performs near Shannon limit and recommended for many practical applications. Non-binary LDPC codes extension of binary LDPC in error correcting property especially for short and moderate block length. In many digital communication systems these codes have strong competitors of turbo codes for error control. Low Density Parity Check as it name is suggests that in a parity check matrix (H) consists of very small number of non-zero elements comparing with zero elements. The strength of the LDPC code defines Parity Check Matrix (PCM). LDPC code contains two types of decoding algorithms hard and soft decision algorithm. By comparing with other traditional decoding algorithm FFT based sum product algorithm reduced computation complexity with better decoding performance. In this paper, LDPC codes for FFT based sum product decoding algorithm performances are analysed for various order of Galois Field GF(q) using AWGN channel. Decoding performance measured in terms of symbol error rate which improve with increasing order of Galois field.

International Conference on Emerging Technology Trends in Electronics, Communication and Networking (ET2ECN)•Dec 1, 2014•3 citations
The paper studies symbol-by-symbol maximum a posteriori (MAP) decoding algorithms for non binary codes over an extension field GF(q). This decoding rule minimizes the probability of symbol error over a time-discrete memory less channel by employing the dual code. It is shown that these algorithms meet all requirements needed for iterative decoding as the output of the decoder can be split into three independent estimates: soft channel value, a priori term and extrinsic value. It represents a better form of coding for the q-ary LDPC codes, which have been shown to outperform binary LDPC codes and Reed-Solomon codes on the AWGN channel and it gives us a new fast and reduced-complexity decoding algorithm. The complexity of this rule varies inversely with code rate, making the technique particularly attractive for high rate codes. Finally, we see that complexity is reduced by using the dual code, and the algorithm is accelerated by using the fast Hadamard transform (FHT). Examples are given for both single parity check (non iterative case) and LDPC (iterative case) non binary codes
Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.
The main challenge for hardware implementation of non-binary LDPC decoding is the high computational complexity and large memory requirement. To address this challenge, five new low complexity LDPC decoding algorithms are proposed in this paper. The proposed algorithms are developed specifically towards the low complexity, yet effective, decoding of the NB LDPC codes. The proposed decoding algorithms update, iteratively, the hard decision received vector to search for the valid codeword in the vector space of Galois field (GF){(GF)}(GF) . The selection criterion for least reliable symbol positions is based on the information from the failed checks and the reliability information from the Galois field structure as well as from the received channel soft information. To choose the correct value for the candidate symbol, two methods are used. The first method is based on the prediction of the error symbol from the set of Galois field symbols which maximize an objective function. In the second method, individual bits are flipped based on the reliability information obtained from the channel. Algorithms 1 and 2 flip a single symbol per iteration whilst the other three algorithms 3, 4 and 5 flip multiple symbols in each iteration. The proposed voting based Algorithms 1, 2 and 5 first short list the unreliable positions using a majority voting scheme and then choose the candidate symbol value from the set of the symbols in GF(q){GF(q)}GF(q) while not violating the field order q{q}q . These methods simplify the decoding complexity in terms of computation and memory. Results and analysis of these algorithms show an appealing tradeoff between computational complexity and bit error rate performance for NB LDPC codes.
By presenting an approximated performance-complexity tradeoff (PCT) algorithm, a low-complexity non-binary low density parity check (LDPC) code over q-ary-input symmetric-output channel is designed in this manuscript which converges faster than the threshold-optimized non-binary LDPC codes in the low error rate regime. We examine our algorithm by both hard and soft decision decoders. Moreover, simulation shows that the approximated PCT algorithm has accelerated the convergence process by 30% regarding the number of the decoding iterations.
Non-binary LDPC codes are promising error cor- recting codes for short and moderate block lengths. These codes demonstrate interesting performances in high order fields, though are more complex to decode. As for binary LDPC codes, decoding scheduling can be optimized to improve performance. In this paper, a simulation-based approach is used for different scheduling policies in the non-binary case in order to point out possible performance gains for these codes. An optimization of decoding scheduling is also proposed and exhibits about 20% complexity reduction in error-floor region, thus promising interesting gains if combined with advanced dynamic scheduling strategies. I. INTRODUCTION Channel coding has seen important developments over the last two decades. Thanks to the introduction of advanced error- correcting codes, initiated by Turbo-codes in the early 90's, and to the use of iterative decoding techniques, Shannnon- limit performance has been closely approached. Low-Density Parity-Check (LDPC) codes, first introduced by Gallager (1) in the 60's, were rediscovered by Mackay and Neal (2) in 1996. Excellent error-correcting performance for long block lengths (3) position LDPC codes as an important candidate for advanced communication systems, already adopted in different standards, such as DVB-S2, IEEE 802.16 and 802.11n. How- ever, as codewords become shorter, LDPC performance gains are generally less satisfying. Non-binary LDPC codes, though more complex, proved to significantly improve performance for moderate and short blocklengths (4), (5). The use of a high order alphabet also suggests matching it with the modulation alphabet: LDPC codes over a 16�elements Galois field for example can be naturally mapped in 16�QAM modulated symbols. This would avoid the bit-to-symbol performance loss, especially when having a frequency selective channel, as non- binary encoding can reduce channel memory effect (6). This use of non-binary LDPC codes is thus very promising for high data rate communications, especially when complexity reduc- tion techniques are adopted, either for decoding update rules or scheduling policy. Previous work on scheduling strategies for the binary case can be found in (7). In this paper, we will first address a brief overview of decoding techniques for LDPC codes over high order extension fields. Then, scheduling strategies and effects will be compared for the non-binary case. A simulation-based approach will also be detailed to suggest new scheduling policies, and results from an optimized scheduling will be presented. The paper will be concluded by some remarks and suggestions towards future works.
Low Density Parity Check (LDPC) codes have excellent error correcting performance. LDPC codes are one of the block coding techniques and it performs near Shannon limit and recommended for many practical applications. Non-binary LDPC codes extension of binary LDPC in error correcting property especially for short and moderate block length. In many digital communication systems these codes have strong competitors of turbo codes for error control. Low Density Parity Check as it name is suggests that in a parity check matrix (H) consists of very small number of non-zero elements comparing with zero elements. The strength of the LDPC code defines Parity Check Matrix (PCM). LDPC code contains two types of decoding algorithms hard and soft decision algorithm. By comparing with other traditional decoding algorithm FFT based sum product algorithm reduced computation complexity with better decoding performance. In this paper, LDPC codes for FFT based sum product decoding algorithm performances are analysed for various order of Galois Field GF(q) using AWGN channel. Decoding performance measured in terms of symbol error rate which improve with increasing order of Galois field.