On the Burst Erasure Efficiency of Array LDPC Codes

Abstract

In this paper a family of LDPC codes based on the shortened and superposed array LDPC codes is proposed for burst erasure channels. The design of constructions is based on identifying and analyzing cycles corresponding to consecutive columns in parity check matrices. The burst erasure capability of the codes, represented by $L_{max}$, can be determined by finding such cycles. Our constructions are categorized into four classes that one of them is a burstMDS code with efficiency equal to 1. By considering a single burst erasure-correcting over burst erasure channels, the simulation results show that our constructed codes can be competed with well-known LDPC codes in comparable rates, lengths and efficiencies.

1 Introduction and Background

1.1 Introduction

Low-density parity-check (LDPC) codes introduced by Gallager are near-capacity approaching codes under iterative message-passing decoding algorithms [1]. Most of researches have been done on these codes over the AWGN channels [1, 2]. However, recently, different methods of constructing LDPC codes have focused on the performance of these codes over the burst erasure channels  [3, 4].

Some combinatorial properties of LDPC codes, such as stopping sets, can significantly affect their decoding over erasure and burst erasure channels, [5–7]. This implies that LDPC codes with appropriate combinatorial parameters should be designed to overcome burst erasures. In such a channel, the longest decodable burst erasure by an iterative decoding algorithm is called a reasonable maximum burst erasure length, $L_{max}$ [8]. In other words, the iterative decoding algorithm can correct a burst erasure completely when the length of the burst is equal to or smaller than $L_{max}$.

There are several methods that have investigated correcting single burst erasure for LDPC codes  [3, 4, 8–10]. Some start from a parity-check matrix of a LDPC code and permute some columns of it to find an optimized parity-check matrix with a good $L_{max}$ and same rate over the erasure channels  [11].

Yang and Ryan [8, 12], found $L_{max}$ by developing an efficient exhaustive search algorithm which is guaranteed to correct the longest burst associated with LDPC code. Moreover in [13] a pseudo random method for constructing parity-check matrices with large $L_{max}$ is presented. In [14], a class of the product codes based on LDPC constituent codes has been introduced for multiple phased-burst erasure correction (MPBEC) such that these codes can correct one large burst and/or a number of shorter bursts.

In [5], some constructing methods of LDPC codes for correcting burst erasures are proposed. These methods are based on the size of the stopping sets of the base matrices and choosing the appropriate permutation matrices for superposing. The results are used to design both single and multiple burst erasure-correcting LDPC codes. Array LDPC codes (Array codes) are well-structured quasi-cyclic LDPC codes [15]. Their performance over the AWGN channels has been the subject of many papers [16, 17]. Some combinatorial properties such as girth, stopping sets, trapping sets and absorbing sets have been investigated in [2, 4, 6, 16, 18–20].

In this paper, LDPC codes have been derived from shortened array codes and superposition of shortened array codes. By superposing (particular products) of the various shortened array codes, four constructions of LDPC codes with the capability of correcting a single burst of erasures have been constructed. One of the constructed LDPC codes is the burstMDS code with efficiency 1.

The other types of constructed LDPC codes have a high efficiency, good, and acceptable $L_{max}$ compared to LDPC codes in [5]. The main contribution of this paper is finding and analyzing cycles corresponding to consecutive columns in parity check matrices of the constructed codes. By finding such cycles, the value of $L_{max}$ can be determined.

The rest of the paper is organized as follows: In Sect. 1.2, the necessary background, definitions and notations are provided. Section 2 is devoted to the main lemma for finding a special cycle in a parity check matrix and the product operations. In Sect. 3, we introduce four proposed constructions based on the definitions given in Sect. 2 and also in this section their important parameters over burst erasure channels are described. Simulation results are provided in Sect. 4 and, finally, the conclusion is presented in Sect. 5.

1.2 Background

A binary erasure channel is the simplest model for memoryless erasure channels where a transmitted bit is either correctly received or erased. There are two basic types of binary erasure channels, namely random and burst. In a random binary erasure channel, erasures occur at random locations, each with the same probability of occurrence, whereas over a binary burst erasure channel, erasures cluster into bursts. Indeed, if the memoryless erasure channel is considered as a model of packet-based transmission, then a burst erasure can occur for this type of transmission (e.g. wireless transmission).

In [21], the classical case for burst erasure channel has been defined with two states: burst space and guard space. In the burst space, the channel output carries no information about the inputs in the guard space, either the outputs are erasure free or are randomly corrupted with erasure probability p. In this paper, both states of the channel are considered for simulating the proposed codes.

Definition 1

An LDPC code with parity-check matrix $H(m,q)$

$$\begin{aligned} H(m,q)=\left[ \begin{array}{ccccc} I &{} I &{} I &{} \cdots &{} I \\ I &{} P &{} P^{2} &{} \cdots &{} P^{q-1} \\ \vdots &{} \vdots &{} \vdots &{} \ddots &{} \vdots \\ I &{} P^{m-1} &{} P^{2(m-1)} &{} \cdots &{} P^{(q-1)(m-1)} \\ \end{array} \right] \end{aligned}$$

(1)

is known as an array code [16] where $q$ is an odd prime number and $m$ is an integer number between $1$ and $q$. In (1), $I=I_q$ denotes the $q \times q$ identity matrix, and $P^i, i \ge 0$ is a $q \times q$ circulant permutation matrix obtained from $I_q$ by cyclically shifting its rows i positions to the left. We set $P^1=P$ and $P^0=I$ and $H(m,q)$ may be considered as an $m\times q$ matrix, with $q \times q$ circulant permutation matrices as its entries. In this case, each of the m rows (q columns) of $H(m,q)$ is referred to as a block-row (block-column).

Definition 2

$H(m, q, \theta )$ is defined as a shortened array code with a parity-check matrix containing the first $\theta$ block-columns of $H(m,q)$, where $m\,<\,\theta \,\le \,q$. Hence the length of the associated code is $\theta q$.

Definition 3

A set of columns in a parity check matrix is said to form a cycle, if the associated Tanner graph contains a cycle and the column and row weight of the associated regular sub-matrix be 2.

There is a relationship between the above definition of cycles and stopping sets concept. In Tian et al. [22], proved that every stopping set contains at least one cycle. A bipartite graph without singly connected variable nodes called a stopping set.

Definition 4

A maximum distance separable code (MDS code) is an achievable code that satisfies the relation $d\,=\,n-k+1$ where d, n and k are minimum distance, length and dimension of the code, respectively.

Definition 5

A BurstMDS code corrects bursts of erasures with combined length of $n-k$ bits [5].

In this paper, it is proved that shortened binary array codes with parity-check matrices $H(2,q,\theta ), m\,<\,\theta \,\le \,q$, are burstMDS codes.

Another required parameter of a code is efficiency [5] which depends on the maximum resolvable erasure burst length $L_{max}$, and that is

$$\begin{aligned} \eta =\frac{L_{max}}{n-k}. \end{aligned}$$

The efficiency $\eta$ is a parameter between 0 and 1. Therefore, in single burst erasure-correcting codes, a burstMDS code achieves the maximum efficiency if $L_{max}$ is equal to $n - k$.

2 Main Lemma and Product Operations

The main lemma for finding a special cycle in a parity check matrix and the definition of product operations between two parity check matrices are given in this section.

Lemma 1

In the parity-check matrix $H(2,q)$ of an array code, columns in every two consecutive block-columns k and $(k+1), 1 \le k < q$, form a cycle of length $4q$.

Proof

Let the rows of $H(2,q)$ be indexed from 1 to $2q$ and the columns in every block-column be indexed from 1 to q. In a permutation matrix, each left cyclic shift is equivalent to a down cyclical shift, then in $H(2,q)$ the $t$th column of the kth block-column has intersection with the tth row and the $q+1+<t+k-2>_q$th row, where $<\cdot >_q$ is the remainder modulo $q, 1 \le t \le q$. Moreover, $H(2,q)$ is 4-cycle free.

To show that the columns in block-columns k and $(k+1)$ form a cycle, we start from an arbitrary column in block-columns k or $(k+1)$ and after going through all the other columns in these two block-columns, we return to the starting column. We start from the tth column, $1\,\le \,t\,\le \,q$, of the kth block-column. This column intersects with the tth row. The tth row intersects with the tth column of the $(k+1)$th block-column and this column intersects with the $q+1 + <t+(k+1)-2>_q$th row. It should also be noted that the $<t>_q +1$th column of the block-column k intersects with $q + 1+ < t+(k+1)-2>_q$th row. Similarly, $<t>_q+1$th row intersects with $<t>_q +1$th column of both block-columns k and $(k+1)$. The $<t>_q +1$th column of the $(k+1)$th block-column intersects with the $q+1+<(t+1)+(k+1)-2>_q$th row and so on.

According to the above sequence of incidences, it can easily be seen that at first the tth column of both block-columns are added to the path, then the $<t>_q+1$th columns of both block-columns of both block-columns are added to the path and then the $<t+1>_q+1$ columns of both block-columns are added to the path and so on. Since t was arbitrary value, by an inductive method it can be concluded that this procedure will continue until the $<t+q-1>_q+1$th column is reached which is the beginning column t. Therefore, all $2q$ columns of both block-columns k and $(k+1)$ form a cycle of length $4q$. $\square$

Example 1

In $H(2,3)$, columns in the first and second block-columns, form a cycle of length $4q\,=\,12$. This cycle is shown in Fig. 1.

Fig. 1

A cycle of length 12 formed by columns in the first and second block-columns in parity-check matrix H(2,3)

Remark 1

Lemma 1 can be simply proved for any selected block-columns i and j where $1 \le i<j \le q$. In the first step and by starting the cycle from a block-column i, for an arbitrary $t, 1 \le t \le q$, two columns t and $<t+l-1>_q +1$ of two block-columns i and j, where $l\,=\,j-i$ are added to the path. Then, the $<t+2l-1>_q +1$th column of each of these block-columns is added and so on. Since q is an odd prime number, for each c where $1 \le c \le q-1$, the numbers $<t+cl-1>_q +1$ are distinct integer numbers belong to $\{1,\cdots , q\}$. Thus, after passing through all pairs of columns we return to the tth column. Therefore, there is a cycle of length $4q$.

Definition 6

A product operation $\bar{\odot }$ between two parity-check matrices $H(2,q,\theta )$ and $H(2,q',\theta )$ where $q\, {\text{and}}\, q'$ are odd prime numbers is defined as follows:

(2)

This shows that each sub-matrix $A_i$ for $1 \le i \le \theta , 3 \le \theta \le \min \{q,q' \}$ is obtained by replacing the nonzero entries of each block-column i of $H(2,q,\theta )$ from rows 1 to q with $I:=I_{q'}$, from rows $q+1$ to $2q$ with $P^{i-1}:=P^{i-1}_{q'}$ and the zeros with $q'\times q'$ zero matrices. In each sub-matrix $A_i, S_{ij}$ represents the jth block-column in sub-matrix $A_i, 1 \le i\le \theta$ and $1\le j\le q$.

Remark 2

If $q\,=\,q'$, then we use notation $H^{2}(2,q,\theta )$ instead of product $H(2,q,\theta )\bar{\odot }H(2,q,\theta )$.

Definition 7

A product operation $\underline{\odot }$ between two parity-check matrices $H(2,q,\theta )$ and $H(q,q',\theta )$, where $q\, {\text{and}}\, q'$ are odd prime numbers, $3 \le \theta \le \min \{q,q' \}$ and $q < q'$ is defined as follows:

where each sub-matrix $A_i, 1 \le i \le \theta$, is obtained by replacing the nonzero entries of each block-column i of $H(2,q,\theta )$ from rows 1 to q with $I:=I_{q'}$ and by replacing the nonzero entries of $q + k$th row, $1 \le k \le q$, with $P^{k(i-1)}:=P^{k(i-1)}_{q'}$. Moreover, replacing all zeros of block-column i will be substituted with $q'\times q'$, all zero matrices. In each sub-matrix $A_i, S_{ij}$ represents the $j$th block-column in sub-matrix $A_i, 1 \le i\le \theta$ and $1 \le j\le q$ (Eq. (3) verifies definition 7).

(3)

3 Constructions

Based on the two previous definitions, the following four types of QC-LDPC codes are constructed:

• type-$I, H(2,q,\theta )$ (shortened array codes);

• type-$II, H^{2}(2,q,\theta )$;

• type-$III, H(2,q,\theta )\bar{\odot }H(2,q',\theta )$;

• type-$IV, H(2,q,\theta )\underline{\odot }H(q,q',\theta )$.

Some properties of the constructed codes such as $L_{max}$, efficiency $\eta$ and rate $R$ have been analyzed.

3.1 Construction Type $I$ ($H(2,q,\theta )$)

Theorem 1

Let q be an odd prime number and $3 \le \theta \le q$. Then $L_{max}=2q-1$ for $H(2,q,\theta )$.

Proof

It is clear that two consecutive block-columns of length $2q$ form a cycle (and so a stopping set) in $H(2,q,\theta )$. So $2q-1$ is an upper bound for $L_{max}$. Therefore, it is sufficient to show that a burst erasure of length $2q-1$ can be corrected at any location of a received word, $\omega$, by iterative decoding. In general, two or three block-columns of $H(2,q,\theta )$ can be involved by such a burst erasure of length $2q-1$.

• a. If two block-columns $i$ and $(i+1), 1 \le i < \theta$, have been involved by the burst erasure, then either the first column of the $i$th block-column or the last column of the $(i+1)$th block-column has the correct value and the rest of bits in these two block-columns are erased. Hence according to Lemma 1, all the $2q-1$ erased bits will be corrected by iterative decoding.

• b. Suppose three consecutive block-columns $(i-1), i$ and $(i+1), 2 \le i \le \theta -1$, have been involved by the burst erasure. Suppose the bits in the last k columns of the $(i-1)$th block-column, the first l columns of the $(i+1)$th block-column and all the columns in the ith block-column are erased, where $1 \le k,l \le q-2$ such that $l+k=q-1$. It is easy to investigate that the $(l+1)$th, $(q+i-1)$th and $(q+i)$th rows have only one erased bit. This is because the bits corresponding to the $(l+1)$th column of each of the $(i-1)$th and $(i+1)$th block-columns is out of the burst range.

  Moreover, the bits corresponding to the first two columns of the $(i-1)$th block-column and to the last two columns of the $(i+1)$th block-column are not within the burst range. Suppose the circulant matrices in each block-row are numbered from left to right. In the second block-row, the $(i+1)$th circulant matrix is obtained by cyclically left shifting the rows of the $(i-1)$th circulant matrix twice.

  Therefore, the nonzero elements in the first and second columns of the $(i-1)$th circulant matrix are located at the $(q-1)$th and $q$th column of the $(i+1)$th circulant matrix, respectively. Hence, the corresponding rows to these nonzero elements, i.e. the $(q+i-1)$th and $(q+i)$th rows, have only one erased bit in location i. In addition, the only row with 3 erased bits is: $q+1+<(l+2)+(i-1)-2>_q =q+1+<l+i-1>_q,$ since this row intersects with the $q-k+1(=l+2)$th column of the $(i-1)$th block-column, and the $(l+1)$th column of the ith block-column and also with the lth column of the $(i + 1)$th block-column. The correction process of the burst erasure can be carried out as follows:

  The erased bit associated to the $(l+1)$th column of the ith block-column will be corrected by the $(l+1)$th row. Note that this correction reduces the number of erased bits in the $q+1+<l+i-1>_q$th row from 3 to 2 and there is no row with degree greater than 2.

  The last k columns of block-column $(i-1)$ and their corresponding columns within the ith block-column are a part of the cycle formed by two block-columns $(i-1)$ and i. Therefore by starting from the erased variable node in the qth column of block-column i and correcting it by the $(q+i-1)$ row in the iterative decoding process, all other erased variable-nodes in this cycle will be corrected. Similarly, the corresponding erased variable-nodes to the first l columns of both block-columns i and $(i+1)$ will be corrected by starting from the first column of the ith block-column.

Thus a burst erasure of length $2q-1$ can be corrected at any location of the received word, which proves that $L_{max}=2q-1$. $\square$

Proposition 1

$rank(H(2,q,\theta ))=2q-1$ for $3 \le \theta \le q$.

Proof

As mentioned in [18], it follows simply by applying Gaussian elimination to find rank of matrix $H(2,q,\theta )$. $\square$

From Theorem 1 and Proposition 1 it can be concluded that the efficiency of a shortened array code with parity-check matrix $H(2,q,\theta ), 3 \le \theta \le q$, is $\eta =\displaystyle { \frac{L_{max}}{(n-k)}=\frac{L_{max}}{rank(H)} }=1$. Consequently, this family of codes are burstMDS codes. The rate of these codes depends on the values of q and $\theta$. That is

$$\begin{aligned} R=\displaystyle {\frac{k}{n}}=\displaystyle {\frac{q\theta -2q+1}{q\theta }}=1-\displaystyle {\frac{2q-1}{q\theta }}. \end{aligned}$$

3.2 Construction Type $II$ ( $H^{2}(2,q,\theta )$)

Lemma 2

In $H^{2}(2,q,\theta )$, the columns in two consecutive sub-matrices $A_i$ and $A_{i+1}, 1 \le i\le \theta -1$, form $q$ distinct cycles, each of length $4q$.

Proof

Let $A_i$ and $A_{i+1}, 1\le i\le \theta -1$, be two sub-matrices in Eq. (2). Note that an arbitrary column $t, 1 \le t\le q$, of block-column $S_{ij}, 1 \le j\le q$ intersect with the tth row of block-row j and $1+<t+i-2>_q$th row of the block-row $q+1+<j+i-2>_q$ in $H^{2}(2,q,\theta )$. Now, focussing on the tth column of the $S_{ij}$th block-column of $H^{2}(2,q,\theta )$, the tth row intersects with the tth column of the $S_{(i+1)j}$th block-column and the tth column intersects with the $1+<t+(i+1)-2>_q$th row of block-row $q+1+<j+(i+1)-2>_q$. Column $<t>_q+1$ of block-column $S_{i(<j>_q+1)}$ intersects with the $1+<(t+1)+i-2>_q$th row of the $q+1+<(j+1)+i-2>_q$th block-row. Similarly, the $<t>_q+1$th row intersects with the $<t>_q+1$th column of the $S_{i(<j>_q +1)}$th block-column and the $<t>_q+1$th row intersects with the $<t>_q+1$th column of the $S_{(i+1)(<j>_q+1)}$th block-column. The $<t>_q+1$th column of the $S_{(i+1)(<j>_q+1)}$th block-column intersects with the $q+1+<(t+1)+(i+1)-2>_q$th row and so on. According to the above sequence of incidences, it can be shown that at first the tth columns of both block-columns $S_{ij}$ and $S_{(i+1)j}$ are added to the path, then the $<t>_q+1$th columns of both block-columns $S_{i(<j>_q+1)}$ and $S_{(i+1)(<j>_q+1)}$ are added and subsequently the $<t+1>_q+1$ columns of both block-columns $S_{i(<j+1>_q+1)}$ and $S_{(i+1)(<j+1>_q+1)}$ are added to the path and so on. Since t and j were arbitrary values, it can be concluded by an inductive method that this procedure will continue until the $<t+q-1>_q+1$th column of the block-column $S_{i(<j+q-1>_q+1)}$ is reached, i.e. the beginning column t of the $S_{ij}$th block-column. Therefore, by starting from an arbitrary column t in any arbitrary block-column of $S_{ij}$, where $1 \le i\le \theta$ and $1\le j\le q$, and after passing from $2q$ columns, we return to the starting column, so a cycle of length $4q$ is formed (note that for $1 \le t\le q, 1 \le j\le q, t=<t+q-1>_q+1$ and $j=<j+q-1>_q+1$). If the next cycle starts from the $<t>_q +1$th column of the block-column $S_{ij}$, it is easy to see that a right shift of all columns in the previous cycle is included in the new cycle. That is to say in forming a new cycle, at first columns $<t>_q +1$ of both block-columns $S_{ij}$ and $S_{(i+1)j}$ are added to the cycle, then columns $<t+1>_q+1$ of both block-columns $S_{i(<j>_q+1)}$ and $S_{(i+1)(<j>_q+1)}$ are added and so on.

The same argument can be used by starting from every q column of block-column $S_{ij}$. Therefore q distinct cycles in two sub-matrices $A_i$ and $A_{i+1}$ will be obtained where each column in these two sub-matrices belongs to one and only one of these cycles. Thus in general case there exist q cycles of length $4q$. See Fig. 2. $\square$

Fig. 2

A graph representation of q cycles in two sub-matrices $A_i$ and $A_{i+1}$ each of length $4q$

Theorem 2

For a code with parity-check matrix $H^{2}(2,q,\theta ), L_{max}=2q^2-q-1$.

Proof

It is sufficient to show that a burst erasure of length $2q^2-q-1$ can be corrected at any location of the received word, $\omega$, by iterative decoding. From Lemma 2, columns of any two consecutive block-columns form q distinct cycles of length $4q$. In general, two or three sub-matrices of the parity-check matrix $H^{2}(2,q,\theta )$ can be involved by such burst erasures of length $2q^2-q-1$.

• a. Assume that only sub-matrices $A_i$ and $A_{i+1}$ have been involved by a burst erasure of length $2q^2-q-1$. In this case, either the $S_{i1}$th or the $S_{(i+1)q}$th block-column have no erased bits. Hence an entire block-column is not involved by the erasure bits and so there is a variable-node with a correct value in every q cycles that are constructed by columns in these two sub-matrices. Therefore the rest of the erased bits can be corrected by using iterative decoding. Otherwise, the last k columns of the $S_{i1}$th block-column, the first l columns of the $S_{(i+1)q}$th block-column, and all the columns in block-columns $S_{iz}$ for $2\le z \le q$ and block-columns $S_{(i+1)v}$ for $1\le v \le q-1$ are affected the erased bits in $\omega$ where $1 \le l,k \le q-1$ and $l+k=q-1$. It is clear that both of the first column of block-column $S_{i1}$ and the last column of block-column $S_{(i+1)q}$ belong to a cycle and their associated variable-nodes have correct values. The rest of the first $q-k$ columns of block-column $S_{i1}$ and the rest of the last $q-l$ columns of block-column $S_{(i+1)q}$ belong to one of the $q-1$ remaining cycles and then by iterative decoding and the above discussion, there is at least one variable-node with a correct value in each cycle and so all $2q^2-q-1$ erased bits can be corrected.

• b. Assume three sub-matrices $A_{i-1}, A_i$ and $A_{i+1}$ have been involved by a burst erasure of length $2q^2-q-1$ in $\omega$. Thus the first $\delta _1$ columns and the last $\delta _2$ columns of the sub-matrices $A_{i-1}$ and $A_{i+1}, q+2\le \delta _1, \delta _2 \le q^2-1$, are not erased. Consider the cycles of columns in two sub-matrices $A_{i-1}$ and $A_i$ and also the cycles of columns in two sub-matrices $A_i$ and $A_{i+1}$ simultaneously. It is known that each row is associated to a check node with 3 erased bits, which are at most $q-1$, connects to two erased variable-nodes in one cycle and connects to one erased variable-node in the second cycle. Therefore each variable-node with a correct value in the second cycle can reduce the number of erased bits of the mentioned rows to 2. Then, having a variable-node with a correct value in the first cycle can correct the two other erased bits of a row. It is easy to investigate whether each pair of cycles formed by columns of a sub-matrix $A_i$ and its left and right neighbour sub-matrices, intersect with one or two variable-nodes with erased values. In each case, with either one or two intersections, the number of variable nodes with correct values is at least one more than the number of erased bits in these pair of cycles. Consequently, all the erased bits in both cycles can be corrected.

Therefore, each burst erasure of length $2q^2-q-1$ can be corrected at any location of $\omega$. On the other hand, if two consecutive block-columns $A_i$ and $A_{i+1}$ are affected a burst erasure of length $2q^2-q$ and the starting column is column t in $A_i, t\ge 2$, then there exists a cycle in which all of its variable-nodes are erased and the $2q$ bits corresponding to this cycle can not be corrected. It is concluded that $L_{max}=2q^2-q-1$. $\square$

Proposition 2

$rank(H^{2}(2,q,\theta ))=2q^2-q$.

Proof

The proof can be simply concluded by using Gaussian elimination on $H^{2}(2,q,\theta )$. $\square$

By Theorem 2 and proposition 2, it can be concluded that the efficiency of the code with parity-check matrix $H^{2}(2,q,\theta )$ is equal to

$$\begin{aligned} \eta =\displaystyle {\frac{L_{max}}{(n-k)}=\frac{L_{max}}{rank(H)}=\frac{2q^2-q-1}{2q^2-q}}=\displaystyle {1- \frac{1}{2q^2-q} }. \end{aligned}$$

Also this code has also a very high efficiency and by increasing the value of q efficiency will become close to 1. The rate of the code can be changed by the values of q and $\theta$. That is $R=\displaystyle {\frac{q^2 \theta -2q^2+q}{q^2 \theta }= 1- \frac{2q^2-q}{q^2\theta }}.$

3.3 Construction Type $III$ ($H(2,q,\theta )\bar{\odot }H(2,q',\theta )$)

Lemma 3

In parity-check matrix

$$\begin{aligned} H(2,q,\theta )\bar{\odot }H(2,q',\theta ), \end{aligned}$$

where $q$ and $q'$ are distinct odd prime numbers and $3 \le \theta \le \min \{q,q'\}$, the columns in two consecutive sub-matrices $A_i$ and $A_{i+1}, 1 \le i\le \theta -1$, form a cycle of length $4qq'$.

Proof

Let $A_i$ and $A_{i+1}, 1 \le i\le \theta -1$ be two sub-matrices in $H(2,q,\theta )\bar{\odot }H(2,q',\theta )$ and the tth column of the $S_{ij}$th block-column is selected arbitrarily where $1 \le j\le q$. Note that column $t, 1 \le t\le q'$, of block-column $S_{ij}$ intersects with the tth row of block-row j and the $1+<t+i-2>_{q'}$th row of block-row $q+1+<j+i-2>_q$. Similar to Lemma 2, we can check that at first the tth columns of both block-columns $S_{ij}$ and $S_{(i+1)j}$ are added to the path. Then, the $<t>_{q'}+1$th columns of both block-columns $S_{i(<j>_q+1)}$ and $S_{(i+1)(<j>_q+1)}$ are added to the path. The $<t+1>_{q'} +1$th columns of both block-columns $S_{i(<j+1>_q+1)}$ and $S_{(i+1)(<j+1>_q+1)}$ are added next and so on. Since t and j were arbitrary values, then by induction it can be concluded that this procedure will continue until the $<t+q-1>_{q'}+1$th column of block-column $S_{i(<j+q-1>_q+1)}$ is reached. $j=<j+q-1>_q+1$, we return to the $<t+q-1>_{q'}+1$th column of the first block-column , i.e. $S_{ij}$th block-column, but not to the $t$th column. Therefore, if moving on the path is continued from the $<t+q-1>_{q'}+1$th column, then after adding the other $2q$ columns to the path, the $<t+2q-1>_{q'}+1$th column in $S_{ij}$th block-column will be available. As q and $q'$ are distinct odd prime numbers, after the $q'$ th iteration, which we are passing from the $S_{ij}$th block-column, we reach the $t=<t+qq'-1>_{q'}+1$th column of the $S_{ij}$th block-column, that is the tth column (starting column of the cycle) of the $S_{ij}$th block-column. Therefore a cycle of length $4qq'$ is formed. $\square$

Theorem 3

For a code with parity-check matrix $H(2,q,\theta )\bar{\odot }H(2,q',\theta )$, where $q$ and $q'$ are distinct odd prime numbers and $3 \le \theta \le \min \{ q,q' \}$, we have $L_{max}=2qq'-q'-1$.

Proof

It is sufficient to show that a burst erasure of length $2qq'-q'-1$ can be corrected at any location of the received word, $\omega$, by iterative decoding. Similar to the previous theorems and according to Lemma 3 and iterative decoding, if all columns of two sub-matrices $A_i$ and $A_{i+1}$ in matrix (2) except one are erased, then iterative decoding can correct all the erased bits($2qq'-1$ erased bits). Note that $H^2(2, q, \theta )$ can be considered as a special case of $H(2,q,\theta )\bar{\odot }H(2,q',\theta )$ where $q\,=\,q'$. Moreover, the length of each cycle associated to two consecutive block-columns in $H(2,q,\theta )\bar{\odot }H(2,q',\theta )$ is greater than $4q$ and q and $q'$ are co-prime. Hence by referring to the proof of Theorem  2 for $H^2(2,q, \theta )$ it is concluded that $L_{max}$ for $H(2,q,\theta )\bar{\odot }H(2,q',\theta )$ is at least $2qq'-q'-1$ (since the proof is based on length of cycles). Now it is shown that $L_{max}$ is equal to this lower bound. It is sufficient to show that a burst erasure of length $2qq'-q'$ can not be corrected. It is known that column $t, 1 \le t\le q'$, of block-column $S_{ij}, 1 \le j \le q$ and $1 \le i \le \theta$, intersects with the tth row of block-row j and with the $1+<t+i-2>_{q'}$th row of block-row $q+1+<s+i-2>_q$ of $H(2,q,\theta )\bar{\odot }H(2,q',\theta )$. We claim that if a burst erasure of length $2qq'-q'$ involves three sub-matrices $A_{i-1}, A_i$ and $A_{i+1}$ and column $t$ of block-column $S_{(i-1)j}$ is the start of the burst range, where $j,t >1$, then there is a cycle of length $8$ in the burst range. This cycle is as follows:

If we start from the tth column of the $S_{(i-1)j}$th block-column, then row t of block-row j intersects with the tth column of the $S_{ij}$th block-column and this column intersects with the $1+<t+i-2>_{q'}$th row of block-row $q+1+<j+i-2>_q$. Moreover, column $(t-1)$ of block-column $S_{(i+1)(j-1)}$ intersects with this row (the $1+<t+i-2>_{q'}$th row of block-row $q+1+<j+i-2>_q$) and this column intersects with the $(t-1)$th row of block-row$(j-1)$. The $(t-1)$th row of block-row $(j-1)$ intersects with the $(t-1)$th column of $S_{i(j-1)}$th block-column and this column has intersection with the $1+<(t-1)+i-2>_{q'}$th row of block-row $q+1+<(j-1)+i-2>_q$. Row $1+<t+(i-1)-2>_{q'}$, of block-row $q+1+<j+(i-1)-2>_q$ intersects with the tth column of the $S_{(i-1)j}$th block-column which is indeed the starting column. Since the length of the burst is $2qq'-q'$ and all of the mentioned columns are located within the burst range, therefore correction of these 4 bits is not possible by iterative decoding. Hence $L_{max}=2qq'-q'-1$. $\square$

Proposition 3

$rank(H(2,q,\theta )\bar{\odot }H(2,q',\theta ))=2qq'-1$.

Proof

The proof can be easily concluded by using Gaussian elimination. $\square$

By Theorem 3 and Proposition 3, it can be concluded that the efficiency of a code with parity-check matrix $H(2,q,\theta )\bar{\odot }H(2,q',\theta )$ is equal to

$$\begin{aligned} \eta =\displaystyle {\frac{L_{max}}{(n-k)}=\frac{L_{max}}{rank(H)}}=\displaystyle {\frac{2qq'-q'-1}{2qq'-1}=1-\frac{q'}{2qq'-1}}. \end{aligned}$$

The rate of the code is equal to $\displaystyle {R=\frac{\theta qq'-2qq'+1}{\theta qq'}=1-\frac{2qq'-1}{\theta qq' } }$ and can be changed by the different values of $q, q'$, and $\theta$ $(3 \le \theta \le \min \{q,q' \})$.

3.4 Construction Type $IV$ ($H(2,q,\theta )\underline{\odot }H(q,q',\theta )$)

Lemma 4

In parity-check matrix

$$\begin{aligned} H(2,q,\theta )\underline{\odot }H(q,q',\theta ) \end{aligned}$$

where $q$ and $q'$ are distinct odd prime numbers, $q' > q$ and $3 \le \theta \le q$, columns in two consecutive sub-matrices $A_i$ and $A_{i+1}, 1 \le i\le \theta -1$, form a cycle of length $4qq'$.

Proof

The proof is similar to the proof of Lemma 3. $\square$

The next theorem provides an upper and a lower bound for $L_{max}$ in parity-check matrix $H(2,q,\theta )\underline{\odot }H(q,q',\theta )$.

Theorem 4

Let $q$ and $q'$ be two odd prime numbers where $q' > q$. For a code with parity-check matrix $H(2,q,\theta )\underline{\odot }H(q,q',\theta )$, we have $2qq'-q'-1 \le L_{max} \le 2qq'-1$.

Proof

According to Lemma  4 if the columns of two sub-matrices $A_i$ and $A_{i+1}, 1 \le i\le \theta -1$, are considered, then a cycle of length $2qq'$is obtained. Thus $L_{max}$ can be at most $2qq'-1$. Similar to Theorem 3 it can be shown that each burst erasure of length $2qq'-q'-1$ is corrected and this value is a lower bound for $L_{max}$. Thus, both bounds for this code are obtained. $\square$

Proposition 4

$rank(H(2,q,\theta )\underline{\odot }H(q,q',\theta ))=2qq'-1$.

Proof

The proof can be easily concluded by using Gaussian elimination. $\square$

The rate of this code is $\displaystyle {R=1-\frac{2qq'-1}{\theta qq'}}$. Due to varying of $q, q'$ and $\theta$ in $H(2,q,\theta )\underline{\odot }H(q,q',\theta ), L_{max}$ of this matrix is not determined explicitly. The efficiency of this code is computed for some parameters in Table  1.

Table 1 Burst correction properties of proposed codes

4 Simulation Results

In [5] four code construction methods are introduced, so in Table 1 values of $q, q'$ and $\theta$, in the proposed codes, have been chosen to construct codes with lengths and rates near to the codes in  [5]. In addition, values of $L_{max}$ and efficiency $\eta =L_{max}/(n-k)$ have been computed. It can be seen that shortened array codes with parity-check matrix $H(2,q,\theta )$ and efficiency $1$ have better efficiency than other proposed structures in this paper. Moreover these codes compete with the codes in [5].

The implementation of proposed codes is conducted with lengths and rates similar to lengths and rates of the structured codes in [5], namely, near to the length 1500 and rate 4/5. Then the comparison of our proposed codes with the codes in [5] are presented in Figs. 3, 4, 5 and 6. Simulation results of our structures are marked by symbol filled circles. The curves present two cases; solid curves, when the probability of error for the guard band equals to $p=0$, and the dashed curves, for the case that the probability of error in the guard band is equal to $p\,=\,0.01$.

Fig. 3

The performance Comparison of shortened array code with parity-check matrix $H(2,151,10)$ of length 1510 and rate 0.80, and code in  [8] of length 1500 and rate 0.8 on an erasure channel with one randomly located burst erasure and guard band erasure probabilities $p\,=\,0$ (solid curves) and $p\,=\,0.01$ (dashed curves)

Fig. 4

The performance Comparison between the code with parity-check matrix $H^2(2,13,9)$ of length 1521 and rate 0.78, and code in  [8] of length 1500 and rate 0.8 on an erasure channel with one randomly located burst erasure and guard band erasure probabilities $p\,=\,0$ (solid curves) and $p\,=\,0.01$ (dashed curves)

Fig. 5

The performance comparison between the code with parity-check matrix $H(2,17,8) \bar{\odot }H(2,11,8)$ of length 1496 and rate 0.75, and code in  [8] of length 1500 and rate 0.8 on an erasure channel with one randomly located burst erasure and guard band erasure probabilities $p\,=\,0$ (solid curves) and $p\,=\,0.01$ (dashed curves)

Fig. 6

The performance comparison of the code with parity-check matrix $H(2,11,8) \underline{\odot } H(11,17,8)$ of length 1496 and rate 0.75, and code in  [8] of length 1500 and rate 0.8 on an erasure channel with one randomly located burst erasure and guard band erasure probabilities $p\,=\,0$ (solid curves) and $p\,=\,0.01$ (dashed curves)

In the case of dashed curves, just like [5], other solid and dash curves in figures belongs to the first, second and third structures of  [5] and the interleaved MDS code where the symbol of each code is shown in the guide of the figures. The derived $L_{max}$ for the shortened array code with parity-check matrix $H(2,151,10)$ is 301, (Fig. 3).

The value $L_{max}$ of this structure is greater than other codes, because it is a burstMDS code, and has less bit error rate than other structures for bursts erasure length larger than $L_{max}$. The derived $L_{max}$ for the code with parity-check matrix $H^2(2,13,9)$ is 324, (Fig. 4). In solid curves, the bit error rate of this construction is better than the others because, first of all $L_{max}$ of this code is greater than others and second it has a better BER than other codes when the burst erasure length is increased.

The obtained $L_{max}$ for the code with parity-check matrix $H(2,17,8) \bar{\odot }H(2,11,8)$ is $362$, (Fig. 5). In both cases, solid curves with $p=0$, and dashed curves with $p=0.01$, the bit error rate of the code is better than the others. Computed $L_{max}$ for the code with parity-check matrix $H(2,11,8)\underline{\odot }H(11,17,8)$ is 359, (see Fig. 6). This construction has provided better results in both cases, solid curves and dashed curves.

5 Conclusion

Some structured LDPC codes on burst erasure channels have been proposed. It was shown how array codes, as a well known LDPC codes over AWGN channels, and a kind of shortened and superposed of them could be used for constructing suitable codes over burst erasure channels. Cycles, corresponding to consecutive columns in parity check matrices of the constructed codes, were studied and used for determining the value of $L_{max}$ as an important parameter in the constructed codes over burst erasure channels. These LDPC codes are categorized in four classes with one of them being a burstMDS code and having efficiency equal to $1$. It was shown that all the constructed codes compete with the well-known LDPC codes of comparable rate and length over single burst erasure channels. Simplicity in construction, low encoding complexity, various lengths and rates are another advantages of the introduced codes.