Journal of Xidian University

Novel method for counting short cycles of Tanner graphs

Zhou Li-hua

Published Jan 1, 2010• 1 citation

Abstract

Short cycles have an important influence on iterative decoding for low-density parity-check(LDPC) codes.By using tree expanding of Tanner graphs and the analysis of the influence of invalid cycles and duplicate cycles,a formula for counting short cycles of LDPC codes is derived.With the derived formula,an algorithm for counting short cycles of Tanner graphs based on tree expanding is proposed.The proposed algorithm can count short cycles with arbitrary lengths,and thus overcomes the disadvantage of existing algorithms that count short cycles with given lengths.Numerical results of counting short cycles of some typical LDPC codes show the correctness of the proposed algorithm.

Related papers

Counting Short Cycles of Quasi Cyclic Protograph LDPC Codes

Mehdi Karimi, Amir H. Banihashemi

An efficient method for counting short cycles in the Tanner graphs of quasi cyclic (QC) protograph low-density parity-check (LDPC) codes is presented. The method is based on the relationship between the number of short cycles in the graph and the eigenvalues of the directed edge matrix of the graph. We demonstrate that for a QC protograph LDPC code, the complexity of computing such eigenvalues can be reduced significantly by representing the directed edge matrix as a block circulant matrix. Numerical results are presented to show the lower complexity of the proposed method compared to the existing algorithms for counting short cycles. These results also reveal that QC LDPC codes on average have a superior short cycle and girth distribution compared to similar randomly constructed codes.

IEEE Communications LettersFeb 10, 201234 citations

A Method of Counting the Number of Cycles in LDPC Codes

Jun Fan, Yang Xiao

For a given block length sequences of the underlying Tanner graph (TG), the short circles of low-density parity check (LDPC) codes can have considerable variation in performance. By analyzing the shapes of the cycles of TG in parity check matrix, this paper presents a method of counting the number of 4-cycles, 6-cycles, 8-cycles and 10-cycles. Taking out a certain number of rows for different cycles, counting the number of cycles contained in these rows, then adding up all the number of cycles that contained in all possible combinations of the rows in the matrix, and we can get the number of cycles in the matrix. This method can be used effectively to evaluate the performance of LDPC codes according to their short circles distributions. Applying this method, we counting the number of cycles in the random LDPC codes and the quasi-cyclic LDPC codes, the BER performance shows that the random LDPC codes outperform the quasi-cyclic LDPC codes although their girth performance is not as good as the quasi-cyclic LDPC codes.

Jan 1, 200627 citations

Improved method for detecting the short cycles of LDPC codes

Pan Hu, Hongyu Zhao

It is well known that the short cycles in Tanner Graph (TG) greatly impact on the iterative decoding performance of low density parity check (LDPC) codes. In previous literature two methods can be found for detecting such short cycles. This paper presents an improved version of previous Jun Fan's method, which is based on combinational analysis and enumeration of the check matrix patterns caused by cycles of length of 4, 6, 8 and 10 in the corresponding TG. The improved method can more exactly detect the cycles of length greater than 4 in comparison with Jun Fan's method. The validation of the proposed method can be verified by the detection results of short cycles for some LPDC codes.

IEEE International Conference on Information Theory and Information SecurityDec 1, 20105 citations

A Method of Counting the Number of Cycles in LDPC Codes

Yang Xiao

For a given block length sequence of the underlying Tanner graph (TG),the short circles of low-density parity check (LDPC) codes can have considerable variation in performance.By analyzing the shapes of the cycles of TG in parity check matrix,this paper presents a method of counting the number of 4-cycles,6-cycles,8-cycles and 10-cycles.Taking out a certain number of rows for different cycles,counting the number of cycles contained in these rows,then add up all the number of cycles that contained in all possi- ble combination of the rows in the matrix,and we can get the number of cycles in the matrix.This method can be used effectively to eval- uate the performance of LDPC codes according to their short circles distributions.Applying this method,we counting the number of cycles in the random LDPC codes and the quasi-cyclic LDPC codes,the BER performance shows that the random LDPC codes outperform the quasi-cyclic LDPC codes although it's girth performance is not as good as the quasi-cyclic LDPC codes.

Signal ProcessingJan 1, 20081 citation

AN EFFICIENT ALGORITHM FOR COUNTING CYCLES IN QC AND APM LDPC CODES

Mohammad Gholami, Zahra Gholami

In this paper, a new method is given for counting cycles in the Tanner graph of a (Type-I) quasi-cyclic (QC) low-density parity-check (LDPC) code which the complexity mainly is dependent on the base matrix, independent from the CPM-size of the constructed code. Interestingly, for large CPM-sizes, in comparison of the existing methods, this algorithm efficiently counts the cycles of any lengths in the Tanner graphs of QC-LDPC codes. In fact, the algorithm recursively counts the cycles in the paritycheck matrix column-by-column by finding all non-isomorph tailless backtrackless closed (TBC) walks in the base graph and enumerating theoretically their corresponding cycles in the same equivalent class. Moreover, this approach can be modified in few steps to find the cycle distributions of a class of LDPC codes based on Affine permutation matrices (APM-LDPC codes). Interestingly, unlike the existing methods which count the cycles up to 2g - 2, where g is the girth, the proposed algorithm can be used to enumerate the cycles of arbitrary length in the Tanner graph. Moreover, the proposed cycle searching algorithm improves upon various previously known methods, in terms of computational complexity and memory requirements.

arXiv:2310.12556Facta Universitatis Series Mathematics and InformaticsDec 13, 20240 citations

A new algorithm of counting the number of small stopping sets and girth in QC-LDPC Codes

Lingjun Kong, Yang Xiao

It is well known that the performance of low-density parity check (LDPC) codes under iterative decoding is determined by certain combinatorial structures (such as stopping sets and girth) in the Tanner graph. The difficulty in enumerating all possible combinations of the columns may prevent an efficient search of good LDPC codes with small stopping sets and girth. To solve the problem, this paper presents a new algorithm of counting the number of small stopping sets and girth by analyzing the shapes of the cycles of Tanner graph in parity check matrix for designing good LDPC codes which is less complex than the existing algorithms. This method can be used effectively to evaluate the performance of LDPC codes according to their small stopping sets and girth distributions.

Oct 1, 20080 citations