In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than , and a relatively mild necessary and sufficient condition for the code to have a girth of or is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than , and a relatively mild necessary and sufficient condition for the code to have a girth of or is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.

Jan 1, 20030 citations

Quasicyclic low density parity check codes

M.P.C. Fossorier

In this work, the construction of low density parity check codes (LDPCs) from circulant permutation matrices is investigated. It is shown that such codes can not have a Tanner graph representation with girth larger than 12, and a relatively loose necessary and sufficient condition for the code to have a girth of 6, 8, 10 or 12 is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered.In this work, the construction of low density parity check codes (LDPCs) from circulant permutation matrices is investigated. It is shown that such codes can not have a Tanner graph representation with girth larger than 12, and a relatively loose necessary and sufficient condition for the code to have a girth of 6, 8, 10 or 12 is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered.

IEEE International Symposium on Information Theory (ISIT)Jan 1, 200317 citations

Quasi-Cyclic Low-Density Parity-Check Codes With Girth Larger Than $12$

Sunghwan Kim, Jong‐Seon No, Habong Chung +1 more

A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices (or circulants). In this correspondence, we find all the subgraph patterns of protographs of QC LDPC codes having inevitable cycles of length 2i, i = 6, 7, 8, 9,10, i.e., the cycles that always exist regardless of the shift values of circulants. It is also derived that if the girth of the protograph is 2g, g > 2, its protograph code cannot have the inevitable cycles of length smaller than 6g. Based on these subgraph patterns, we propose new combinatorial construction methods of the protographs, whose protograph codes can have girth larger than or equal to 14 or 18. We also propose a couple of shift value assigning rules for circulants of a QC LDPC code guaranteeing the girth 14.A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices (or circulants). In this correspondence, we find all the subgraph patterns of protographs of QC LDPC codes having inevitable cycles of length 2i, i = 6, 7, 8, 9,10, i.e., the cycles that always exist regardless of the shift values of circulants. It is also derived that if the girth of the protograph is 2g, g > 2, its protograph code cannot have the inevitable cycles of length smaller than 6g. Based on these subgraph patterns, we propose new combinatorial construction methods of the protographs, whose protograph codes can have girth larger than or equal to 14 or 18. We also propose a couple of shift value assigning rules for circulants of a QC LDPC code guaranteeing the girth 14.

IEEE Transactions on Information TheoryAug 1, 200795 citations

Necessary and Sufficient Girth Conditions for LDPC Tanner Graphs with Denser Protographs

Anthony Gómez-Fonseca, Roxana Smarandache, David G. M. Mitchell

This paper gives necessary and sufficient conditions for the Tanner graph of a quasi-cyclic (QC) low-density parity-check (LDPC) code based on the all-one protograph to have girth 6, 8, 10, and 12, respectively, in the case of parity-check matrices with column weight 4. These results are a natural extension of the girth results of the already-studied cases of column weight 2 and 3, and it is based on the connection between the girth of a Tanner graph given by a parity-check matrix and the properties of powers of the product between the matrix and its transpose. The girth conditions can be easily incorporated into fast algorithms that construct codes of desired girth between 6 and 12; our own algorithms are presented for each girth, together with constructions obtained from them and corresponding computer simulations. More importantly, this paper emphasizes how the girth conditions of the Tanner graph corresponding to a parity-check matrix composed of circulants relate to the matrix obtained by adding (over the integers) the circulant columns of the parity-check matrix. In particular, we show that imposing girth conditions on a parity-check matrix is equivalent to imposing conditions on a square circulant submatrix obtained from it.This paper gives necessary and sufficient conditions for the Tanner graph of a quasi-cyclic (QC) low-density parity-check (LDPC) code based on the all-one protograph to have girth 6, 8, 10, and 12, respectively, in the case of parity-check matrices with column weight 4. These results are a natural extension of the girth results of the already-studied cases of column weight 2 and 3, and it is based on the connection between the girth of a Tanner graph given by a parity-check matrix and the properties of powers of the product between the matrix and its transpose. The girth conditions can be easily incorporated into fast algorithms that construct codes of desired girth between 6 and 12; our own algorithms are presented for each girth, together with constructions obtained from them and corresponding computer simulations. More importantly, this paper emphasizes how the girth conditions of the Tanner graph corresponding to a parity-check matrix composed of circulants relate to the matrix obtained by adding (over the integers) the circulant columns of the parity-check matrix. In particular, we show that imposing girth conditions on a parity-check matrix is equivalent to imposing conditions on a square circulant submatrix obtained from it.

arXiv:2106.00861International Symposium on Turbo Codes and Iterative Information ProcessingAug 30, 20212 citations

Necessary and sufficient condition for Tanner codes without girth 4

Yang Xiao

To solve the problem of the girth 4 which will lead to a serious decrease in the performance of quasi-cyclic low-density parity-check(QC LDPC) codes,this paper presents the necessary and sufficient conditions of Tanner codes without girth 4 in the form of several theorems.These theorems can be used as the constraint conditions for the construction of Tanner codes.To construct the Tanner codes without girth 4 needs to adjust the dimension and the shift factors of the circulant matrices of the given sparse parity-check matrices according to the proposed theorems.Examples are provided to verify the theorems,and computer simulation results show that the Tanner codes obtained by proposed constructions achieve good BER performance compared with that of randomly constructed LDPC codes.To solve the problem of the girth 4 which will lead to a serious decrease in the performance of quasi-cyclic low-density parity-check(QC LDPC) codes,this paper presents the necessary and sufficient conditions of Tanner codes without girth 4 in the form of several theorems.These theorems can be used as the constraint conditions for the construction of Tanner codes.To construct the Tanner codes without girth 4 needs to adjust the dimension and the shift factors of the circulant matrices of the given sparse parity-check matrices according to the proposed theorems.Examples are provided to verify the theorems,and computer simulation results show that the Tanner codes obtained by proposed constructions achieve good BER performance compared with that of randomly constructed LDPC codes.

Systems engineering and electronicsJan 1, 20091 citation

Anti Quasi-Cyclic LDPC Codes

Zahra Gholami, Mohammad Gholami

Low-density parity-check (LDPC) codes based on affine permutation matrices, APM-LDPC codes, have been attracted recently, because of some advantages rather than QC-LDPC codes in minimum-distance, cycle distribution and error-rate performance. In this letter, circulant and anti-circulant permutation matrices are used to define a class of LDPC codes, called AQC-LDPC codes, which can be considered as an special case of APM-LDPC codes. In fact, each AQC-LDPC code can be verified by a sign matrix and a slope matrix which are helpful to show each cycle in the Tanner graph by a modular linear equation. For the normal sign matrix A , if -1 ϵ, A, it is shown that the corresponding AQC-LDPC code has maximum-girth 8. Finally, two explicit constructions for AQC-LDPC codes with girths 6, 8 are presented which have some benefits rather than the explicitly constructed QC and APM LDPC codes in minimum-distance, cycle distributions and bit-error-rate performances.Low-density parity-check (LDPC) codes based on affine permutation matrices, APM-LDPC codes, have been attracted recently, because of some advantages rather than QC-LDPC codes in minimum-distance, cycle distribution and error-rate performance. In this letter, circulant and anti-circulant permutation matrices are used to define a class of LDPC codes, called AQC-LDPC codes, which can be considered as an special case of APM-LDPC codes. In fact, each AQC-LDPC code can be verified by a sign matrix and a slope matrix which are helpful to show each cycle in the Tanner graph by a modular linear equation. For the normal sign matrix A , if -1 ϵ, A, it is shown that the corresponding AQC-LDPC code has maximum-girth 8. Finally, two explicit constructions for AQC-LDPC codes with girths 6, 8 are presented which have some benefits rather than the explicitly constructed QC and APM LDPC codes in minimum-distance, cycle distributions and bit-error-rate performances.

IEEE Communications LettersMar 26, 20185 citations