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 Journal of e-Education e-Business e-Management and e-Learning

Construction of Structured Nonbinary Low-Density Parity-Check Codes

Wojciech Sułek

Published Jan 1, 2013• 0 citations
Publisher

Abstract

Low Density Parity Check (LDPC) codes over nonbinary Galois Fields GF(q) are a generalization of the industrial standard binary LDPC codes for forward error correction in communication and information systems.The nonbinary codes can achieve significantly better performance for short and moderate block lengths.A lot of works concerning "good" LDPC codes parity check matrix construction has been published so far.However, it is well known that efficient partially parallel hardware decoder architectures are allowed only for codes with blockwise partitioned structure of the parity check matrix, called structured codes.In this paper we present a versatile algorithm for construction of codes that are both nonbinary and structured.The proposed algorithm aims at optimizing the code graph (Tanner graph) by reducing the existence of small cycles with low external connectivity, while at the same time selecting appropriate nonzero coefficients from the Galois Field under interest.The algorithm can be used for code construction of any field order, block length and code rate.

DOI
10.7763/ijeeee.2013.v3.267

Related papers

The design of structured LDPC codes with algorithmic graph construction

Wojciech Sułek

Low-Density Parity-Check (LDPC) codes are among the most effective modern error-correcting codes due to their excellent correction performance and highly parallel decoding scheme. Moreover, the nonbinary extension of such codes further increases performance in the short-block regime. In this paper, we review the key elements for the construction of implementation-oriented binary and nonbinary codes. These Quasi-Cyclic LDPC (QC-LDPC) codes additionally feature efficient encoder and decoder implementation frameworks. We then present a versatile algorithm for the construction of both binary and nonbinary QC-LDPC codes that have low encoding complexity and an optimized corresponding graph structure. Our algorithm uses a progressive edge growth algorithm, modified for QC-LDPC graph construction, and then performs an iterative global search for optimized cyclic shift values within the QC-LDPC circulants. Strong error correction performance is achieved by minimizing the number of short cycles, and cycles with low external connectivity, within the code graph. We validate this approach via error rate simulations of a transmission system model featuring an LDPC coder-decoder, digital modulation, and additive white Gaussian noise channels. The obtained numerical results validate the effectiveness of the proposed construction algorithm, with a number of constructed codes exhibiting either similar or superior performance to industry standard binary codes and selected nonbinary codes from the literature.

Bulletin of the Polish Academy of Sciences Technical Sciences•May 30, 2022•0 citations

Column weights optimization for semi-regular nonbinary LDPC codes

Wojciech Sułek, Marcin Kucharczyk

The paper concerns Low Density Parity Check (LDPC) codes over nonbinary Galois Fields GF(q), that are a generalization of the industrial standard binary LDPC codes for forward error correction in communication and information systems. The semi-regular nonbinary LDPC codes can outperform their binary counterparts in the case of short to moderate code word lengths. The methods for the good code construction based on a computer search techniques are already well investigated. However, there is a lack of systematic results for optimal weight distribution of columns of parity check matrices for codes over different field order and different rate. In this article we present a Monte Carlo like algorithm for column weight optimization devoted to nonbinary semi-regular codes along with optimization results that facilitate the codes construction computer-based methods.

International Conference on Telecommunications and Signal Processing (TSP)•Jul 1, 2015•1 citation

Construction of short-block nonbinary LDPC codes based on cyclic codes

Hengzhou Xu, Baoming Bai, Min Zhu +2 more

In this paper, we focus on short-block nonbinary LDPC (NB-LDPC) codes based on cyclic codes. Based on Tanner graphs' isomorphism, we present an efficient search algorithm for finding non-isomorphic binary cyclic LDPC codes. Notice that the parity-check matrix H of the resulting code is square and not of full rank, and its row weight and column weight are the same. By replacing the ones in the same column of H with a nonzero element of finite fields GF(q), a class of NB-LDPC codes over GF(q) is obtained. Numerical results show that the constructed codes perform well over the AWGN channel and have fast decoding convergence. Therefore, the proposed NB-LDPC codes provide a promising coding scheme for low-latency and high-reliability communications.

China Communications•Aug 1, 2017•5 citations

High-Rate Nonbinary Regular Quasi-Cyclic LDPC Codes for Optical Communications

Murat Arabaci, Ivan B. Djordjević, Ross Saunders +1 more

The parity-check matrix of a nonbinary (NB) low-density parity-check (LDPC) code over Galois field GF(q) is constructed by assigning nonzero elements from GF(q) to the 1s in corresponding binary LDPC code. In this paper, we state and prove a theorem that establishes a necessary and sufficient condition that an NB matrix over GF(q), constructed by assigning nonzero elements from GF(q) to the 1s in the parity-check matrix of a binary quasi-cyclic (QC) LDPC code, must satisfy in order for its null-space to define a nonbinary QC-LDPC (NB-QC-LDPC) code. We also provide a general scheme for constructing NB-QC-LDPC codes along with some other code construction schemes targeting different goals, e.g., a scheme that can be used to construct codes for which the fast-Fourier-transform-based decoding algorithm does not contain any intermediary permutation blocks between bit node processing and check node processing steps. Via Monte Carlo simulations, we demonstrate that NB-QC-LDPC codes can achieve a net effective coding gain of 10.8 dB at an output bit error rate of 10-12. Due to their structural properties that can be exploited during encoding/decoding and impressive error rate performance, NB-QC-LDPC codes are strong candidates for application in optical communications.

Journal of Lightwave Technology•Aug 7, 2009•42 citations

Computing the Minimum Distance of Nonbinary LDPC Codes

Lei Liu, Jie Huang, Wuyang Zhou +1 more

Finding the minimum distance of low-density-parity-check (LDPC) codes is an NP-hard problem. Different from all existing works that focus on binary LDPC codes, we in this paper aim to compute the minimum distance of nonbinary LDPC codes, motivated by the fact that operating in a large Galois field provides one important degree of freedom to achieve both good waterfall and error-floor performance. Our method is based on the existing nearest nonzero codeword search (NNCS) method, but several modifications are incorporated for nonbinary LDPC codes, including the modified error impulse pattern, the dithering method, and the nonbinary decoder. Numerical results on the estimated minimum distances show that a code's minimum distance can be increased by careful selection of nonzero elements of the parity check matrix, or by increasing the mean column weight, or by increasing the size of the Galois field. These results support observations that have been made based on simulated performance in the literature. Finally, we provide an upper bound on the minimum distance for nonbinary quasi-cyclic LDPC codes.

IEEE Transactions on Communications•Jul 1, 2012•8 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
Low Density Parity Check (LDPC) codes over nonbinary Galois Fields GF(q) are a generalization of the industrial standard binary LDPC codes for forward error correction in communication and information systems.The nonbinary codes can achieve significantly better performance for short and moderate block lengths.A lot of works concerning "good" LDPC codes parity check matrix construction has been published so far.However, it is well known that efficient partially parallel hardware decoder architectures are allowed only for codes with blockwise partitioned structure of the parity check matrix, called structured codes.In this paper we present a versatile algorithm for construction of codes that are both nonbinary and structured.The proposed algorithm aims at optimizing the code graph (Tanner graph) by reducing the existence of small cycles with low external connectivity, while at the same time selecting appropriate nonzero coefficients from the Galois Field under interest.The algorithm can be used for code construction of any field order, block length and code rate.
Low-Density Parity-Check (LDPC) codes are among the most effective modern error-correcting codes due to their excellent correction performance and highly parallel decoding scheme. Moreover, the nonbinary extension of such codes further increases performance in the short-block regime. In this paper, we review the key elements for the construction of implementation-oriented binary and nonbinary codes. These Quasi-Cyclic LDPC (QC-LDPC) codes additionally feature efficient encoder and decoder implementation frameworks. We then present a versatile algorithm for the construction of both binary and nonbinary QC-LDPC codes that have low encoding complexity and an optimized corresponding graph structure. Our algorithm uses a progressive edge growth algorithm, modified for QC-LDPC graph construction, and then performs an iterative global search for optimized cyclic shift values within the QC-LDPC circulants. Strong error correction performance is achieved by minimizing the number of short cycles, and cycles with low external connectivity, within the code graph. We validate this approach via error rate simulations of a transmission system model featuring an LDPC coder-decoder, digital modulation, and additive white Gaussian noise channels. The obtained numerical results validate the effectiveness of the proposed construction algorithm, with a number of constructed codes exhibiting either similar or superior performance to industry standard binary codes and selected nonbinary codes from the literature.
The paper concerns Low Density Parity Check (LDPC) codes over nonbinary Galois Fields GF(q), that are a generalization of the industrial standard binary LDPC codes for forward error correction in communication and information systems. The semi-regular nonbinary LDPC codes can outperform their binary counterparts in the case of short to moderate code word lengths. The methods for the good code construction based on a computer search techniques are already well investigated. However, there is a lack of systematic results for optimal weight distribution of columns of parity check matrices for codes over different field order and different rate. In this article we present a Monte Carlo like algorithm for column weight optimization devoted to nonbinary semi-regular codes along with optimization results that facilitate the codes construction computer-based methods.
In this paper, we focus on short-block nonbinary LDPC (NB-LDPC) codes based on cyclic codes. Based on Tanner graphs' isomorphism, we present an efficient search algorithm for finding non-isomorphic binary cyclic LDPC codes. Notice that the parity-check matrix H of the resulting code is square and not of full rank, and its row weight and column weight are the same. By replacing the ones in the same column of H with a nonzero element of finite fields GF(q), a class of NB-LDPC codes over GF(q) is obtained. Numerical results show that the constructed codes perform well over the AWGN channel and have fast decoding convergence. Therefore, the proposed NB-LDPC codes provide a promising coding scheme for low-latency and high-reliability communications.
The parity-check matrix of a nonbinary (NB) low-density parity-check (LDPC) code over Galois field GF(q) is constructed by assigning nonzero elements from GF(q) to the 1s in corresponding binary LDPC code. In this paper, we state and prove a theorem that establishes a necessary and sufficient condition that an NB matrix over GF(q), constructed by assigning nonzero elements from GF(q) to the 1s in the parity-check matrix of a binary quasi-cyclic (QC) LDPC code, must satisfy in order for its null-space to define a nonbinary QC-LDPC (NB-QC-LDPC) code. We also provide a general scheme for constructing NB-QC-LDPC codes along with some other code construction schemes targeting different goals, e.g., a scheme that can be used to construct codes for which the fast-Fourier-transform-based decoding algorithm does not contain any intermediary permutation blocks between bit node processing and check node processing steps. Via Monte Carlo simulations, we demonstrate that NB-QC-LDPC codes can achieve a net effective coding gain of 10.8 dB at an output bit error rate of 10-12. Due to their structural properties that can be exploited during encoding/decoding and impressive error rate performance, NB-QC-LDPC codes are strong candidates for application in optical communications.
Finding the minimum distance of low-density-parity-check (LDPC) codes is an NP-hard problem. Different from all existing works that focus on binary LDPC codes, we in this paper aim to compute the minimum distance of nonbinary LDPC codes, motivated by the fact that operating in a large Galois field provides one important degree of freedom to achieve both good waterfall and error-floor performance. Our method is based on the existing nearest nonzero codeword search (NNCS) method, but several modifications are incorporated for nonbinary LDPC codes, including the modified error impulse pattern, the dithering method, and the nonbinary decoder. Numerical results on the estimated minimum distances show that a code's minimum distance can be increased by careful selection of nonzero elements of the parity check matrix, or by increasing the mean column weight, or by increasing the size of the Galois field. These results support observations that have been made based on simulated performance in the literature. Finally, we provide an upper bound on the minimum distance for nonbinary quasi-cyclic LDPC 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.