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

arXiv:2005.07352 · IEEE Transactions on Communications

Decoding of NB-LDPC codes over Subfields

V. B. Wijekoon, Emanuele Viterbo, Yi Hong

Published Jan 1, 2020• 6 citations
arXivHTMLPDF

Abstract

In this paper, we present a novel method to expand a graph over a finite field into a larger one over one of the original field's subfields. This allows a number of different graph expansions for any given graph. These expansions can be used in various applications, and we focus specifically on the case of decoding NB-LDPC codes. Using the novel expanded graphs, it is possible to reduce decoding complexity of NB- LDPC codes significantly with minimal performance losses.

DOI
10.1109/tcomm.2020.3036073

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

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

V. B. Wijekoon, Emanuele Viterbo, Yi Hong +2 more

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.

IEEE Transactions on Communications•Dec 23, 2019•14 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 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

Efficient decoding implementations of LDPC codes

Wenbo Wang

As for the sum-product decoding algorithm of LDPC codes,a new kind of difference-based decoding method is proposed.The main idea about it is that the messages passed on the bipartite graph of LDPC are based on the probability differences,and the renewal of both check nodes and message nodes is carried out on the special addition domain.As for the renewal of check nodes,some differences possessing the minimum absolute values can be selected to further reduce the complexity of computation.In contrast with the traditional LLR-based decoding method,the proposed method has much lower complexity,while it has no obvious loss of performance and convergence.

Systems engineering and electronics•Jan 1, 2010•0 citations

Split non-binary LDPC codes

Adrian Voicila, David Declercq, François S. Verdier +2 more

In this paper, we propose and study a new family of error-correcting codes. These achieve excellent error performance under an iterative decoding over the binary-input noisy channel and solves the memory space requirements problem of the non-binary LDPC decoders. We named this class of codes, Split non-binary LDPC codes. The main particularity of this new family of codes is that the variable and the check nodes are not defined over the same finite field GF(2p), like in the case of classical non-binary LDPC codes. The class of Split non-binary LDPC codes is obviously larger than that of existing types of codes, which gives more degrees of freedom to find good codes when the existing codes show their limits. We provide two examples of interesting split NB-LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•7 citations
In this paper, we present a novel method to expand a graph over a finite field into a larger one over one of the original field's subfields. This allows a number of different graph expansions for any given graph. These expansions can be used in various applications, and we focus specifically on the case of decoding NB-LDPC codes. Using the novel expanded graphs, it is possible to reduce decoding complexity of NB- LDPC codes significantly with minimal performance losses.
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.
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.
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 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.
As for the sum-product decoding algorithm of LDPC codes,a new kind of difference-based decoding method is proposed.The main idea about it is that the messages passed on the bipartite graph of LDPC are based on the probability differences,and the renewal of both check nodes and message nodes is carried out on the special addition domain.As for the renewal of check nodes,some differences possessing the minimum absolute values can be selected to further reduce the complexity of computation.In contrast with the traditional LLR-based decoding method,the proposed method has much lower complexity,while it has no obvious loss of performance and convergence.
In this paper, we propose and study a new family of error-correcting codes. These achieve excellent error performance under an iterative decoding over the binary-input noisy channel and solves the memory space requirements problem of the non-binary LDPC decoders. We named this class of codes, Split non-binary LDPC codes. The main particularity of this new family of codes is that the variable and the check nodes are not defined over the same finite field GF(2p), like in the case of classical non-binary LDPC codes. The class of Split non-binary LDPC codes is obviously larger than that of existing types of codes, which gives more degrees of freedom to find good codes when the existing codes show their limits. We provide two examples of interesting split NB-LDPC codes.