Search

In this paper, we propose a new technique, based on the so-called breadth-first search algorithm, to count the short cycles of a bipartite graph. For a general bipartite graph with $|V|$ nodes and girth $g$ , our technique has a time complexity of $\mathcal {O}(|V|^{2}\Delta)$ to count $g$ -cycles and $(g+2)$ -cycles, and a time complexity of $\mathcal {O}(|V|^{2}\Delta ^{2})$ to count $(g+4)$ -cycles, where $\Delta $ is the maximum node degree in the graph. Moreover, for bi-regular bipartite graphs, the latter complexity is further reduced to $\mathcal {O}(|V|^{2}\Delta)$. Compared to the fastest known algorithm, which has a complexity $\mathcal {O}(g |V|^{2} \Delta ^{2})$ , the proposed method always has a lower complexity for counting $g$ -cycles and $(g+2)$ -cycles. It also has a lower complexity for counting $(g+4)$ -cycles in bi-regular graphs and in scenarios where $g$ is increased with the size of the graph. Related to the problem of counting short cycles, we also demonstrate, using a long-standing conjecture, that there is no algorithm with time complexity less than $\mathcal {O}\left({|V|^{2-\frac {2}{1+i}}}\right)$ that can determine whether a given sparse bipartite graph has a cycle of length $4i$. An important application of the results presented here is to count the short cycles of Tanner graphs of low-density parity-check (LDPC) codes. [ABSTRACT FROM AUTHOR]

In this paper, we give lower bounds on the size of $(a,b)$ elementary trapping sets (ETSs) of variable-regular LDPC codes with any girth, $g$ , and irregular ones with girth 8, where $a$ is the size and $b$ is the number of degree-one check nodes. Our proposed lower bounds are analytical, applicable to all values of $g$ and $b$ , based on graph theories and tighter than the existing ones in the literature. Our results mostly depend on the girth. We also propose results, which are independent of the girth and rely on the variables $a$ , $b$ , $\gamma $ , and the column weight value. We obtain the tightest lower bounds on the size of ETSs of variable-regular LDPC codes with girth eight. These results provide us with a chance to present a method to achieve the minimum size of ETSs of irregular LDPC codes with girth, especially those whose column weight values are a subset of {2, 3, 4, 5, 6} and fulfill the inequality $(b/a)<1$. Moreover, we present a range of numerical results about $(a,b)$ ETSs with girths 8 and 10 to compare the tightness between our proposed lower bounds and the existing bounds in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we deal with time-invariant spatially coupled low-density parity-check convolutional codes (SC-LDPC-CCs). Classic design approaches usually start from quasi-cyclic low-density parity-check block codes and exploit suitable unwrapping procedures to obtain SC-LDPC-CCs. We show that the direct design of the SC-LDPC-CCs syndrome former matrix or, equivalently, the symbolic parity-check matrix, leads to codes with smaller syndrome former constraint lengths with respect to the best solutions available in the literature. We provide theoretical lower bounds on the syndrome former constraint length for the most relevant families of SC-LDPC-CCs, under constraints on the minimum length of cycles in their Tanner graphs. We also propose new code design techniques that approach or achieve such theoretical limits. [ABSTRACT FROM PUBLISHER]