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 Transactions on Communications

A Novel Graph Expansion and a Decoding Algorithm for NB-LDPC Codes

V. B. Wijekoon, Emanuele Viterbo, Yi Hong, Rino Micheloni, Alessia Marelli

Published Dec 23, 2019• 14 citations
Publisher

Abstract

Non-binary low-density parity-check (NB-LDPC) codes are known to offer several advantages over their binary counterparts, but the higher complexity, and the resource-hungry nature of decoding algorithms have so far restricted their practical usage. In this paper, we propose a new decoding algorithm for NB-LDPC codes over finite fields of characteristic 2, based on a novel binary expansion of the Q-ary Tanner graph. While it offers substantial complexity gains, simulation results demonstrate that the performance loss of the new algorithm, in comparison to the best known decoder, is quite small. Furthermore, due to being based on a binary graph, it is particularly attractive for hardware implementations. We also suggest a simplified version of the algorithm, which offers even higher gains in complexity.

DOI
10.1109/tcomm.2019.2961884

Related papers

A Low Complexity Decoding Algorithm for NB-LDPC Codes over Quadratic Extension Fields

V. B. Wijekoon, Emanuele Viterbo, Yi Hong

NB-LDPC codes, a class of codes well-known for their exceptional error correcting performance, are not yet used widely in practice due to the high complexity of decoding algorithms. In this paper, we propose a low complexity decoder for these codes by means of a novel graph expansion. We view the finite field over which the code is constructed as the quadratic extension of one of its subfields, and then expand the Tanner graph of the code into a graph over that particular field. Decoding algorithm, which is tailored for this larger graph, presents significant complexity gains while the performance loss is minimal.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•3 citations

Coset Probability Based Majority-logic Decoding for Non-binary LDPC Codes

V. B. Wijekoon, Shuiyin Liu, Emanuele Viterbo +3 more

This paper presents a majority-logic decoding (MLgD) algorithm for non-binary LDPC codes based on a novel expansion of the Tanner graph. The expansion introduced converts the Q-ary graph into a binary one, which makes the new MLgD algorithm more attractive for hardware implementations. Proposed algorithm performs significantly better than the existing MLgD algorithms in the waterfall region, and it shows a much lower error-floor as well. Algorithm only requires integer additions, comparisons, finite field operations and some binary operations. Thus, it offers an effective trade-off between performance and complexity in decoding non-binary LDPC codes.

IEEE Information Theory Workshop (ITW)•Aug 1, 2019•0 citations

Efficient Check Node Processing for Min-Max NB-LDPC Decoding over Lower-Order Finite Fields

Xinmiao Zhang

Low-density parity-check (LDPC) codes defined over non-binary (NB) finite field GF(2q)(q >1) achieve better error-correcting performance than binary LDPC codes when the codeword length is moderate. The decoder complexity increases very fast with the order of the field, 2q, although the error-correcting performance also improves. To reduce the complexity for practical applications, NB-LDPC codes over lower-order finite fields are of great interest. Previous designs have been focusing on decoders over either the smallest NB field GF (4) or much larger fields, such as GF (32) or higher. Prior optimization techniques are either not applicable or do not lead to efficient designs for codes over GF (8) or other lower-order fields. In this paper, an efficient architecture is developed for the check node processing, which is the most complicated step in NB-LDPC decoding, for the Min-max algorithm over lower-order fields. By utilizing the properties of finite field elements, the max/min comparison results are shared and the number of comparators needed is reduced significantly. Compared to the best prior design, the proposed check node processing has 18.5% smaller area and shorter critical path for an example code over GF (8).

IEEE International Symposium on Circuits and Systems proceedings•May 28, 2022•0 citations

A new min-sum based decoding algorithm for non-binary LDPC codes

Chung-Li Wang, Zongwang Li, Shaohua Yang

Non-binary low-density parity-check (NB-LDPC) codes are robust to various channel impairments. In this paper, we present a new decoding algorithm for the NB-LDPC decoder that is based on the q-ary min-sum algorithm (QMSA). The new one modifies the check node (CN) computations of the QMSA into two steps. By reorganizing the message entries and providing the most likely symbol, a compressed intermediate message can be easily obtained and stored, from which the check-to-variable messages can be computed with a look-up table. Thus the decoder architecture can have a straightforward design for the CN with reduced complexity and memory requirements. Besides, the simulation results demonstrate that the proposed algorithm has negligible performance loss compared to the QMSA over AWGN channel.

2012 International Conference on Computing, Networking and Communications (ICNC)•Jan 1, 2012•5 citations

A New NB-LDPC Code Construction Method With Arbitrary Generalized Girth

Jaeil Lim, Jaewon Chung, Donghun Jeong +2 more

!Non-binary low density parity check (NB-LDPC) codes are known to have higher correction capability than their binary counterparts, low density parity check (LDPC) codes. The latest technique for analyzing NB-LDPC codes is to measure generalized girth. The generalized girth cannot be measured in a binary LDPC code, and can be considered an indicator for measuring the performance of NB-LDPC code. In this paper, we propose a new analysis method to represent NB-LDPC code as a graph. This graph is called a permutation graph. In this paper, we present and prove a reasoning for analyzing generalized girth using the permutation graph. This is a faster and simpler method than the existing generalized girth analysis method. The proposed code construction algorithm constructs NB-LDPC codes to have an arbitrary generalized girth length. Because the permutation graph-based analysis is applied, which is more effective than existing methods, the complexity of code construction is significantly reduced. This enables more efficient code construction. The decoding simulations show that the proposed method improves the correction performance of NB-LDPC codes compared to the existing state-of-the-art.

IEEE Transactions on Communications•Jan 1, 2026•0 citations

Parallel Symbol-Flipping Decoding for Non-Binary LDPC Codes

Chao-Cheng Huang, Chi‐Jen Wu, Chao‐Yu Chen +1 more

A new low-complexity parallel symbol-flipping decoding algorithm for non-binary low-density parity-check (NB-LDPC) codes is proposed. The algorithm outperforms quite a number of existing reliability-based message-passing algorithms, and its computation complexity is smaller than that of almost all the previously proposed iterative decoding algorithms for NB-LDPC codes. It is suitable for decoding NB-LDPC codes whose parity-check matrices have large column weights.

IEEE Communications Letters•Jun 1, 2013•23 citations
Non-binary low-density parity-check (NB-LDPC) codes are known to offer several advantages over their binary counterparts, but the higher complexity, and the resource-hungry nature of decoding algorithms have so far restricted their practical usage. In this paper, we propose a new decoding algorithm for NB-LDPC codes over finite fields of characteristic 2, based on a novel binary expansion of the Q-ary Tanner graph. While it offers substantial complexity gains, simulation results demonstrate that the performance loss of the new algorithm, in comparison to the best known decoder, is quite small. Furthermore, due to being based on a binary graph, it is particularly attractive for hardware implementations. We also suggest a simplified version of the algorithm, which offers even higher gains in complexity.
NB-LDPC codes, a class of codes well-known for their exceptional error correcting performance, are not yet used widely in practice due to the high complexity of decoding algorithms. In this paper, we propose a low complexity decoder for these codes by means of a novel graph expansion. We view the finite field over which the code is constructed as the quadratic extension of one of its subfields, and then expand the Tanner graph of the code into a graph over that particular field. Decoding algorithm, which is tailored for this larger graph, presents significant complexity gains while the performance loss is minimal.
This paper presents a majority-logic decoding (MLgD) algorithm for non-binary LDPC codes based on a novel expansion of the Tanner graph. The expansion introduced converts the Q-ary graph into a binary one, which makes the new MLgD algorithm more attractive for hardware implementations. Proposed algorithm performs significantly better than the existing MLgD algorithms in the waterfall region, and it shows a much lower error-floor as well. Algorithm only requires integer additions, comparisons, finite field operations and some binary operations. Thus, it offers an effective trade-off between performance and complexity in decoding non-binary LDPC codes.
Low-density parity-check (LDPC) codes defined over non-binary (NB) finite field GF(2q)(q >1) achieve better error-correcting performance than binary LDPC codes when the codeword length is moderate. The decoder complexity increases very fast with the order of the field, 2q, although the error-correcting performance also improves. To reduce the complexity for practical applications, NB-LDPC codes over lower-order finite fields are of great interest. Previous designs have been focusing on decoders over either the smallest NB field GF (4) or much larger fields, such as GF (32) or higher. Prior optimization techniques are either not applicable or do not lead to efficient designs for codes over GF (8) or other lower-order fields. In this paper, an efficient architecture is developed for the check node processing, which is the most complicated step in NB-LDPC decoding, for the Min-max algorithm over lower-order fields. By utilizing the properties of finite field elements, the max/min comparison results are shared and the number of comparators needed is reduced significantly. Compared to the best prior design, the proposed check node processing has 18.5% smaller area and shorter critical path for an example code over GF (8).
Non-binary low-density parity-check (NB-LDPC) codes are robust to various channel impairments. In this paper, we present a new decoding algorithm for the NB-LDPC decoder that is based on the q-ary min-sum algorithm (QMSA). The new one modifies the check node (CN) computations of the QMSA into two steps. By reorganizing the message entries and providing the most likely symbol, a compressed intermediate message can be easily obtained and stored, from which the check-to-variable messages can be computed with a look-up table. Thus the decoder architecture can have a straightforward design for the CN with reduced complexity and memory requirements. Besides, the simulation results demonstrate that the proposed algorithm has negligible performance loss compared to the QMSA over AWGN channel.
!Non-binary low density parity check (NB-LDPC) codes are known to have higher correction capability than their binary counterparts, low density parity check (LDPC) codes. The latest technique for analyzing NB-LDPC codes is to measure generalized girth. The generalized girth cannot be measured in a binary LDPC code, and can be considered an indicator for measuring the performance of NB-LDPC code. In this paper, we propose a new analysis method to represent NB-LDPC code as a graph. This graph is called a permutation graph. In this paper, we present and prove a reasoning for analyzing generalized girth using the permutation graph. This is a faster and simpler method than the existing generalized girth analysis method. The proposed code construction algorithm constructs NB-LDPC codes to have an arbitrary generalized girth length. Because the permutation graph-based analysis is applied, which is more effective than existing methods, the complexity of code construction is significantly reduced. This enables more efficient code construction. The decoding simulations show that the proposed method improves the correction performance of NB-LDPC codes compared to the existing state-of-the-art.