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

International Symposium on Wireless Communication Systems

Non-binary split LDPC codes defined over finite groups

Bilal Shams, David Declercq, Vincent Heinrich

Published Sep 1, 2009• 3 citations
Publisher

Abstract

In this paper, we propose a practically implementable decoding algorithm for split LDPC codes with parity constraints defined over finite groups. The proposed decoding algorithm generalizes the orders of the variable and check nodes such that it may have messages of different order at the various nodes. This gives us a further degree of freedom in terms of better code construction. Using the binary image of the parity check matrix, we define the function node which maps lower order messages to higher order and vice-versa. In order to have a reduced complexity decoder which is practically implementable, we use the truncated messages concept at the check nodes and evaluate its performance. We show improved performance in the error floor region as compared to other non-split low complexity decoding algorithms.

DOI
10.1109/iswcs.2009.5285264

Related papers

Decoding Algorithm for Non-Binary LDPC Codes Based on Node-Subset and k-Order Message Truncation

Youming Sun, Haiqiang Chen, Xiangcheng Li +2 more

This paper presents a low complexity non-binary LDPC decoding algorithm,whose complexity can be reduced in the following two ways.First,a new truncation scheme is presented to define the processing/non-processing check node subsets.The check nodes with relatively high reliability are not required to be processed,which can reduce the complexity.Second,for the check nodes in the processing subset,we further present a k-order message truncation for the states and branches of the check node Trellis.In the decoding iterations,only those live states/branches are involved in the message updating process,which can further reduce the computational loads at check nodes.Simulation results show that the presented algorithm performs very closely to several existing improved EMS decoding algorithms,but it has the lowest complexity when decoding the non-binary LDPC codes constructed both in low/high order fields.%

Dianzi xuebao•Jan 1, 2017•1 citation

Improved decoding Architecture for non-binary split LDPC codes defined over finite groups

Bilal Shams, David Declercq, Vincent Heinrich

In this paper, we propose an improvement of the previously proposed decoder for split LDPC codes defined over finite groups. The output of the check nodes is adjusted such that it bears better resemblance to that of more complex and efficient algorithms. There is a significant improvement in the decoding performance with almost no oeffect on the decoding complexity. The hardware architecture for the proposed decoder is explained in detail and we show with Monte-Carlo simulations that the performance is indeed improved.

International Conference on Future Computer and Communication•Jan 1, 2010•0 citations

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

Adaptive Extended Min-Sum Algorithm for Nonbinary LDPC Decoding

Xuan Guan, Yunsi Fei

Low Density Parity Check (LDPC) codes over a Galois Field GF(q) can provide significantly better error- correcting quality than binary LDPC codes with moderate code length. However, the computational complexity and memory requirement of nonbinary codes are much higher, limiting the application of non- binary LDPC codes. In this paper, we propose an adaptive message truncation algorithm for non-binary LDPC decoding, guided by the estimated code error rates. Compared to the previous fixed message truncation method, it can cut the messages adaptively, and therefore provide better decoding quality and computation complexity reduction. To further reduce the computation, we propose another adaptive check node update algorithm, simplifying the decoding by reducing the number of check nodes updating. Our simulation results demonstrate that by combining these two algorithms together, the average message size can be reduced greatly and good decoding quality is achieved, at a little cost of iterations. Compared to the existing truncation algorithms, our approach can reduce the order of complexity to O(nalog2(na)) (where nais messages size), with less performance degradation.

Globecom•Dec 1, 2011•7 citations

Efficient Design of Structured LDPC Codes

Biwoong Chung, Joon-Sung Kim, Song Hong-Yeop

The high encoding complexity of LDPC codes can be solved by designing structured parity-check matrix. If the parity-check matrix of LDPC codes is composed of same type of blocks, decoder implementation can be simple, this structure allow structured decoding and required memory for storing the parity-check matrix can be reduced largely. In this paper, we propose a construction algorithm for short block length structured LDPC codes based on girth condition, PEG algorithm and variable node connectivity. The code designed by this algorithm shows similar performance to other codes without structured constraint in low SNR and better performance in high SNR than those by simulation

한국통신학회논문지•Jan 1, 2006•1 citation

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•725 citations
In this paper, we propose a practically implementable decoding algorithm for split LDPC codes with parity constraints defined over finite groups. The proposed decoding algorithm generalizes the orders of the variable and check nodes such that it may have messages of different order at the various nodes. This gives us a further degree of freedom in terms of better code construction. Using the binary image of the parity check matrix, we define the function node which maps lower order messages to higher order and vice-versa. In order to have a reduced complexity decoder which is practically implementable, we use the truncated messages concept at the check nodes and evaluate its performance. We show improved performance in the error floor region as compared to other non-split low complexity decoding algorithms.
This paper presents a low complexity non-binary LDPC decoding algorithm,whose complexity can be reduced in the following two ways.First,a new truncation scheme is presented to define the processing/non-processing check node subsets.The check nodes with relatively high reliability are not required to be processed,which can reduce the complexity.Second,for the check nodes in the processing subset,we further present a k-order message truncation for the states and branches of the check node Trellis.In the decoding iterations,only those live states/branches are involved in the message updating process,which can further reduce the computational loads at check nodes.Simulation results show that the presented algorithm performs very closely to several existing improved EMS decoding algorithms,but it has the lowest complexity when decoding the non-binary LDPC codes constructed both in low/high order fields.%
In this paper, we propose an improvement of the previously proposed decoder for split LDPC codes defined over finite groups. The output of the check nodes is adjusted such that it bears better resemblance to that of more complex and efficient algorithms. There is a significant improvement in the decoding performance with almost no oeffect on the decoding complexity. The hardware architecture for the proposed decoder is explained in detail and we show with Monte-Carlo simulations that the performance is indeed improved.
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.
Low Density Parity Check (LDPC) codes over a Galois Field GF(q) can provide significantly better error- correcting quality than binary LDPC codes with moderate code length. However, the computational complexity and memory requirement of nonbinary codes are much higher, limiting the application of non- binary LDPC codes. In this paper, we propose an adaptive message truncation algorithm for non-binary LDPC decoding, guided by the estimated code error rates. Compared to the previous fixed message truncation method, it can cut the messages adaptively, and therefore provide better decoding quality and computation complexity reduction. To further reduce the computation, we propose another adaptive check node update algorithm, simplifying the decoding by reducing the number of check nodes updating. Our simulation results demonstrate that by combining these two algorithms together, the average message size can be reduced greatly and good decoding quality is achieved, at a little cost of iterations. Compared to the existing truncation algorithms, our approach can reduce the order of complexity to O(nalog2(na)) (where nais messages size), with less performance degradation.
The high encoding complexity of LDPC codes can be solved by designing structured parity-check matrix. If the parity-check matrix of LDPC codes is composed of same type of blocks, decoder implementation can be simple, this structure allow structured decoding and required memory for storing the parity-check matrix can be reduced largely. In this paper, we propose a construction algorithm for short block length structured LDPC codes based on girth condition, PEG algorithm and variable node connectivity. The code designed by this algorithm shows similar performance to other codes without structured constraint in low SNR and better performance in high SNR than those by simulation
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