On the Tanner Graph Cycle Distribution of Random LDPC, Random Protograph-Based LDPC, and Random Quasi-Cyclic LDPC Code Ensembles

DOI10.1109/TIT.2018.2805906zbMATH Open1395.94347arXiv1701.02379MaRDI QIDQ5375587FDOQ5375587

Authors: A. Dehghan, Amir H. Banihashemi 

Publication date: 14 September 2018

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasi-cyclic (QC) LDPC codes. We prove that for a random bipartite graph, with a given (irregular) degree distribution, the distributions of cycles of different length tend to independent Poisson distributions, as the size of the graph tends to infinity. We derive asymptotic upper and lower bounds on the expected values of the Poisson distributions that are independent of the size of the graph, and only depend on the degree distribution and the cycle length. For a random lift of a bi-regular protograph, we prove that the asymptotic cycle distributions are essentially the same as those of random bipartite graphs as long as the degree distributions are identical. For random QC-LDPC codes, however, we show that the cycle distribution can be quite different from the other two categories. In particular, depending on the protograph and the value of $c$, the expected number of cycles of length $c$, in this case, can be either $Theta(N)$ or $Theta(1)$, where $N$ is the lifting degree (code length). We also provide numerical results that match our theoretical derivations. Our results provide a theoretical foundation for emperical results that were reported in the literature but were not well-justified. They can also be used for the analysis and design of LDPC codes and associated algorithms that are based on cycles.

Full work available at URL: https://arxiv.org/abs/1701.02379

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Cyclic codes (94B15)

Cited In (4)

• Detecting cycles of length 10 in the Tanner graph of a QC-LDPC code based on protograph analysis
• Global eigenvalue fluctuations of random biregular bipartite graphs
• Cospectral bipartite graphs with the same degree sequences but with different number of large cycles
• Counting short cycles of \((c,d)\)-regular bipartite graphs

This page was built for publication: On the Tanner Graph Cycle Distribution of Random LDPC, Random Protograph-Based LDPC, and Random Quasi-Cyclic LDPC Code Ensembles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5375587)