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

Design of Structured Regular LDPC Codes without Short Cycles using Gray Code Representations

Vibha Kulkarni, K. Jaya Sankar

Published Jan 1, 2013• 0 citations
OpenAlex

Abstract

Low Density Parity Check (LDPC) codes are specified by the parity check matrix H. Smaller girths in the Tanner graphs of LDPC codes prevent the sum-product algorithm from converging, i.e., short cycles in H-matrix degrade the performance of LDPC decoder. In this paper, we present an algorithm for constructing LDPC codes without short cycles. The H-matrix must be sufficiently sparse to increase the girth of a code. In this work, we present a simple method to increase the sparsity of matrix and provide lemmas to avoid short cycles of lengths 4 and 6. We design sub-matrices for column-weight two and column-weight three codes. This design makes use of a simple shifting function given by the proposed scheme. These are then combined into a final H-matrix using Gray code representations. The proposed method provides structured, regular codes with flexibility in code rates and code lengths. The regularity of these codes gives the advantages like simplicity of hardware implementation and fast encoding. Key words LDPC codes, Tanner Graph, Girth, Gray codes

Related papers

The Design of Structured Low-Density Parity-Check Codes With Large Girth

Jing Long

This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.

Chinese Journal of Computers•Jan 1, 2007•1 citation

Design of LDPC Codes with Large Girth Based on the Submatrix Shifting Method

Yang Xiao

By analyzing the shapes of 4-cycles and 6-cycles of TG in parity check matrix,this paper presents a method of counting the number of 4-cycles and 6-cycles.Considering the cycles,especially the short cycles,degrade the performance of LDPC decoders,this paper then proposes a design of regular check matrix for Low-Density Parity-Check(LDPC) codes with girth 8.The proposed construction algorithm for LDPC codes is to design 3 submatrices with different given shifting functions,then combine them into one matrix,and finally expand the transposed matrix of the combination matrix into a desired parity check matrix using the identity matrix and the cyclic shift matrices of the identity matrix randomly.The simulation results in the AWGN channel show that the BER performance of these codes obtained by the generation matrix derived from the proposed check matrices in encoding the random information bits is as good as that of the random LDPC codes.

Journal of the China Railway Society•Jan 1, 2007•0 citations

Quasi-Cyclic Low-Density Parity-Check Codes Based on Progressive Cycle Growth Algorithm

Yuanhua Liu, Meiling Zhang, Niu Xin-Liang

Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.

International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC)•Jul 1, 2016•1 citation

Generalized Construction of Quasi-Cyclic Regular LDPC Codes Based on Permutation Matrices

E.M. Gabidulin, Abdolhosein Moinian, Bahram Honary

A new approach is proposed for constructing regular low-density parity-check (LDPC) codes based on tensor product of matrices. In this paper, first a general construction method of regular LDPC codes exploiting permutation matrices is described. Constructed codes have a quasi-cyclic structure with no short cycles of length 4 in their Tanner graph, hence simple encoding while maintaining good performance is achieved. The paper also demonstrates a generalized design, which covers a large family of LDPC codes and number of other construction methods. The new generalized LDPC codes are defined by a small number of parameters and cover a large set of code lengths and rates. Using these codes, LDPC matrices of any column weight and row weight can be constructed. Performance of these codes under iterative decoding compares well with other well-structured as well as random LDPC codes

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•16 citations

Structured LDPC Codes with Linear Complexity Encoding

Vinay Bhardwaj, Nagendra Prasad Pathak, Arun R. Kumar

Low density parity check (LDPC) codes have stimulated a lot of interest in recent years due to their capacity approaching performance and availability of fast decoding algorithms. The existing encoding scheme for LDPC code usually incurs too high complexity and should be changed to encoding scheme with low complexity. An elementary turbo structured Tanner graph construction and encoding scheme for a family of regular LDPC codes attaining desired high girth is studied in this paper. The construction provides flexibility in choice of parameters like column weight (j > =2), row weight k and arbitrary girth g. Turbo structured low density parity check ( TS-LDPC) codes are regular LDPC codes with their Tanner graph consists of two trees connected by an interleaver. Linear complexity is attained with few alterations and restrictions of in Tanner graph of turbo structured LDPC codes. Simulation results demonstrates that not only the bit error rate (BER) performance of TSLDPC codes at low signal to noise ratio (SNR) is comparable with error performance of corresponding random LDPC codes, with better error performance at high SNR but linear encoding considerably reduces simulation time.

•Jan 1, 2009•3 citations

Construction of low density parity check codes without short cycles

Lizhi Wu

With the rapid expansion of communication networks, there has been an increasing demand for efficient and reliable digital data transmission and storage systems. Many efficient codes have been developed. The LDPC code is one of them. In this thesis, the sum-product algorithm is used in the decoding of LDPC codes. Some schemes for encoding LDPC codes have been studied. In particular, two methods of producing regular H matrices have been attempted that include short cycles of length four with code rates of 0.5, and we present three schemes of finding regular H matrices which do not include short cycles of length four with code rate being 0.5. The effect of short cycles in the bipartite graph of regular LDPC codes has been considered. The simulation results show that the BER performances of regular H matrices that do not include short cycles of length four based on BPSK or 8PSK on AWGN channel is better than those of regular H matrices that include short cycles of length four. In conclusion, in order to obtain good performance with LDPC code, one should design H matrix related to bipartite graph without short cycles.

•Jan 1, 2003•0 citations
Low Density Parity Check (LDPC) codes are specified by the parity check matrix H. Smaller girths in the Tanner graphs of LDPC codes prevent the sum-product algorithm from converging, i.e., short cycles in H-matrix degrade the performance of LDPC decoder. In this paper, we present an algorithm for constructing LDPC codes without short cycles. The H-matrix must be sufficiently sparse to increase the girth of a code. In this work, we present a simple method to increase the sparsity of matrix and provide lemmas to avoid short cycles of lengths 4 and 6. We design sub-matrices for column-weight two and column-weight three codes. This design makes use of a simple shifting function given by the proposed scheme. These are then combined into a final H-matrix using Gray code representations. The proposed method provides structured, regular codes with flexibility in code rates and code lengths. The regularity of these codes gives the advantages like simplicity of hardware implementation and fast encoding. Key words LDPC codes, Tanner Graph, Girth, Gray codes
This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.
By analyzing the shapes of 4-cycles and 6-cycles of TG in parity check matrix,this paper presents a method of counting the number of 4-cycles and 6-cycles.Considering the cycles,especially the short cycles,degrade the performance of LDPC decoders,this paper then proposes a design of regular check matrix for Low-Density Parity-Check(LDPC) codes with girth 8.The proposed construction algorithm for LDPC codes is to design 3 submatrices with different given shifting functions,then combine them into one matrix,and finally expand the transposed matrix of the combination matrix into a desired parity check matrix using the identity matrix and the cyclic shift matrices of the identity matrix randomly.The simulation results in the AWGN channel show that the BER performance of these codes obtained by the generation matrix derived from the proposed check matrices in encoding the random information bits is as good as that of the random LDPC codes.
Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.
A new approach is proposed for constructing regular low-density parity-check (LDPC) codes based on tensor product of matrices. In this paper, first a general construction method of regular LDPC codes exploiting permutation matrices is described. Constructed codes have a quasi-cyclic structure with no short cycles of length 4 in their Tanner graph, hence simple encoding while maintaining good performance is achieved. The paper also demonstrates a generalized design, which covers a large family of LDPC codes and number of other construction methods. The new generalized LDPC codes are defined by a small number of parameters and cover a large set of code lengths and rates. Using these codes, LDPC matrices of any column weight and row weight can be constructed. Performance of these codes under iterative decoding compares well with other well-structured as well as random LDPC codes
Low density parity check (LDPC) codes have stimulated a lot of interest in recent years due to their capacity approaching performance and availability of fast decoding algorithms. The existing encoding scheme for LDPC code usually incurs too high complexity and should be changed to encoding scheme with low complexity. An elementary turbo structured Tanner graph construction and encoding scheme for a family of regular LDPC codes attaining desired high girth is studied in this paper. The construction provides flexibility in choice of parameters like column weight (j > =2), row weight k and arbitrary girth g. Turbo structured low density parity check ( TS-LDPC) codes are regular LDPC codes with their Tanner graph consists of two trees connected by an interleaver. Linear complexity is attained with few alterations and restrictions of in Tanner graph of turbo structured LDPC codes. Simulation results demonstrates that not only the bit error rate (BER) performance of TSLDPC codes at low signal to noise ratio (SNR) is comparable with error performance of corresponding random LDPC codes, with better error performance at high SNR but linear encoding considerably reduces simulation time.
With the rapid expansion of communication networks, there has been an increasing demand for efficient and reliable digital data transmission and storage systems. Many efficient codes have been developed. The LDPC code is one of them. In this thesis, the sum-product algorithm is used in the decoding of LDPC codes. Some schemes for encoding LDPC codes have been studied. In particular, two methods of producing regular H matrices have been attempted that include short cycles of length four with code rates of 0.5, and we present three schemes of finding regular H matrices which do not include short cycles of length four with code rate being 0.5. The effect of short cycles in the bipartite graph of regular LDPC codes has been considered. The simulation results show that the BER performances of regular H matrices that do not include short cycles of length four based on BPSK or 8PSK on AWGN channel is better than those of regular H matrices that include short cycles of length four. In conclusion, in order to obtain good performance with LDPC code, one should design H matrix related to bipartite graph without short cycles.