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 Information Theory

Searching for Binary and Nonbinary Block and Convolutional LDPC Codes

Irina E. Bocharova, Boris D. Kudryashov, Rolf Johannesson

Published Oct 29, 2015• 62 citations
Publisher

Abstract

A unified approach to search for and optimize codes determined by their sparse parity-check matrices is presented. Replacing the nonzero elements of a binary parity-check matrix (the base or parent matrix) either by circulants or by companion matrices of elements from a finite field GF(2m), we obtain quasi-cyclic low-density parity-check (LDPC) block codes and binary images of nonbinary LDPC block codes, respectively. By substituting monomials of a formal variable D, we obtain the polynomial description of an LDPC convolutional code. A set of performance measures applicable to different classes of LDPC codes is considered, and a greedy algorithm for code performance optimization is presented. The heart of the new optimization algorithm is a fast procedure for searching for LDPC codes with large girth of their Tanner graphs. For a few classes of LDPC codes, examples of codes combining good error-correcting performance with compact representation are obtained. In particular, we present optimized convolutional LDPC codes and conclude that the LDPC block codes are still superior to their convolutional counterparts if both decoding complexity and coding delay are considered. Moreover, a specific channel model can easily be embedded into the optimization loop. Thereby, the code can be optimized for a specific channel. The efficiency of such an optimization is demonstrated via an example of faster than Nyquist (FTN) signaling using LDPC codes. The FTN strategy combined with a rate R = 1/2 LDPC code of length 64800 optimized for effective data rate R = 3/4 gains more than 0.5 dB compared with the standard LDPC codes of the same rate and length. The obtained gain corresponds to transmission at the capacity of the binary input additive white Gaussian noise channel. In most numerical examples, we consider codes with bidiagonal structure of the parity-check matrix. This restriction preserves low encoding complexity and allows fair comparison with codes selected for communication standards.

DOI
10.1109/tit.2015.2496213

Related papers

A unified approach to optimization of LDPC codes for various communication scenarios

Irina E. Bocharova, Rolf Johannesson, Boris D. Kudryashov

A unified approach to construct and optimize codes determined by their sparse parity-check matrices is presented. Parity-check matrices of quasi-cyclic (QC) LDPC block codes are obtained by replacing the nonzero elements of a base (seed) matrix by circulants. Replacing the nonzero elements either by companion matrices of elements from a finite field GF(2m) or by a formal variable D gives parity-check matrices of binary images of nonbinary LDPC block codes and LDPC convolutional codes, respectively. A set of performance measures applicable to different classes of LDPC codes are considered and a greedy algorithm for code performance optimization is presented. For a few classes of LDPC codes examples of codes combining good error-correcting performance with compact representation are obtained. Moreover, a specific channel model can easily be embedded into the optimization loop. Thereby, the code can be optimized for a specific channel. The efficiency of such an optimization is demonstrated via an example of Faster Than Nyquist (FTN) signaling using LDPC codes.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 1, 2014•1 citation

Design and Analysis of LDPC Convolutional Codes

Arvind Sridharan

Low-density parity-check (LDPC) block codes invented by Gallager in 1962 achieve exceptional error performance on a wide variety of communication channels. LDPC convolutional codes are the convolutional counterparts of LDPC block codes. This dissertation describes techniques for the design of LDPC convolutional codes, and analyzes their distance properties and iterative decoding convergence thresholds. The construction of time invariant LDPC convolutional codes by unwrapping the Tanner graph of algebraically constructed quasi-cyclic LDPC codes is described. The convolutional codes outperform the quasi-cyclic codes from which they are derived. The design of parity-check matrices for time invariant LDPC convolutional codes by the polynomial extension of a base matrix is proposed. An upper bound on free distance, proving that time invariant LDPC codes are not asymptotically good, is obtained. The Tanner graph is used to describe a pipelined message passing based iterative decoder for LDPC convolutional codes that outputs decoding results continuously. The performance of LDPC block and convolutional codes are compared for fixed decoding parameters like computational complexity, processor complexity, and decoding delay. In each case, the LDPC convolutional code performance is at least as good as that of LDPC block codes. An analog circuit to implement pipelined decoding of LDPC convolutional codes is proposed. The distance properties of a permutation matrix based (time varying) ensemble of (J,K) regular LDPC convolutional codes is investigated. It is proved that these codes (for J > 2) have free distance increasing linearly with constraint length, i.e., they are asymptotically good. Further, the asymptotic free distance to constraint length ratio for the convolutional codes is several times larger than the minimum distance to block length ratio for corresponding LDPC block codes. Iterative decoding of terminated LDPC convolutional codes, based on the ensemble mentioned above, is analyzed, assuming transmission over a binary erasure channel. The structured irregularity of the codes leads to significantly better convergence thresholds compared to corresponding LDPC block codes. At the calculated thresholds, both the bit and block error probability can be made arbitrarily small. The results obtained suggest that the thresholds approach capacity with increasing J.

•Sep 15, 2022•30 citations

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

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

Combinatorial optimization for improving QC LDPC codes performance

Irina E. Bocharova, Boris D. Kudryashov, Rolf Johannesson

Techniques for searching for good quasi-cyclic (QC) LDPC block codes of short and moderate lengths which are suitable for practical purposes are studied. To facilitate implementations only codes whose parity-check matrices having bidiagonal structure of their submatrices and consequently having low encoding complexity are considered. The problem of finding QC LDPC codes with the near-optimum frame or bit error rate performance is split into two independent steps: searching for the near-optimum column degree distribution of the parity-check matrix together with the best base matrix for this degree distribution and searching for the near-optimum labeling of the chosen base matrix. Sets of parameters and criteria for both steps are introduced and discussed. They allow further reduction of the search complexity without significant loss of the search optimality. New QC LDPC block codes of various code rates are obtained and their BER and FER performances are compared with those of the LDPC block codes as well as the turbo codes defined in the IEEE 802.16 WiMAX standard.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•7 citations

Construction of Structured Nonbinary Low-Density Parity-Check Codes

Wojciech Sułek

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.

International Journal of e-Education e-Business e-Management and e-Learning•Jan 1, 2013•0 citations
A unified approach to search for and optimize codes determined by their sparse parity-check matrices is presented. Replacing the nonzero elements of a binary parity-check matrix (the base or parent matrix) either by circulants or by companion matrices of elements from a finite field GF(2m), we obtain quasi-cyclic low-density parity-check (LDPC) block codes and binary images of nonbinary LDPC block codes, respectively. By substituting monomials of a formal variable D, we obtain the polynomial description of an LDPC convolutional code. A set of performance measures applicable to different classes of LDPC codes is considered, and a greedy algorithm for code performance optimization is presented. The heart of the new optimization algorithm is a fast procedure for searching for LDPC codes with large girth of their Tanner graphs. For a few classes of LDPC codes, examples of codes combining good error-correcting performance with compact representation are obtained. In particular, we present optimized convolutional LDPC codes and conclude that the LDPC block codes are still superior to their convolutional counterparts if both decoding complexity and coding delay are considered. Moreover, a specific channel model can easily be embedded into the optimization loop. Thereby, the code can be optimized for a specific channel. The efficiency of such an optimization is demonstrated via an example of faster than Nyquist (FTN) signaling using LDPC codes. The FTN strategy combined with a rate R = 1/2 LDPC code of length 64800 optimized for effective data rate R = 3/4 gains more than 0.5 dB compared with the standard LDPC codes of the same rate and length. The obtained gain corresponds to transmission at the capacity of the binary input additive white Gaussian noise channel. In most numerical examples, we consider codes with bidiagonal structure of the parity-check matrix. This restriction preserves low encoding complexity and allows fair comparison with codes selected for communication standards.
A unified approach to construct and optimize codes determined by their sparse parity-check matrices is presented. Parity-check matrices of quasi-cyclic (QC) LDPC block codes are obtained by replacing the nonzero elements of a base (seed) matrix by circulants. Replacing the nonzero elements either by companion matrices of elements from a finite field GF(2m) or by a formal variable D gives parity-check matrices of binary images of nonbinary LDPC block codes and LDPC convolutional codes, respectively. A set of performance measures applicable to different classes of LDPC codes are considered and a greedy algorithm for code performance optimization is presented. For a few classes of LDPC codes examples of codes combining good error-correcting performance with compact representation are obtained. Moreover, a specific channel model can easily be embedded into the optimization loop. Thereby, the code can be optimized for a specific channel. The efficiency of such an optimization is demonstrated via an example of Faster Than Nyquist (FTN) signaling using LDPC codes.
Low-density parity-check (LDPC) block codes invented by Gallager in 1962 achieve exceptional error performance on a wide variety of communication channels. LDPC convolutional codes are the convolutional counterparts of LDPC block codes. This dissertation describes techniques for the design of LDPC convolutional codes, and analyzes their distance properties and iterative decoding convergence thresholds. The construction of time invariant LDPC convolutional codes by unwrapping the Tanner graph of algebraically constructed quasi-cyclic LDPC codes is described. The convolutional codes outperform the quasi-cyclic codes from which they are derived. The design of parity-check matrices for time invariant LDPC convolutional codes by the polynomial extension of a base matrix is proposed. An upper bound on free distance, proving that time invariant LDPC codes are not asymptotically good, is obtained. The Tanner graph is used to describe a pipelined message passing based iterative decoder for LDPC convolutional codes that outputs decoding results continuously. The performance of LDPC block and convolutional codes are compared for fixed decoding parameters like computational complexity, processor complexity, and decoding delay. In each case, the LDPC convolutional code performance is at least as good as that of LDPC block codes. An analog circuit to implement pipelined decoding of LDPC convolutional codes is proposed. The distance properties of a permutation matrix based (time varying) ensemble of (J,K) regular LDPC convolutional codes is investigated. It is proved that these codes (for J > 2) have free distance increasing linearly with constraint length, i.e., they are asymptotically good. Further, the asymptotic free distance to constraint length ratio for the convolutional codes is several times larger than the minimum distance to block length ratio for corresponding LDPC block codes. Iterative decoding of terminated LDPC convolutional codes, based on the ensemble mentioned above, is analyzed, assuming transmission over a binary erasure channel. The structured irregularity of the codes leads to significantly better convergence thresholds compared to corresponding LDPC block codes. At the calculated thresholds, both the bit and block error probability can be made arbitrarily small. The results obtained suggest that the thresholds approach capacity with increasing J.
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.
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.
Techniques for searching for good quasi-cyclic (QC) LDPC block codes of short and moderate lengths which are suitable for practical purposes are studied. To facilitate implementations only codes whose parity-check matrices having bidiagonal structure of their submatrices and consequently having low encoding complexity are considered. The problem of finding QC LDPC codes with the near-optimum frame or bit error rate performance is split into two independent steps: searching for the near-optimum column degree distribution of the parity-check matrix together with the best base matrix for this degree distribution and searching for the near-optimum labeling of the chosen base matrix. Sets of parameters and criteria for both steps are introduced and discussed. They allow further reduction of the search complexity without significant loss of the search optimality. New QC LDPC block codes of various code rates are obtained and their BER and FER performances are compared with those of the LDPC block codes as well as the turbo codes defined in the IEEE 802.16 WiMAX standard.
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.