1 Introduction

In the last 50 years, LDPC codes came to prominence, since they outperform in iterative decoding and show the capacity approaching performance. QC-LDPC codes, an important class of LDPC codes perform very well in encoding as well as in decoding because of its quasi-cyclic nature and so, have been adopted by many communication systems [2]. A regular-(J,L)-QC-LDPC code with CPM size \( {q} \), is specified by a parity-check matrix (PCM) H, which is a \( J \times L \) array of \( q \times q \) circulant permutation matrices (CPMs). The CPM \( I\left( {e_{ij} } \right) \), \( 1 \le i \le J, 1 \le j \le L \), is the \( q \times q \) identity matrix in which ones in each row are cyclically shifted to the right by \( e_{ij} \) positions. The matrix \( \left[ {e_{ij} } \right]_{J \times L} \) is called the exponent matrix. The one can derive a PCM from an exponent matrix by replacing its elements with the corresponding circulant matrices. The iterative decoding performance of QC-LDPC codes depends upon the girth of the code. Girth is the length of the shortest cycle present in the Tanner graph representation of code [9]. QC-LDPC codes, free from short-cycles, i.e., with girth at least six have better decoding performance in comparison with codes having short-cycles. Therefore, to construct QC-LDPC codes with girth six or more and having the minimum CPM size is the core aim of current research [1, 3,4,5,6,7, 10, 12, 20]. QC-LDPC codes are also used as underlying codes for the construction of QC-LDPC lattices to achieve the sphere-bound [6].

Although QC-LDPC codes can be constructed by a variety of methods, the constructions based on exponent matrices or base matrices have attracted much attention [3, 5, 8, 11, 13, 14]; these constructions give ease to find the short-cycles even when the code has large block length. The construction of QC-LDPC codes with base matrices can further be categorised as the algebraic methods [8, 15,16,17,18] and the search based methods [1, 3, 13, 14]. The method based on difference matrices is also seemed useful to generate the QC-LDPC codes of more considerable girth and with less complexity [1].

At the outset, in 2004, the girth-6 (J,L)-QC-LDPC codes for \( J = 2,3,4,5,6 \) have been constructed with a combination of algebraic method and the computer search, but the search was limited to only L = 13 [3]. The necessary and sufficient conditions for (J,L)-QC-LDPC codes for given girth were also derived in [3]. Later on, a significant part of the work has been devoted to the search of QC-LDPC codes with the minimum CPM size and higher girth [4, 5, 10, 12, 13, 20]. The work was extended in [18], which proposed the girth-8 (3,L)-QC-LDPC codes of smaller CPM size. In continuity, (5,L) and (6,L)-QC-LDPC codes with girth at least eight were deterministically constructed by [19] and proved that (5,L) and (6,L)-QC-LDPC codes always exist for CPM size \( q \ge \left( {2L + 3} \right)\left( {L - 1} \right) + 1 \) and \( q \ge 2\left( {L + 5} \right)\left( {L - 1} \right) + 1 \) respectively, which were the improvements over two existing bounds \( L^{2} \left( {L - 1} \right) + 1 \) and \( (L^{2} + 1)\left( {L - 1} \right) + 1 \), respectively. Similar work was done by [14], which searched the ((3,4,5,6),L)-QC-LDPC codes with girth at least eight for \( L \le 25 \), out of which most of the codes are of smaller size in comparison with existing codes. In literature, it is observed that the most of the algebraic constructions of (J,L)-QC-LDPC codes are based on row multipliers, as in [5], girth-8 (J,L)-QC-LDPC codes for \( J = 3,4,5,6 \), were constructed by row multipliers \( \left( {0,1,L,L + 1,L^{2} ,L^{2} + 1} \right) \). In [17], row multipliers, to construct a girth-8 QC-LDPC code were derived using the greatest common divisor (GCD) method. In [19], \( \left( {J,L} \right) \)-QC-LDPC codes with girth at least eight were constructed by taking the row multipliers \( \left( {0,1,L,L + 1,L^{2} ,L^{2} + 1,L^{2} + L,L^{2} + L + 1} \right) \), for \( J = 3 \) to \( 8 \). Therefore, we can see that most of the existing methods concentrated only on row multipliers to construct the exponent matrices of QC-LDPC codes and also the codes constructed by row multipliers have larger CPM size for larger values of L.

In this paper, a new way to construct the exponent matrix E of a QC-LDPC code is proposed, which is based on the column multipliers. The idea gives an algebraic structure of (3,L)-QC-LDPC codes with girth at least eight, and having smaller CPM size as compared to the respective codes constructed by row multipliers. The structure of the exponent matrix based on column multipliers is defined as follow:

Definition 1.1

Let \( E = \left[ {e_{ij} } \right] \) be an exponent matrix of order \( 3 \times L \), such that \( e_{ij} = \left( {i - 1} \right)\left( {S_{j} - 1} \right) \) for all \( 1 \le i \le 3 \), \( 1 \le j \le L \)\( (L > 3) \). i.e.

$$ E = \left[ {\begin{array}{*{20}c} {\left( {S_{1} - 1} \right).0} & {\left( {S_{2} - 1} \right).0} & {\left( {S_{3} - 1} \right).0} \\ {\left( {S_{1} - 1} \right).1} & {\left( {S_{2} - 1} \right).1} & {\left( {S_{3} - 1} \right).1} \\ {\left( {S_{1} - 1} \right).2} & {\left( {S_{2} - 1} \right).2} & {\left( {S_{3} - 1} \right).2} \\ \end{array} \begin{array}{*{20}c} { \ldots \ldots } \\ { \ldots \ldots } \\ { \ldots \ldots } \\ \end{array} \begin{array}{*{20}c} {\left( {S_{L} - 1} \right).0} \\ {\left( {S_{L} - 1} \right).1} \\ {\left( {S_{L} - 1} \right).2} \\ \end{array} } \right]_{3 \times L} $$

Here, \( S_{\alpha } \) gives us the value of column multiplier for the \( \alpha \)th column. The exponent matrix is derived with the help of generator column \( \left[ {0, 1, 2} \right]^{T} \) by multiplying it with different column multipliers. To find the adequate values of column multipliers, \( S_{\alpha } \) is defined as follow:

Definition 1.2

\( S_{\alpha } = 1 + \mathop \sum \limits_{m = 0}^{k} \alpha_{m} \zeta_{m} \), where, \( \alpha_{m} = \left\lfloor\frac{{\alpha + 2^{m} - 1}}{{2^{m + 1} }} \right\rfloor\) and \( \zeta_{m} = \frac{{3^{m} + 1}}{2} \) such that \( 2^{k} \le \alpha < 2^{k + 1} \), \( \alpha \in {\mathbb{N}} \) and \( k \in {\mathbb{Z}}^{*} \).

Example

If \( L = 7 \), then the column multipliers \( S_{\alpha } \) for \( 1 \le \alpha \le 7 \) are 1, 2, 4, 5, 10, 11, 13 respectively, and the corresponding exponent matrix E is given by:

$$ E = \left[ {\begin{array}{*{20}c} 0 & 0 & 0 \\ 0 & 1 & 3 \\ 0 & 2 & 6 \\ \end{array} \begin{array}{*{20}c} 0 & 0 & 0 \\ 4 & 9 & {10} \\ 8 & {18} & {20} \\ \end{array} \begin{array}{*{20}c} 0 \\ {12} \\ {24} \\ \end{array} } \right] $$

This exponent matrix has corresponded to a (3,7)-QC-LDPC code with girth at least eight.

Also, a lower bound \( q \ge 2S_{L} - 1 \) for the minimum CPM size \( q \) of (3,L)-QC-LDPC codes with girth at least eight, has been proposed, which is the tightest bound among the literature. The main advantage of this method is that it is an algebraic based method due to which it reduces the complexity and gives ease to derive the exponent matrix for any value of \( L > 3 \). Moreover, all the codes constructed from this method are optimal to the given lower bound on the minimum CPM size and for \( L > 25 \) are of shortest CPM size as compared to existing QC-LDPC codes of girth at least eight.

The rest of the paper is ordered as follow: In Sect. 2, the construction and the bound on the minimum CPM size for (3,L)-QC-LDPC codes with girth at least eight are presented. The conclusion of the paper is given in Sect. 3.

2 Construction of (3,L)-QC-LDPC codes with girth at least 8

In this section, explicit construction of the exponent matrix of a girth-8 QC-LDPC code is given. To define the essential properties and characteristics of \( S_{\alpha } \), some of the lemmas are proved. With the help of these lemmas and theorems, it is proved that the exponent matrix E corresponds a (3,L)-QC-LDPC codes of girth at least eight.

Lemma 2.1

If\( \alpha < \beta \)then\( \alpha_{m} < \beta_{m} \), for at least one of the value of\( m \)such that\( 0 \le m \le k, \)\( m \in {\mathbb{Z}}^{*} \)and\( 2^{k} \le \alpha < \beta < 2^{k + 1} \).

Proof

  • Case 1 If \( \beta = \alpha + 1 \)

    • Sub-case 1.1 When \( \alpha \) is odd,

      Since \( \beta = \alpha + 1 \) and \( \alpha \) is odd \( \Rightarrow \)\( \beta \) is even

      \( \Rightarrow \) there exists a number \( t \in {\mathbb{N}} \) such that \( \frac{\beta }{2} = t \) and \( \frac{\alpha }{2} = t - \frac{1}{2} \)\( \therefore\, \beta_{0} = \left\lfloor\frac{{\beta + 2^{0} - 1}}{{2^{0 + 1} }}\right\rfloor = \left\lfloor\frac{\beta }{2}\right\rfloor = t\,{\text{and}}\,\alpha_{0} = \left\lfloor\frac{{\alpha + 2^{0} - 1}}{{2^{0 + 1} }}\right\rfloor = \left\lfloor\frac{\alpha }{2}\right\rfloor = \left\lfloor t - \frac{1}{2}\right\rfloor = t - 1 \Rightarrow \alpha_{0} < \beta_{0} \)

    • Sub-case 1.2 When \( \alpha \) is even

      We, further divide it into two cases

    • Sub-case 1.2.a When \( \alpha = 2^{k} \)

      Then, \( \beta_{k} = \left\lfloor\frac{{2^{k} + 1 + 2^{k} - 1}}{{2^{k + 1} }}\right\rfloor = 1 \) and \( \alpha_{k} = \left\lfloor\frac{{2^{k} + 2^{k} - 1}}{{2^{k + 1} }}\right\rfloor = 0 \Rightarrow \alpha_{k} < \beta_{k} \)

    • Sub-case 1.2.b When \( \alpha \ne 2^{k} \)

      Since \( \alpha \) is even, therefore, there exists at least one \( i \)\( (0 < i < k) \) such that \( 2^{i} |\alpha \) but \( 2^{i + 1} {\nmid }\alpha \)

      therefore, \( \alpha_{i} = \left\lfloor\frac{{\alpha + 2^{i} - 1}}{{2^{i + 1} }}\right\rfloor \) and \( \beta_{i} = \left\lfloor\frac{{\beta + 2^{i} - 1}}{{2^{i + 1} }}\right\rfloor = \left\lfloor\frac{{\alpha + 2^{i} }}{{2^{i + 1} }}\right\rfloor \)

      as, \( 2^{i} |\alpha \) then there exists a number \( t \in {\mathbb{N}} \) such that \( \frac{\alpha }{{2^{i} }} = t \)

      but \( 2^{i + 1} {\nmid }\alpha \)\( \Rightarrow 2^{i + 1} {\nmid }2^{i} .t \)\( \Rightarrow 2{\nmid }t \)\( \Rightarrow t \) is odd and so, let \( \frac{t + 1}{2} = n \in {\mathbb{N}} \)

      now, \( \alpha_{i} = \left\lfloor\frac{{\alpha + 2^{i} - 1}}{{2^{i + 1} }}\right\rfloor \) and \( \beta_{i} = \left\lfloor\frac{{\alpha + 2^{i} }}{{2^{i + 1} }}\right\rfloor \)\( \Rightarrow \)\(\alpha_{i} = \left\lfloor\frac{{2^{i} .t + 2^{i} - 1}}{{2^{i + 1} }}\right\rfloor = n - 1 \) and \( \beta_{i} = \left\lfloor\frac{{2^{i} .t + 2^{i} }}{{2^{i + 1} }}\right\rfloor = n \Rightarrow \alpha_{i} < \beta_{i}. \)

  • Case 2 When \( \beta > \alpha + 1 \)

    Let, \( \beta = \alpha + n \) where \( n \ge 2 \)

    then \( \beta_{0} = \left\lfloor\frac{{\beta + 2^{0} - 1}}{{2^{0 + 1} }}\right\rfloor = \left\lfloor\frac{\beta }{2}\right\rfloor = \left\lfloor\frac{\alpha + n}{2}\right\rfloor \ge \left\lfloor\frac{\alpha }{2} + 1\right\rfloor > \left\lfloor\frac{\alpha }{2}\right\rfloor = \left\lfloor\frac{{\alpha + 2^{0} - 1}}{{2^{0 + 1} }}\right\rfloor = \alpha_{0} \)

    \( \Rightarrow \alpha_{0} < \beta_{0} . \)

    Hence, the proof is complete. □

Lemma 2.2

If\( \alpha < \beta \)then\( S_{\alpha } < S_{\beta } \)for all\( \alpha ,\beta \in {\mathbb{N}} \).

Proof

Since, \( \alpha < \beta \)\( \Rightarrow \)\( \frac{{\alpha + 2^{m} - 1}}{{2^{m + 1} }} < \frac{{\beta + 2^{m} - 1}}{{2^{m + 1} }} \)\( \forall m \in {\mathbb{Z}}^{*} \Rightarrow \left\lfloor\frac{{\alpha + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor \le \left\lfloor\frac{{\beta + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor \)\( \forall m \in {\mathbb{Z}}^{*} \)\( \Rightarrow \alpha_{m} \le \beta_{m} \)\( \forall m \in {\mathbb{Z}}^{*} \)\( \Rightarrow \)\( \alpha_{m} \zeta_{m} \le \beta_{m} \zeta_{m} \)\( \forall m \in {\mathbb{Z}}^{*} \) from Lemma 2.1, we have \( \alpha_{m} < \beta_{m} \) for at least one value of \( m\Rightarrow \mathop \sum \limits_{m = 0}^{k} \alpha_{m} \zeta_{m} < \mathop \sum \limits_{m = 0}^{k} \beta_{m} \zeta_{m} \) where \( \alpha < \beta < 2^{k + 1} \Rightarrow S_{\alpha } < S_{\beta } \).

Lemma 2.3

If\( \alpha = 2^{k} \)then\( S_{\alpha } = \zeta_{k} \,\forall \,k \ge 0 \).

Proof

Since,

$$ \begin{aligned} \alpha_{m} & = \left\lfloor\frac{{\alpha + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor\,{\text{and}}\,0 \le m \le k \\ \Rightarrow \alpha_{m} & = \left\lfloor\frac{{2^{k} + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor = \left\lfloor2^{k - m - 1} + \frac{1}{2} - \frac{1}{{2^{m + 1} }}\right\rfloor = \left\{ {\begin{array}{*{20}l} {2^{k - 1 - m} } & {when\; 0 \le m < k} \\ 0 &{ m \ge k} \\ \end{array} } \right. \\ \Rightarrow S_{\alpha } & = 1 + \mathop \sum \limits_{m = 0}^{k} \alpha_{m} \zeta_{m} = 1 + \alpha_{0} \zeta_{0} + \alpha_{1} \zeta_{1} + \ldots + \alpha_{k - 1} \zeta_{k - 1} + \alpha_{k} \zeta_{k} \\ \Rightarrow S_{\alpha } & = 1 + 2^{k - 1} \left( {\frac{{3^{0} + 1}}{2}} \right) + 2^{k - 2} \left( {\frac{{3^{1} + 1}}{2}} \right) + \ldots + 2^{k - 1 - k - 1} \left( {\frac{{3^{k - 1} + 1}}{2}} \right) + 0.\left( {\frac{{3^{k} + 1}}{2}} \right) = \zeta_{k} \\ \end{aligned} $$

Hence, the proof is complete. □

Theorem 2.4

If \( 0 < \alpha < \beta < \gamma \)then\( 2S_{\beta } \ne S_{\alpha } + S_{\gamma } \) for all\( \alpha ,\beta ,\gamma \in {\mathbb{N}} \).

Proof

Since, \( 0 < \alpha < \beta < \gamma \), and let \( k \) is any positive integer, then the following cases arise:

  • Case 1 When \( \beta = 2^{k} \), \( \alpha \) and \( \gamma \) may have any value.

    Since \( \beta = 2^{k} \), we have from Lemma 2.3, \( S_{\beta } = \zeta_{k}\, \forall \, k \ge 0 \), and also \( \beta < \gamma \Rightarrow \gamma \ge 2^{k} + 1 \)

    $$ \begin{aligned} \Rightarrow \gamma_{m} \ge \left\lfloor\frac{{2^{k} + 1 + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor = \left\lfloor 2^{k - m - 1} + \frac{1}{2}\right\rfloor = \left\{ {\begin{array}{*{20}l} {2^{k - 1 - m} } \hfill & {when 0 \le m < k} \hfill \\ 1 \hfill & {m = k} \hfill \\ 0 \hfill & {otherwise} \hfill \\ \end{array} } \right. \hfill \\ {\text{and}}\,\beta_{m} = \left\lfloor\frac{{2^{k} + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor = \left\lfloor 2^{k - m - 1} + \frac{1}{2} - \frac{1}{{2^{m + 1} }}\right\rfloor = \left\{ {\begin{array}{*{20}l} {2^{k - 1 - m} } & {when \;0 \le m < k} \\ 0 & {m = k} \\ \end{array} } \right. \hfill \\ \Rightarrow S_{\gamma } = 1 + \mathop \sum \limits_{m = 0}^{k} \gamma_{m} \zeta_{m} \ge 1 + \mathop \sum \limits_{m = 0}^{k - 1} 2^{k - 1 - m} \zeta_{m} + \zeta_{k} \ge 1 + \mathop \sum \limits_{m = 0}^{k} \beta_{m} \zeta_{m} + \zeta_{k} = 2S_{\beta } \hfill \\ \Rightarrow S_{\gamma } + S_{\alpha } > 2S_{\beta } \,{\text{and}}\,{\text{so}}\,2S_{\beta } \ne S_{\alpha } + S_{\gamma } \hfill \\ \end{aligned} $$

  • Case 2 When \( \beta = 2^{k} + 1 \) and

    • Sub-case 2.1\( \gamma \le 2^{k + 1} \) and \( \alpha \) may have any value

      Since \( \beta = 2^{k} + 1 \), \( \gamma \le 2^{k + 1} \) and \( \alpha \) may have any value

      $$ \begin{aligned} \Rightarrow \beta_{m} = \left\lfloor\frac{{2^{k} + 1 + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor = \left\lfloor 2^{k - m - 1} + \frac{1}{2}\right\rfloor = \left\{ {\begin{array}{*{20}l} {2^{k - 1 - m} } & {when \; 0 \le m < k} \\ 1 & {m = k} \\ \end{array} } \right. \hfill \\ {\text{and}}\,\gamma_{m} \le \left\lfloor \frac{{2^{k + 1} + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor = \left\lfloor 2^{k - m} + \frac{1}{2} - \frac{1}{{2^{m + 1} }}\right\rfloor = \left\{ {\begin{array}{*{20}l} {2^{k - m} } & {when \; 0 \le m \le k} \\ 0 & {m = k + 1} \\ \end{array} } \right. \hfill \\ \end{aligned} $$

      we have, \( S_{\gamma } = 1 + \mathop \sum \limits_{m = 0}^{k + 1} \gamma_{m} \zeta_{m} \le 1 + \mathop \sum \limits_{m = 0}^{k} 2^{k - m} \zeta_{m} = 1 + 2\mathop \sum \limits_{m = 0}^{k} 2^{k - 1 - m} \zeta_{m} \)

      $$ \begin{aligned} \Rightarrow S_{\gamma } \le 1 + 2\mathop \sum \limits_{m = 0}^{k - 1} 2^{k - 1 - m} \zeta_{m} + \zeta_{k} \hfill \\ \Rightarrow S_{\gamma } \le 1 + 2\mathop \sum \limits_{m = 0}^{k} \beta_{m} \zeta_{m} - 2\beta_{k} \zeta_{k} + \zeta_{k} = 2S_{\beta } - 1 - \zeta_{k} \hfill \\ \Rightarrow S_{\gamma } + 1 + \zeta_{k} \le 2S_{\beta } \hfill \\ \end{aligned} $$
      (2.1)

      since \( \alpha < \beta = 2^{k} + 1 \Rightarrow \alpha \le 2^{k} \Rightarrow S_{\alpha } \le \zeta_{k} \) [\( \because \) of Lemma 2.3]

      we have from (2.1), \( S_{\gamma } + 1 + S_{\alpha } \le S_{\gamma } + 1 + \zeta_{k} \le 2S_{\beta } \Rightarrow S_{\gamma } + S_{\alpha } < 2S_{\beta } \Rightarrow 2S_{\beta } \ne S_{\alpha } + S_{\gamma } \).

    • Sub-case 2.2\( \gamma > 2^{k + 1} \) and \( \alpha \) may have any value

      Since \( \gamma > 2^{k + 1} \Rightarrow \gamma \ge 2^{k + 1} + 1 \)

      $$ \Rightarrow \gamma_{m} > \left\lfloor \frac{{2^{k + 1} + 1 + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor = \left\lfloor 2^{k - m} + \frac{1}{2}\right\rfloor = \left\{ {\begin{array}{*{20}l} {2^{k - m} } \hfill & {when \;0 \le m \le k} \hfill \\ 1 \hfill & {m = k + 1} \hfill \\ 0 \hfill & {otherwise} \hfill \\ \end{array} } \right. $$

      and \( \beta _{m} = \left\{ {\begin{array}{*{20}l} {2^{{k - 1 - m}} } & {when\,0\, \le m < k} \\ 1 & {m = k} \\ \end{array} } \right. \)

      now, \( S_{\gamma } = 1 + \mathop \sum \limits_{m = 0}^{k + 1} \gamma_{m} \zeta_{m} > 1 + \mathop \sum \limits_{m = 0}^{k} 2^{k - m} \zeta_{m} + \zeta_{k + 1} \)

      $$ \begin{aligned} \Rightarrow S_{\gamma } > 1 + 2\mathop \sum \limits_{m = 0}^{k} 2^{k - 1 - m} \zeta_{m} + \zeta_{k + 1} = 1 + 2\mathop \sum \limits_{m = 0}^{k - 1} 2^{k - 1 - m} \zeta_{m} + 2.2^{k - 1 - k} \zeta_{k} + \zeta_{k + 1} \hfill \\ \Rightarrow S_{\gamma } > 1 + 2\mathop \sum \limits_{m = 0}^{k - 1} \beta_{m} \zeta_{m} + \zeta_{k} + \zeta_{k + 1} = 1 + 2\mathop \sum \limits_{m = 0}^{k} \beta_{m} \zeta_{m} - 2\beta_{k} \zeta_{k} + \zeta_{k} + \zeta_{k + 1} \hfill \\ \Rightarrow S_{\gamma } > 2S_{\beta } - 1 - \zeta_{k} + \zeta_{k + 1} = 2S_{\beta } - 1 - \frac{{3^{k} + 1}}{2} + \frac{{3^{k + 1} + 1}}{2} = 2S_{\beta } - 1 + 3^{k} > 2S_{\beta } \hfill \\ \Rightarrow S_{\gamma } > 2S_{\beta } \Rightarrow S_{\gamma } + S_{\alpha } > 2S_{\beta } \Rightarrow 2S_{\beta } \ne S_{\alpha } + S_{\gamma } \hfill \\ \end{aligned} $$

  • Case 3. When \( 2^{k} + 1 < \beta < 2^{k + 1} \)

    • Sub-case 3.1\( \gamma > 2^{k + 1} \) and \( \alpha \) may have any value

      since \( 2^{k} + 1 < \beta < 2^{k + 1} \), \( 2^{k + 1} < \gamma \) and \( \alpha < \beta \Rightarrow \)\( \gamma \ge 2^{k + 1} + 1 \)\( \Rightarrow \gamma_{m} \ge \left\lfloor \frac{{2^{k + 1} + 1 + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor = \left\lfloor 2^{k - m} + \frac{1}{2}\right\rfloor = \left\{ {\begin{array}{*{20}l} {2^{k - m} } \hfill & {when\; 0 \le m \le k} \hfill \\ 1 \hfill & {m = k + 1 } \hfill \\ 0 \hfill & {otherwise } \hfill \\ \end{array} } \right. \)

      and, \( \beta_{m} < \left\lfloor \frac{{2^{k + 1} + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor = \left\lfloor 2^{k - m} + \frac{1}{2} - \frac{1}{{2^{m + 1} }}\right\rfloor = \left\{ {\begin{array}{*{20}l} {2^{k - m} } & {when \;0 \le m \le k} \\ 0 & {m = k + 1} \\ \end{array} } \right. \)

      we have, \( S_{\gamma } = 1 + \mathop \sum \limits_{m = 0}^{k + 1} \gamma_{m} \zeta_{m} = 1 + \mathop \sum \limits_{m = 0}^{k} \gamma_{m} \zeta_{m} + \gamma_{k + 1} \zeta_{k + 1} > 1 + \mathop \sum \limits_{m = 0}^{k} 2^{k - m} \zeta_{m} + \zeta_{k + 1} \)\( \begin{aligned} \Rightarrow S_{\gamma } > 1 + \mathop \sum \limits_{m = 0}^{k} 2^{k - m} \zeta_{m} + {\text{S}}_{{2^{k + 1} }} [\because \,{\text{of}}\,{\text{Lemma}}\, 2. 3 ,\,\zeta_{k + 1} = S_{{2^{k + 1} }} ] \hfill \\ \Rightarrow S_{\gamma } > 1 + \mathop \sum \limits_{m = 0}^{k} \beta_{m} \zeta_{m} + S_{{2^{k + 1} }} > S_{\beta } + S_{\beta } [\because \,{\text{of}}\,{\text{Lemma}}\, 2. 2] \hfill \\ \Rightarrow S_{\gamma } > 2S_{\beta } \Rightarrow S_{\gamma } + S_{\alpha } > 2S_{\beta } \Rightarrow 2S_{\beta } \ne S_{\alpha } + S_{\gamma } \hfill \\ \end{aligned} \)

    • Sub-case 3.2\( \gamma \le 2^{k + 1} \) and \( \alpha \) may have any value

      since \( 2^{k} + 1 < \beta < 2^{k + 1} \), \( \gamma \le 2^{k + 1} \) and \( \alpha < \beta \)

      $$ \begin{aligned} \Rightarrow \gamma_{m} & \le \left\lfloor\frac{{2^{k + 1} + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor = \left\lfloor 2^{k - m} + \frac{1}{2} - \frac{1}{{2^{m + 1} }}\right\rfloor = \left\{ {\begin{array}{*{20}l} {2^{k - m} } & {when \; 0 \le m \le k} \\ 0 & {m = k + 1} \\ \end{array} } \right. \\ {\text{and}}\,\beta_{m} & \ge 2^{k} + 2 = \left\lfloor \frac{{2^{k} + 2 + 2^{m} - 1}}{{2^{m + 1} }}\right\rfloor = \left\lfloor 2^{k - m - 1} + \frac{1}{2} + \frac{1}{{2^{m + 1} }}\right\rfloor = \left\{ {\begin{array}{*{20}l} {2^{k - 1} + 1} \hfill & {when\; m = 0} \hfill \\ {2^{{k - 1 - {\text{m}}}} } \hfill & {0 < m \le k - 1} \hfill \\ 1 \hfill & {when \; m = k} \hfill \\ \end{array} } \right. \\ \end{aligned} $$

      now,

      $$ \begin{aligned} S_{\gamma } = 1 + \mathop \sum \limits_{m = 0}^{k + 1} \gamma_{m} \zeta_{m} = 1 + \gamma_{0} \zeta_{0} + \mathop \sum \limits_{m = 1}^{k - 1} \gamma_{m} \zeta_{m} + \gamma_{k} \zeta_{\text{k}} + \gamma_{k + 1} \zeta_{k + 1} < 1 + \mathop \sum \limits_{m = 0}^{k - 1} 2^{k - m} \zeta_{m} + \zeta_{k} \hfill \\ \Rightarrow S_{\gamma } < 1 + 2\mathop \sum \limits_{m = 0}^{k - 1} 2^{k - 1 - m} \zeta_{m} + \zeta_{k} < 1 + 2\mathop \sum \limits_{m = 0}^{k} \beta_{m} \zeta_{m} - 2\beta_{k} \zeta_{k} + \zeta_{k} \hfill \\ \Rightarrow S_{\gamma } + S_{\alpha } < 2S_{\beta } \hfill \\ \end{aligned} $$

Therefore, for all the cases \( S_{\gamma } + S_{\alpha } \ne 2S_{\beta } \). Hence, the proof is complete. □

Theorem 2.5

The exponent matrix\( E \)is corresponded to a QC-LDPC code with girth at least 8 and with CPM size\( q \ge 2S_{L} - 1 \).

Proof

To prove that the corresponding codes are of girth at least 8, firstly we have to prove that there is no 4-cycle. For this, if possible, let us suppose there is a 4-cycle present in ath and bth rows and cth and dth columns. So by Theorem 2.1 of [3], we have

$$ \begin{aligned} \left( {e_{ac} - e_{bc} } \right) + \left( {e_{bd} - e_{ad} } \right) \equiv 0\left( {mod q} \right) \hfill \\ \Rightarrow \left( {\left( {a - 1} \right)\left( {S_{c} - 1} \right) - \left( {b - 1} \right)\left( {S_{c} - 1} \right)} \right) + \left( {\left( {b - 1} \right)\left( {S_{d} - 1} \right) - \left( {a - 1} \right)\left( {S_{d} - 1} \right)} \right) \equiv 0\left( {mod q} \right) \hfill \\ \Rightarrow \left( {S_{c} - 1} \right)\left( {a - b} \right) - \left( {S_{d} - 1} \right)\left( {a - b} \right) \equiv 0\left( {mod q} \right)\, \Rightarrow \left( {a - b} \right)\left( {S_{c} - S_{d} } \right) \equiv 0\left( {mod q} \right) \hfill \\ {\text{since}},\,q \ge 2S_{L} - 1,\,1 \le a < b \le 3\,{\text{and}}\,1 \le c < d \le L \hfill \\ \Rightarrow 1 \le S_{c} < S_{d} \le S_{L} [\because \,{\text{of}}\,{\text{Lemma}}\, 2. 2 ]\hfill \\ \end{aligned} $$

also \( 0 < \left( {{\text{a}} - {\text{b}}} \right)\left( {{\text{S}}_{\text{c}} - {\text{S}}_{\text{d}} } \right) = \left( {{\text{b}} - {\text{a}}} \right)\left( {{\text{S}}_{\text{d}} - {\text{S}}_{\text{c}} } \right) < 2\left( {{\text{S}}_{\text{L}} - 1} \right) < q \) therefore, \( \left( {a - b} \right)\left( {S_{c} - S_{d} } \right) \equiv 0\left( {mod q} \right) \) becomes a simple equation i.e. \( \left( {a - b} \right)\left( {S_{c} - S_{d} } \right) = 0 \) and so, we have \( a = b \) or \( S_{c} = S_{d} \), which is not possible. Therefore, there is no 4-cycle present in QC-LDPC codes corresponding to exponent matrix \( E \). □

Now, we will prove that there is no 6-cycle present in the corresponding QC-LDPC codes. If possible, suppose there is a 6-cycle present in 1st, 2nd and 3rd rows and dth, eth and fth columns. So again, by Theorem 2.1 of [3], we have

$$ \begin{aligned} \left( {e_{1d} - e_{3d} } \right) + \left( {e_{3e} - e_{2e} } \right) + \left( {e_{2f} - e_{1f} } \right) & \equiv 0\left( {mod q} \right) \\ \left( {e_{1d} - e_{3d} } \right) + \left( {e_{3f} - e_{2f} } \right) + \left( {e_{2e} - e_{1e} } \right) & \equiv 0\left( {mod q} \right) \\ \left( {e_{2d} - e_{3d} } \right) + \left( {e_{3f} - e_{1f} } \right) + \left( {e_{1e} - e_{2e} } \right) & \equiv 0\left( {mod q} \right) \\ \left( {e_{1d} - e_{2d} } \right) + \left( {e_{2e} - e_{3e} } \right) + \left( {e_{3f} - e_{1f} } \right) & \equiv 0\left( {mod q} \right) \\ \left( {e_{2d} - e_{3d} } \right) + \left( {e_{3e} - e_{1e} } \right) + \left( {e_{1f} - e_{2f} } \right) & \equiv 0\left( {mod q} \right) \\ \left( {e_{1d} - e_{2d} } \right) + \left( {e_{2f} - e_{3f} } \right) + \left( {e_{3e} - e_{1e} } \right) & \equiv 0\left( {mod q} \right) \\ \end{aligned} $$

substitute the values of \( e_{ij} \) for different values of \( i \) and \( j \), and after some simple calculations, we get

$$ S_{e} + S_{f} \equiv 2S_{d} \left( {mod q} \right) $$
(2.2)
$$ S_{f} + S_{e} \equiv 2S_{d} \left( {mod q} \right) $$
(2.3)
$$ 2S_{f} \equiv \left( {S_{d} + S_{e} } \right)\left( {mod q} \right) $$
(2.4)
$$ 2S_{f} \equiv \left( {S_{d} + S_{e} } \right)\left( {mod q} \right) $$
(2.5)
$$ 2S_{e} \equiv \left( {S_{d} + S_{f} } \right)\left( {mod q} \right) $$
(2.6)
$$ 2S_{e} \equiv \left( {S_{d} + S_{f} } \right)\left( {mod q} \right) $$
(2.7)

From Eqs. (2.2) and (2.3), we have

$$ S_{e} + S_{f} \equiv 2S_{d} \left( {mod q} \right) $$

since \( {\text{d}} < e < f \le L \Rightarrow {\text{S}}_{\text{d}} < {\text{S}}_{\text{e}} < {\text{S}}_{\text{f}} \le {\text{S}}_{\text{L}} \Rightarrow S_{e} + S_{f} \le S_{L} - 1 + S_{L} \le q \) and also \( 2S_{d} < q \) hence, both the sides of Eqs. (2.2) and (2.3), are less than \( q \) so that the equations can be written as a simple equation, i.e., \( S_{e} + S_{f} = 2S_{d} < S_{e} + S_{d} \Rightarrow S_{f} < S_{d} \), which contradicts the Lemma 2.2. Similarly, the remaining four equations also become simple equations. Now, from Eqs. (2.4) and (2.5), we have \( 2S_{f} = S_{d} + S_{e} < S_{e} + S_{e} \Rightarrow 2S_{f} < 2S_{e} \Rightarrow S_{f} < S_{e} \) which is not possible, because \( S_{d} < S_{e} < S_{f} \). Similarly, from Eqs. (2.6) and (2.7), we have \( 2S_{e} = S_{d} + S_{f} \) where, \( {\text{d}} < e < f \), which contradicts the Theorem 2.4 and so, \( 2S_{e} \ne S_{d} + S_{f} \). Hence, all the six equations are not satisfied, which contradicts our supposition that there exists a 6-cycle.

Therefore, QC-LDPC codes corresponded by exponent matrix E are free from 4-cycles, and 6-cycles. Moreover, it is also make cleared from the above theorem that the proposed codes satisfy the tightest lower bound \( q \ge 2S_{L} - 1 \) on the minimum CPM size \( q \), and hence are of the smallest size in literature. To validate our claim, we compare the minimum CPM size of our proposed girth-8 QC-LDPC codes with the ones in [18] (see Table 1).

Table 1 Comparison on the minimum CPM size \( \varvec{q} \) of the proposed (3,L)-QC-LDPC codes with the codes given by [18] for girth at least 8 and for \( 26 \le \varvec{L} \le 40 \)
Full size table

3 Conclusion

A new and simple method to construct the exponent matrix for a QC-LDPC code is given in this paper. The method is capable of constructing the exponent matrix of order \( 3 \times L \), for any value of \( L > 3 \), by using the column multipliers. For the proposed method, a lower bound on the minimum CPM size \( q \) is given, which is the tightest lower bound in literature. Moreover, all the constructed QC-LDPC codes by the proposed method are optimal to the given bound. Most of the constructed codes are of the smallest CPM size in comparison with existing codes based on algebraic constructions.