Cycle distribution of LDPC(Low-Density Parity-Check) codes affects the codes decoding performance and encoding complexity,however it is commonly NP hard to analyse.We propose the rotation-distance for analysis of QC-LDPC(Quasi-Cyclic Low-Density Parity-Check) code based on circulant matrices.The circulant sub-matrices within the parity-check are treated as a matrix node to simplify theTanner graphs of the codes.Thus cycles of QC-LDPC codes can be found efficiently,and we demonstrate the usefulness of the new method by a simple proof of the known result that 12 is an upper limit of the girth of the QC-LDPC codes we considered.Moreover,the cycle analysis based on the new method also reveals relations between decoding performance and the cycle distribution of the code.
Cycle distribution of LDPC(Low-Density Parity-Check) codes affects the codes decoding performance and encoding complexity,however it is commonly NP hard to analyse.We propose the rotation-distance for analysis of QC-LDPC(Quasi-Cyclic Low-Density Parity-Check) code based on circulant matrices.The circulant sub-matrices within the parity-check are treated as a matrix node to simplify theTanner graphs of the codes.Thus cycles of QC-LDPC codes can be found efficiently,and we demonstrate the usefulness of the new method by a simple proof of the known result that 12 is an upper limit of the girth of the QC-LDPC codes we considered.Moreover,the cycle analysis based on the new method also reveals relations between decoding performance and the cycle distribution of the code.
In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.
In this paper a new low complexity method for constructing binary quasi-cyclic low-density parity-check (QC-LDPC) codes is introduced. In the proposed method, each block-column of the parity check matrix H is made by a circulant matrix in a way that the associated Tanner graph is free of cycle four. Each circulant matrix in H is made by a generator column. The generator columns should be selected in a way that each associated circulant matrix and every two distinct circulant matrices are free of cycle four. The generator columns are made by row distance sets. An algorithm for generating distance sets and obtaining circulant matrices with columns of weight three is presented separately. Simplicity of construction and having a good flexible family of quasi cyclic LDPC codes both in rate and length are the main properties of the proposed method. The performance of the proposed codes is compared with that of the random-like and Array LDPC codes over an AWGN channel. Simulation results show that from the performance perspective, the constructed codes are competitive with random-like and Array LDPC codes.
A quasi-cyclic (QC) low-density parity-check
(LDPC) code can be viewed as the protograph code with circulant
permutation matrices. In this paper, we use permutation matrices
to form protograph LDPC codes. In protograph LDPC codes, we
present cycle relationships of the mother matrix and the
protograph LDPC code. It is derived that the girth of a protograph
LDPC code is no smaller than its mother matrix .And cycles in the
protograph LDPC codes are uniquely induced by the cycles in its
mother matrix.
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.
A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices. In this paper, 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 existing regardless of the shift values of circulants. It is also derived that if the girth of the protograph is 2g,gges 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.
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.