# A Construction of High Performance Quasicyclic LDPC Codes: A Combinatoric Design Approach

Authors: Muhammad Asif; Wuyang Zhou; Muhammad Ajmal; Zain ul Abiden Akhtar; Nauman Ali Khan
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

This correspondence presents a construction of quasicyclic (QC) low-density parity-check (LDPC) codes based on a special type of combinatorial designs known as block disjoint difference families (BDDFs). The proposed construction of QC-LDPC codes gives parity-check matrices with column weight three and Tanner graphs having a girth lower-bounded by 6. The proposed QC-LDPC codes provide an excellent performance with iterative decoding over an additive white Gaussian-noise(AWGN) channel. Performance analysis shows that the proposed short and moderate length QC-LDPC codes perform as well as their competitors in the lower signal-to-noise ratio (SNR) region but outperform in the higher SNR region. Also, the codes constructed are quasicyclic in nature, so the encoding can be done with simple shift-register circuits with linear complexity.


---

## Body

## 1. Introduction

Low-density parity-check codes [1] are of vital importance for many modern communication systems because of their capacity-approaching performance and low-complexity iterative decoding over noisy information channels. LDPC codes were first discovered by Robert Gallager in the early 1960’s and rediscovered by Mackay [2] in 1990’s. LDPC codes provide many advantages over other error correction codes in terms of error performance, low-cost encoding and decoding, and a flexible scale for code length and rate selection. Therefore, LDPC codes have become a focal choice for many advanced communication standards such as Wi-Fi (802.11n/ac/ad), WiMAX (802.16e), and 10 Gigabit Ethernet (802.3an). After several rounds of discussions, LDPC codes have been determined for 5G communications. LDPC codes have been adopted by an important scenario of 5G communications known as enhanced mobile broadband (eMBB). The most promising error correction codes for 5G communications are polar codes, spatially coupled LDPC codes, binary/nonbinary LDPC codes, block Markov superposition transmission (BMST), and turbo codes. Recently, in literature [3, 4], low-complexity decoding algorithms have been presented for LDPC codes. Because of these significant efforts, LDPC codes have been adopted for many next-generation communication systems.A binary(wc,wr)-regular LDPC code is defined by the null space of a parity-check matrix H having constant column-weight wc and constant row-weight wr. The null space of a parity-check matrix having variable column and/or variable row weights gives an irregular LDPC code. If the parity-check matrix consists of an array circulant permutation matrices of same size over a finite field GF(q), the null space of this parity-check matrix gives a QC-LDPC code over GF(q) [5–7]. An important constraint on parity-check matrix that any two rows or columns of H can agree in at most one position, called Row-Column (RC)-constraint. The RC-constraint on parity-check matrix H guarantees that the Tanner graph of an LDPC code has no length-4 cycles.Based on the major construction methods, LDPC codes are categorized into two classes: (1) random-like LDPC codes are designed based on computer search, the most well-known random-like constructions are based on PEG [8] and protograph-based methods [9–11]; (2) structured LDPC codes are constructed based on algebraic techniques such as finite fields [5, 6, 12–20], finite geometries [21, 22], and combinatorial structures [23–32]. The QC-LDPC codes, also known as architecture-aware codes, are one of the most studied LDPC codes because their parity-check matrices have a special structure which facilitates the hardware implementations of an encoder and decoder. Compared to random-like LDPC codes, the QC-LDPC codes have generator matrices which are quasicyclic in nature, so encoding can be done with shift register circuits having linear complexity.Recently, some researchers have focused on a special class of regular QC-LDPC codes with parity-check matrices composed of an array of circulant permutation matrices and proved that the minimum distance of any(wc,wr)-regular QC-LDPC code is lower-bounded by wc+1 and a girth of at most 12 [33, 34]. In literature [23–32], QC-LDPC codes have been constructed based on the different combinatorial structures. In this correspondence, a construction method for binary QC-LDPC codes based on block disjoint difference families [35, 36] is presented. The proposed construction scheme gives length-4 cycles free QC-LDPC codes. The proposed QC-LDPC codes constructed for short and moderate length applications provide excellent error-correcting performance with iterative decoding over an AWGN channel. Based on numerical testing, the proposed QC-LDPC codes perform as well as their competitors in the lower SNR region but outperform in the higher SNR region. Also, the codes constructed are quasicyclic in nature, so the encoding can be done with simple shift-register circuits with linear complexity.The remainder of this correspondence is arranged as follows: in Section2, the basic concepts about design theory and cyclic difference families (CDFs) are given. The existence and construction of block disjoint difference families based on Skolem and Rosa Triple systems are given in Section 3. Section 4 presents the construction of QC-LDPC codes based on BDDFs for v=1,3mod6. Performance analysis based on numerical results is presented in Section 5, and the conclusion of this correspondence is presented in Section 6.


## 2. Basic Concepts and Definitions

In this section, we discuss some basic concepts of design theory such as balanced incomplete block design (BIBD), cyclic difference families, and block disjoint difference families.Definition 1 (see [37]).
A design is a pair(X,A), where X is a set of elements called points and A is a collection of nonempty subsets of X called blocks. Let v, k, and λ be positive integers such that v>k≥2. A (v,k,λ)-BIBD is a design (X,A) such that the following properties hold: (i)
X=v,(ii)
each block contains exactlyk points, and(iii)
every pair of points appear in exactlyλ blocks.Definition 2 (see [37]).
LetZv={0,1,…,v-1} be an additive group. The ω k-element subsets of Zv, Ai={ai1,ai2,…,aik}, i=1,2,…,ω, ai1<ai2<⋯<aik, give a cyclic difference family represented as (v,k,λ) if all nonzero elements appear λ times among the differences aix-aiy, i=1,2,…,ω, x≠y, x,y=1,2,…,k. This (v,k,λ)-CDF is called a planar CDF if λ=1.
In [26–30], (k(k-1)ω+1,k,1)-CDFs are used to construct QC-LDPC having a girth lower bounded by 6. The existences of (k(k-1)ω+1,k,1)-CDFs are given in Theorem 3.Theorem 3.
Under any of the following conditions, a(v,k,1)-CDF exists: (i)
A(6ω+1,3,1) cyclic difference family exists for all ω≥1 [38].(ii)
A(12ω+1,4,1) cyclic difference family exists for all 1≤ω≤1000 [39].(iii)
A(20ω+1,5,1) cyclic difference family exists for 1≤ω≤50 and ω≠16,25,31,34,40,45 [40].In this correspondence, regular QC-LDPC codes of short and moderate lengths are constructed using a special class of cyclic difference families, called block disjoint difference families.Definition 4 (see [36]).
IfZv is an additive group, then a family of k-tuples of elements from Zv is a (v,k,λ)-CDF if the collection of blocks of k-tuples form a (v,k,λ) balanced incomplete block design. If this collection of blocks is disjoint, the family (v,k,λ) is known as a block disjoint difference family.In next section, we review some constructions of(v,3,1)-BDDFs based on Skolem Triple System and Rosa Triple System for v=1mod6 and v=3mod6, respectively. Finally, we will use (v,3,1)-BDDFs, v=1,3mod6, to desing lenght-4 cycles free binary QC-LDPC codes.


## 3. Block Disjoint Difference Families (BDDFs)

### 3.1. Construction of (v, 3, 1)-BDDFs for v= 1 mod 6

Based on Skolem Triple System, a class of(v,3,1)-CDFs is used to construct (v,3,1)-BDDFs for v=1mod6. First, we construct (v,3,1)-CDFs based on Skolem Triple Systems, and then a linear translation of (v,3,1)-CDFs gives (v,3,1)-BDDFs for v=1mod6.Definition 5 (see [37]).
A sequenceS=(s1,s2,…,s2ω) of 2ω elements taken from {1,2,…,ω} is known as a Skolem sequence of order ω if(i)
everysm∈{1,…,ω} appears exactly twice in S, and(ii)
ifsm=sn=μ for n>m, then n-m=μ.
Skolem sequences can also be represented as collections of ordered pairs{(xj,yj):1≤j≤ω,yj-xj=j} with ⋃j=1ω{xj,yj}={1,2,…,2ω}. Skolem sequences of order ω exist if and only if ω=0,1mod4. Skolem sequences of order ω are constructed by a method given in [37]. (i)
ω=1;(1,1)(ii)
ω=4;(1,1,3,4,2,3,2,4)(iii)
ω=5;(2,4,2,3,5,4,3,1,1,5)(iv)
ω=4α;α≥2(1)2α,4α-1,2α+1,6αα-1,3α,α,α+14α+ψ-1,8α-ψ+1ψ=1,…,2αα+ψ+1,3α-ψψ=1,…,α-2ψ,4α-ψ-1ψ=1,…,α-2(v)
ω=4α+1;α≥2(2)α+1,α+2,2α+1,6α+2,2α+2,4α+14α+ψ+1,ψα-ψ+3,ψ=1,…,2αα+ψ+2,3α-ψ+1,ψ=1,…,α-2ψ,4α-ψ+1,ψ=1,…,αExample 6.
We construct a Skolem sequence of order8(3)S=4,1,1,5,4,7,8,3,5,6,3,2,7,2,8,6A Skolem sequence of order ω can be used to generate a Steiner Triple System (STS) of order 6ω+1 using following construction:(i)
for eachsi=sj∈S, form pairs (i,j).(ii)
transform each pair into triples(μ,i+ω,j+ω), where si=sj=μ.(iii)
transform each triple(μ,i+ω,j+ω) into base blocks {0,μ,j+ω}.(iv)
each base block in (iii) is developed by adding1 under Z6ω+1 to generate an STS of order (6ω+1).Example 7.
We construct an STS(25). First, construct a skolem sequence of order4, S=(1,1,4,2,3,2,4,3). From step (i), we obtain the pairs (1,2),(4,6),(5,8),(3,7). Based on step (ii), we then convert these pairs into triples (1,5,6),(2,8,10),(3,9,12),(4,7,11). Using transformation in step (iii), we construct the sets {0,1,6},{0,2,10},{0,3,12},{0,4,11}. We then add 1 to each of these sets mod25 to obtain a STS of size 4×25=100.
From a STS of order(6ω+1), a (6ω+1,3,1)-CDF can be obtained by letting Ai={0,μ,j+ω}, for 1≤i≤ω, where Ai’s denote the base blocks of a (6ω+1,3,1)-CDF. A construction of (6ω+1,3,1)-BDDFs using a linear translation of (6ω+1,3,1)-CDFs based on Skolem Triple System can be found in [35].Theorem 8 (see [35]).
There exists a block disjoint(24ω+1,3,1) difference family for ω≥1.Proof.
Beginning with a(24ω+1,3,1)-CDF based on a Skolem Triple System of order 4ω that does not have disjoint blocks, the idea is to linearly translate the blocks such that no two blocks intersect. This construction requires that ω≥3. The cases for smaller values of ω are treated separately.(4)a1:0,1,12ωb1:0,4ω-1,9ω-1c1:0,2ω,10ω-1d1:0,4ω,10ωe1:0,2ω-2r-1,7ω+r-1,1≤r≤ω-1f1:0,2ω+2r,11ω+r-1,1≤r≤ω-1g1:0,2r+1,10ω+r,1≤r≤ω-1h1:0,2r,6ω+r,1≤r≤ω-1
By linear translation of above cyclic difference family, we can obtain the following block disjoint difference family:(5)a11:7ω-1,7ω,19ω-1,ω=0mod2a12:7ω,7ω+1,19ω,ω=1mod2b11:2ω+2,6ω+1,11ω+1c11:0,2ω,10ω-1d11:6ω,10ω,16ωe11:2r,2ω+4r-1,7ω+3r-1f11:2r+1,2ω+4r+1,11ω+3rg11:17ω+4r,17ω+2r-1,ω+3rh11:21ω+r+1+sω,21ω+3r+1+sω,3ω+2r+sω,r≢0mod3h12:13ω+r-lr+5,13ω+3r-lr+5,19ω+2r-lr+5r≡0mod3andr≢ω-1h13:10ω+13,12ω+1,17ω+2,ω≡1mod3
where1≤r≤ω-1,sω=ωmod2, and lr is defined asForω≡0mod3: if r≠3r′-lr′ for all r′<r then lr=0; otherwise lr=4.Forω≡1mod3: if r≠3r′-lr′ for all r′<r then lr=0; otherwise lr=2.Forω≡2mod3: if r≠3r′-lr′+2 for all r′<r then lr=2; otherwise lr=4.
Since by linear translation (and one flip) of cyclic difference family based on Skolem Triple Systems a block disjoint difference family is obtained, clearly, the new set of triples is also a difference family with disjoint blocks. The linear translation from cyclic difference family to block disjoint difference family is summarized in Table1. In the following cases for small values of ω, 1≤ω≤2:v=25ω=1: (0,2,9), (6,10,16), (7,8,19), (12,15,20).v=49(ω=2): (0,4,19), (2,7,16), (3,9,25), (6,13,23), (8,44,46), (12,20,32), (17,35,37), (21,22,45).
It is relatively easy to verify that the triples are all disjoint which complete the proof.Table 1
Linear translation from CDFs to BDDFs forv=1mod6.
CDF BDDF Add Comments a1 a 11 7 ω - 1 ifω≡0mod2  a1 a 12 7 ω ifω≡1mod2  b1 b 11 2 ω + 2  c1 c 11 0  d1 d 11 6t  e1 e 11 2 r for1≤r≤ω-1  f1 f 11 2 r + 1 for1≤r≤ω-1  g1 g 11 17 ω + 4 r to{0,-(2r+1),-(10ω+r)} for 1≤r≤ω-1  h1 h 11 21 ω + r + s ω 1 ≤ r ≤ ω - 1 if r≢0mod3  h1 h 12 13 ω + r - l r + 5 1 ≤ r ≤ ω - 2 if r≡0mod3  h1 h 13 10 ω + 3 ifr≡0mod3


### 3.2. Construction of (v, 3, 1)-BDDFs for v=3 mod 6

This subsection gives a construction of(v,3,1)-BDDFs for v=3mod6. A class of (v,3,1)-CDFs based on Rosa Triple Systems is used to construct (v,3,1)-BDDFs for v=3mod6. First, we construct (v,3,1)-CDFs based on Rosa Triple System, then by a linear translation of (v,3,1)-CDFs we obtain (v,3,1)-BDDFs for v=3mod6.Definition 9 (see [37]).
A sequenceS=(s1,…,sω,0,sω+2,…,s2ω+1) of 2ω+1 elements taken from {1,2,…,ω} is said to be a Rosa sequence of order ω if all of the following hold: (i)
everysi∈{1,…,ω} appears exactly twice in S.(ii)
ifsm=sn=μ for n>m, then n-m=μ.(iii)
a hook or zero is inserted at positionω+1.Rosa sequences can also be expressed as collections of ordered pairs{(xi,yi):1≤i≤ω,yi-xi=i} with ⋃i=1ω{xi,yi}={1,2,…,2ω}. Rosa sequences of order ω exist if and only if ω=0,3mod4. A Rosa sequence of order ω can be constructed by a method given in [37].(1)
ω=2;{(1,2),(4,6)}(2)
ω=5;{(1,5),(2,7),(3,4),(8,10),(9,12))}(3)
ω=4α;α≥1(6)2α-1,2α,3α,5α+13α+1,7α+1,6α+1,8α+14α+ψ+1,8α-ψ+1ψ=1,…,α-15α+ψ+1,7α-ψ+1ψ=1,…,α-1α+ψ-1,3α-ψψ=1,…,α-1ψ,4α-ψ+1ψ=1,…,α-1(4)
ω=4α-1;α≥2(7)6α-1,2α,5α,7α+14α+1,6α,7α-1,7α5α+ψ,7α-ψ-1ψ=1,…,α-24α+ψ+1,8α-ψψ=1,…,α-2ψ,4α-ψψ=1,…,α-2Example 10.
We construct a Rosa sequence of order 8(8)S=3,1,1,3,6,7,5,8,0,4,6,5,7,4,2,8,2Rosa sequences of order ω can be used to generate Steiner Triple System of order 6ω+3 using following construction [37]:(i)
for eachsi=sj∈S, form pairs (i,j).(ii)
Transform each pair into triples(μ,i+ω,j+ω), where si=sj=μ.(iii)
Transform each triple(μ,i+ω,j+ω) into sets {0,μ,j+ω}.(iv)
each base block in (iii) is developed by adding1 under Z6ω+3.(v)
Add triples of the form{0,2ω+1,4ω+2}.(vi)
Add 1 to this triplemod6ω+3 to generate the STS of order 6ω+3.
It is important to note that, from step (i) to step (iv), the construction of STS of order6ω+3 is same as the construction of STS of order 6ω+1. But, step (v) and step (vi) are additionally added in the construction of STS of order 6ω+3. Since, the differences between elements of base blocks must exist in the difference set {1,2,…,6ω+2}. Each base block of STS of order 6ω+3 in step (iii) covers six differences of the difference set. Then, all the base blocks of STS of order 6ω+3 cover 6ω differences of the difference set {1,2,…,6ω+2}. So, there are two differences which are not covered by the base blocks in step (iii). To obtain the two missing differences, from step (v), a short block of the form {0,2ω+1,4ω+2} is added. Finally, from step (vi), the short block {0,2ω+1,4ω+2} is developed by adding 1 of order v/3 which gives the missing v/3 blocks of STS of order 6ω+3.Example 11.
We construct an STS of order27. First, construct a Rosa sequence of order 4, S=(1,1,3,4,0,3,2,4,2). From step (i), we obtain the pairs (1,2),(7,9),(3,6),(4,8). Based on step (ii), we convert these pairs into triples (1,5,6),(2,11,13),(3,7,10),(4,8,12). Using transformation in step (iii), we construct the base blocks {0,1,6},{0,2,13},{0,3,10},{0,4,12}. From step (iv), each base block obtained from step (iii) is developed by adding 1 under Z27. If we develop all base blocks in (iii) under mod 27, we obtain 108 blocks. But, we know however that this is a BIBD and total number of blocks must be equal to n=v(v-1)/k(k-1)=27(27-1)/3(3-1)=117. Also, the differences between elements of four base blocks in step (iii) cover 24 differences of the difference set {1,2,…,26} and two differences, {9,18}, are missing. To obtain the two missing differences, from step (v), a short block of the form {0,9,18} is added. Finally, from step (vi), the short block {0,9,18} is developed by adding 1 of order 9 which gives the missing 9 blocks of STS of order 27.
From a STS of order(6ω+3), a (6ω+3,3,1)-CDF can be constructed by letting Ai={0,μ,j+ω}, for 1≤i≤ω, where Ai’s are called the base blocks of a (6ω+3,3,1)-CDF. Theorem 12 gives the construction of (6ω+3,3,1)-BDDFs by linear translation of (6ω+3,3,1)-CDFs based on Rosa Triple System.Theorem 12 (see [36]).
There exists a block disjoint(24ω+3,3,1) difference family for ω≥0.
Beginning with a(24ω+3,3,1)-CDF based on a Rosa Triple System of order 4ω that does not have disjoint blocks, the idea is to linearly translate the blocks such that no two blocks intersect. A detailed construction of (v,3,1)-BDDFs based on Rosa Triple System can be found in [36].In next section, we construct two classes of binary QC-LDPC codes based on(v,k,1)-BDDFs for v=1,3mod6.


## 3.1. Construction of (v, 3, 1)-BDDFs for v= 1 mod 6

Based on Skolem Triple System, a class of(v,3,1)-CDFs is used to construct (v,3,1)-BDDFs for v=1mod6. First, we construct (v,3,1)-CDFs based on Skolem Triple Systems, and then a linear translation of (v,3,1)-CDFs gives (v,3,1)-BDDFs for v=1mod6.Definition 5 (see [37]).
A sequenceS=(s1,s2,…,s2ω) of 2ω elements taken from {1,2,…,ω} is known as a Skolem sequence of order ω if(i)
everysm∈{1,…,ω} appears exactly twice in S, and(ii)
ifsm=sn=μ for n>m, then n-m=μ.
Skolem sequences can also be represented as collections of ordered pairs{(xj,yj):1≤j≤ω,yj-xj=j} with ⋃j=1ω{xj,yj}={1,2,…,2ω}. Skolem sequences of order ω exist if and only if ω=0,1mod4. Skolem sequences of order ω are constructed by a method given in [37]. (i)
ω=1;(1,1)(ii)
ω=4;(1,1,3,4,2,3,2,4)(iii)
ω=5;(2,4,2,3,5,4,3,1,1,5)(iv)
ω=4α;α≥2(1)2α,4α-1,2α+1,6αα-1,3α,α,α+14α+ψ-1,8α-ψ+1ψ=1,…,2αα+ψ+1,3α-ψψ=1,…,α-2ψ,4α-ψ-1ψ=1,…,α-2(v)
ω=4α+1;α≥2(2)α+1,α+2,2α+1,6α+2,2α+2,4α+14α+ψ+1,ψα-ψ+3,ψ=1,…,2αα+ψ+2,3α-ψ+1,ψ=1,…,α-2ψ,4α-ψ+1,ψ=1,…,αExample 6.
We construct a Skolem sequence of order8(3)S=4,1,1,5,4,7,8,3,5,6,3,2,7,2,8,6A Skolem sequence of order ω can be used to generate a Steiner Triple System (STS) of order 6ω+1 using following construction:(i)
for eachsi=sj∈S, form pairs (i,j).(ii)
transform each pair into triples(μ,i+ω,j+ω), where si=sj=μ.(iii)
transform each triple(μ,i+ω,j+ω) into base blocks {0,μ,j+ω}.(iv)
each base block in (iii) is developed by adding1 under Z6ω+1 to generate an STS of order (6ω+1).Example 7.
We construct an STS(25). First, construct a skolem sequence of order4, S=(1,1,4,2,3,2,4,3). From step (i), we obtain the pairs (1,2),(4,6),(5,8),(3,7). Based on step (ii), we then convert these pairs into triples (1,5,6),(2,8,10),(3,9,12),(4,7,11). Using transformation in step (iii), we construct the sets {0,1,6},{0,2,10},{0,3,12},{0,4,11}. We then add 1 to each of these sets mod25 to obtain a STS of size 4×25=100.
From a STS of order(6ω+1), a (6ω+1,3,1)-CDF can be obtained by letting Ai={0,μ,j+ω}, for 1≤i≤ω, where Ai’s denote the base blocks of a (6ω+1,3,1)-CDF. A construction of (6ω+1,3,1)-BDDFs using a linear translation of (6ω+1,3,1)-CDFs based on Skolem Triple System can be found in [35].Theorem 8 (see [35]).
There exists a block disjoint(24ω+1,3,1) difference family for ω≥1.Proof.
Beginning with a(24ω+1,3,1)-CDF based on a Skolem Triple System of order 4ω that does not have disjoint blocks, the idea is to linearly translate the blocks such that no two blocks intersect. This construction requires that ω≥3. The cases for smaller values of ω are treated separately.(4)a1:0,1,12ωb1:0,4ω-1,9ω-1c1:0,2ω,10ω-1d1:0,4ω,10ωe1:0,2ω-2r-1,7ω+r-1,1≤r≤ω-1f1:0,2ω+2r,11ω+r-1,1≤r≤ω-1g1:0,2r+1,10ω+r,1≤r≤ω-1h1:0,2r,6ω+r,1≤r≤ω-1
By linear translation of above cyclic difference family, we can obtain the following block disjoint difference family:(5)a11:7ω-1,7ω,19ω-1,ω=0mod2a12:7ω,7ω+1,19ω,ω=1mod2b11:2ω+2,6ω+1,11ω+1c11:0,2ω,10ω-1d11:6ω,10ω,16ωe11:2r,2ω+4r-1,7ω+3r-1f11:2r+1,2ω+4r+1,11ω+3rg11:17ω+4r,17ω+2r-1,ω+3rh11:21ω+r+1+sω,21ω+3r+1+sω,3ω+2r+sω,r≢0mod3h12:13ω+r-lr+5,13ω+3r-lr+5,19ω+2r-lr+5r≡0mod3andr≢ω-1h13:10ω+13,12ω+1,17ω+2,ω≡1mod3
where1≤r≤ω-1,sω=ωmod2, and lr is defined asForω≡0mod3: if r≠3r′-lr′ for all r′<r then lr=0; otherwise lr=4.Forω≡1mod3: if r≠3r′-lr′ for all r′<r then lr=0; otherwise lr=2.Forω≡2mod3: if r≠3r′-lr′+2 for all r′<r then lr=2; otherwise lr=4.
Since by linear translation (and one flip) of cyclic difference family based on Skolem Triple Systems a block disjoint difference family is obtained, clearly, the new set of triples is also a difference family with disjoint blocks. The linear translation from cyclic difference family to block disjoint difference family is summarized in Table1. In the following cases for small values of ω, 1≤ω≤2:v=25ω=1: (0,2,9), (6,10,16), (7,8,19), (12,15,20).v=49(ω=2): (0,4,19), (2,7,16), (3,9,25), (6,13,23), (8,44,46), (12,20,32), (17,35,37), (21,22,45).
It is relatively easy to verify that the triples are all disjoint which complete the proof.Table 1
Linear translation from CDFs to BDDFs forv=1mod6.
CDF BDDF Add Comments a1 a 11 7 ω - 1 ifω≡0mod2  a1 a 12 7 ω ifω≡1mod2  b1 b 11 2 ω + 2  c1 c 11 0  d1 d 11 6t  e1 e 11 2 r for1≤r≤ω-1  f1 f 11 2 r + 1 for1≤r≤ω-1  g1 g 11 17 ω + 4 r to{0,-(2r+1),-(10ω+r)} for 1≤r≤ω-1  h1 h 11 21 ω + r + s ω 1 ≤ r ≤ ω - 1 if r≢0mod3  h1 h 12 13 ω + r - l r + 5 1 ≤ r ≤ ω - 2 if r≡0mod3  h1 h 13 10 ω + 3 ifr≡0mod3


## 3.2. Construction of (v, 3, 1)-BDDFs for v=3 mod 6

This subsection gives a construction of(v,3,1)-BDDFs for v=3mod6. A class of (v,3,1)-CDFs based on Rosa Triple Systems is used to construct (v,3,1)-BDDFs for v=3mod6. First, we construct (v,3,1)-CDFs based on Rosa Triple System, then by a linear translation of (v,3,1)-CDFs we obtain (v,3,1)-BDDFs for v=3mod6.Definition 9 (see [37]).
A sequenceS=(s1,…,sω,0,sω+2,…,s2ω+1) of 2ω+1 elements taken from {1,2,…,ω} is said to be a Rosa sequence of order ω if all of the following hold: (i)
everysi∈{1,…,ω} appears exactly twice in S.(ii)
ifsm=sn=μ for n>m, then n-m=μ.(iii)
a hook or zero is inserted at positionω+1.Rosa sequences can also be expressed as collections of ordered pairs{(xi,yi):1≤i≤ω,yi-xi=i} with ⋃i=1ω{xi,yi}={1,2,…,2ω}. Rosa sequences of order ω exist if and only if ω=0,3mod4. A Rosa sequence of order ω can be constructed by a method given in [37].(1)
ω=2;{(1,2),(4,6)}(2)
ω=5;{(1,5),(2,7),(3,4),(8,10),(9,12))}(3)
ω=4α;α≥1(6)2α-1,2α,3α,5α+13α+1,7α+1,6α+1,8α+14α+ψ+1,8α-ψ+1ψ=1,…,α-15α+ψ+1,7α-ψ+1ψ=1,…,α-1α+ψ-1,3α-ψψ=1,…,α-1ψ,4α-ψ+1ψ=1,…,α-1(4)
ω=4α-1;α≥2(7)6α-1,2α,5α,7α+14α+1,6α,7α-1,7α5α+ψ,7α-ψ-1ψ=1,…,α-24α+ψ+1,8α-ψψ=1,…,α-2ψ,4α-ψψ=1,…,α-2Example 10.
We construct a Rosa sequence of order 8(8)S=3,1,1,3,6,7,5,8,0,4,6,5,7,4,2,8,2Rosa sequences of order ω can be used to generate Steiner Triple System of order 6ω+3 using following construction [37]:(i)
for eachsi=sj∈S, form pairs (i,j).(ii)
Transform each pair into triples(μ,i+ω,j+ω), where si=sj=μ.(iii)
Transform each triple(μ,i+ω,j+ω) into sets {0,μ,j+ω}.(iv)
each base block in (iii) is developed by adding1 under Z6ω+3.(v)
Add triples of the form{0,2ω+1,4ω+2}.(vi)
Add 1 to this triplemod6ω+3 to generate the STS of order 6ω+3.
It is important to note that, from step (i) to step (iv), the construction of STS of order6ω+3 is same as the construction of STS of order 6ω+1. But, step (v) and step (vi) are additionally added in the construction of STS of order 6ω+3. Since, the differences between elements of base blocks must exist in the difference set {1,2,…,6ω+2}. Each base block of STS of order 6ω+3 in step (iii) covers six differences of the difference set. Then, all the base blocks of STS of order 6ω+3 cover 6ω differences of the difference set {1,2,…,6ω+2}. So, there are two differences which are not covered by the base blocks in step (iii). To obtain the two missing differences, from step (v), a short block of the form {0,2ω+1,4ω+2} is added. Finally, from step (vi), the short block {0,2ω+1,4ω+2} is developed by adding 1 of order v/3 which gives the missing v/3 blocks of STS of order 6ω+3.Example 11.
We construct an STS of order27. First, construct a Rosa sequence of order 4, S=(1,1,3,4,0,3,2,4,2). From step (i), we obtain the pairs (1,2),(7,9),(3,6),(4,8). Based on step (ii), we convert these pairs into triples (1,5,6),(2,11,13),(3,7,10),(4,8,12). Using transformation in step (iii), we construct the base blocks {0,1,6},{0,2,13},{0,3,10},{0,4,12}. From step (iv), each base block obtained from step (iii) is developed by adding 1 under Z27. If we develop all base blocks in (iii) under mod 27, we obtain 108 blocks. But, we know however that this is a BIBD and total number of blocks must be equal to n=v(v-1)/k(k-1)=27(27-1)/3(3-1)=117. Also, the differences between elements of four base blocks in step (iii) cover 24 differences of the difference set {1,2,…,26} and two differences, {9,18}, are missing. To obtain the two missing differences, from step (v), a short block of the form {0,9,18} is added. Finally, from step (vi), the short block {0,9,18} is developed by adding 1 of order 9 which gives the missing 9 blocks of STS of order 27.
From a STS of order(6ω+3), a (6ω+3,3,1)-CDF can be constructed by letting Ai={0,μ,j+ω}, for 1≤i≤ω, where Ai’s are called the base blocks of a (6ω+3,3,1)-CDF. Theorem 12 gives the construction of (6ω+3,3,1)-BDDFs by linear translation of (6ω+3,3,1)-CDFs based on Rosa Triple System.Theorem 12 (see [36]).
There exists a block disjoint(24ω+3,3,1) difference family for ω≥0.
Beginning with a(24ω+3,3,1)-CDF based on a Rosa Triple System of order 4ω that does not have disjoint blocks, the idea is to linearly translate the blocks such that no two blocks intersect. A detailed construction of (v,3,1)-BDDFs based on Rosa Triple System can be found in [36].In next section, we construct two classes of binary QC-LDPC codes based on(v,k,1)-BDDFs for v=1,3mod6.


## 4. BDDFs-Based Construction of QC-LDPC Codes

Consider a parity-check matrixH(1) consisting of an 1×ω array of k×k circulant matrices given as follows:(9)H1=Q1,Q2,…,QωBased on the block disjoint difference families forv=1,3mod6 given in Sections 3.1 and 3.2, we construct a parity-check matrix H(1) where each Qi, 1≤i≤ω, represents a k×k circulant permutation matrix whose each row is obtained from the right cyclic shift of the row above it. The first row of Qi is obtained from one of the ωk-element base blocks of the (v,k,1)-BDDFs for v=1,3mod6. The null space of H(1) gives a QC-LDPC code of rate ω-1/ω and a girth of at least 6.To make the idea more clear, a detailed construction of parity-check matrices based on the(v,k,1)-BDDFs is given in Example 13, as followsExample 13.
Consider a(25,3,1)-BDDF with base blocks Ai={ai1,ai2,…,aik}, i=1,…,4, and k=3 for Z25. The base blocks for a (6×4+1,3,1)-BDDF are(10)A1=0,2,9,A2=6,10,16,A3=12,15,20,A4=7,8,19.Based on above construction, we can construct a matrixB using a (25,3,1)-BDDF for v=1mod6: (11)B=029610161215207819902166102012151978290101661520128197Theorem 14.
The parity-check matrixH1 based on BDDFs for v=1,3mod6 given in (9) has no length-4 cycles.Proof.
To prove this theorem, we have to prove thatQi’s, for 1≤i≤ω, of H(1) have no length-4 cycles.
Consider a submatrixW given as(12)W=λ1μ1λ2μ2.where λ1,λ2∈Qi and μ1,μ2∈Qj, 1≤i,j≤ω. The submatrix W has cycles of length 4 if and only if λ1-λ2=μ1-μ2 mod v. Due to the property of BDDFs, all the elements of Qi and Qj are distinct. So, both of the differences λ1-λ2andμ1-μ2 satisfy the relation that λ1-λ2≠μ1-μ2. Therefore, the matrix H(1) has no length-4 cycles and provides a girth of at least 6.


### 4.1. A Class of Binary QC-LDPC Codes: Method I

In this subsection, we give a construction of binary QC-LDPC codes based on the BDDFs forv=1,3mod6. Let GF(q) be a finite field. For each nonzero element δi in GF(q), 0≤i<q-1, form a (q-1)-tuple over GF(2), ub(δi)=(u0,u1,…,uq-2), where all the components of ub are equal to zero except the ith component ui=1. Subscript “b” stands for binary. This (q-1)-tuple over GF(2) is referred to as the binary location-vector of δi. The binary location-vector of additive identity of GF(q) is an all-zero (q-1)-tuple, ub(0)=(0,0,0,…,0).Letα be an element of GF(q). The right cyclic-shift of binary location vector ub(α) of field element α gives the binary location vector ub(αδ) of field element αδ. If δ is a primitive element of GF(q), then the (q-1)-tuples of α,δα,δ2α,…,δq-2α, give a (q-1)×(q-1) circular permutation matrix Wb(α) over GF(2). The matrix Wb(α) is called a (q-1)-fold binary dispersion of α over GF(2). If α=0, then the (q-1)-fold binary dispersion of 0-element Wb(0) is a (q-1)×(q-1) all-zero matrix over GF(2).Next, replacing each element ofH(1) given in (9) by its (q-1)-fold binary matrix dispersion Wb over GF(2). We obtain an k×kω array Hb(1) over GF(2):(13)Hb1=W0,0W0,1⋯W0,kω-1W1,0W1,1⋯W1,kω-1⋮⋮⋱⋮Wk-1,0Wk-1,1⋯Wk-1,kω-1where Wi,j is an (q-1)×(q-1) circular permutation matrix over GF(2), for 0≤i<k and 0≤j<kω. Array Hb(1) gives an k(q-1)×kω(q-1) matrix over GF(2). Since the matrix Hb(1) satisfies the RC-constraint, so the null space of Hb(1) gives an LDPC code whose Tanner graph has a girth of at least 6.For any pair of integerswc and wr, for 1≤wc≤k and 1≤wr≤kω. Let Hb(1)(wc,wr) be a wc×wr subarray of Hb(1) and give a wc(q-1)×wr(q-1) matrix over GF(2). The null space of Hb(1)(wc,wr) over GF(2) gives a binary QC-LDPC code Cqc(1) of length wr(q-1) with rate at least (wr-wc)/wr and minimum distance lower bounded by wc+1. Since Hb(1)(wc,wr) satisfies the RC-constraint, the Tanner graph of Cqc(1) has a girth of at least 6. For different choices of wc and wr, the above construction method gives a class binary QC-LDPC codes for various lengths and rates.


### 4.2. A Class of Binary QC-LDPC Codes: Method II

In this subsection, we use the concept of incidence matrices to construct QC-LDPC codes based on the(v,3,1)-BDDFs. Let X=Zv be a set of v varieties or elements. A design (X,B) with nk-subsets of X, B1,B2,…,Bn, called blocks, is known as (v,n,r,k,λ)-BIBD if the following properties hold: (1) each element appears in exactly r blocks; (2) each pair of elements appears in exactly λ blocks; and (3) the block size k is small compared to the cardinality of X. A (v,n,r,k,λ)-BIBD can also be described by a v×n matrix M=(mi,j) over GF(2) defined by the following rule:(14)mi,j=1ifxi∈Bj0ifxi∉Bj.where matrix M is called the incidence matrix. The incidence matrix of a (v,n,r,k,λ)-BIBD satisfies the following properties: (1) each column of M contains exactly k 1’s; (2) each row of M contains exactly r 1’s; and (3) two distinct rows of M can agree at most λ positions.Example 15.
Let(X,B) be the following (7,7,3,3,1)-BIBD: (15)X=1,2,3,4,5,6,7,andB=124,235,346,457,561,672,713.
The incidence matrix of this(7,7,3,3,1)-BIBD is given as follows:(16)M=1000101110001001100011011000010110000101100001011.It is important to note that each row of M is a right cyclic shift of the previous row and the right cyclic shift of last row returns the first row. Also, each column of M is a downward cyclic shift of a column on its left. Therefore, M is a 7×7 circulant permutation matrix.
Consequently, for a(v,k,λ)-BDDF with λ=1, the incidence matrix M satisfies all the required properties of a parity-check matrix. Therefore, the null space of M gives a (wc,wr)-LDPC code of length n. Also, the incidence matrix M satisfies the RC-constraint with λ=1. So, the Tanner graph of M has a girth of at least 6.
Based onv,k,1-BDDFs for v=1,3mod6, consider a parity-check matrix H(2) consisting of an 1×ω array of circulant matrices given as follows:(17)H2=M1,M2,…,Mωwhere each Mi, 1≤i≤ω, represents a v×n incidence matrix over GF(2). Clearly, the matrix H(2) satisfies all the required properties of a parity-check matrix. The matrix H(2) is a v×ωn matrix over GF(2) with row and column weights 3ω and 3, respectively. The null space of H(2) gives a binary regular QC-LDPC with minimum distance at least 4, rate lower bounded by (ω-1)/ω, and a girth of at least 6.


## 4.1. A Class of Binary QC-LDPC Codes: Method I

In this subsection, we give a construction of binary QC-LDPC codes based on the BDDFs forv=1,3mod6. Let GF(q) be a finite field. For each nonzero element δi in GF(q), 0≤i<q-1, form a (q-1)-tuple over GF(2), ub(δi)=(u0,u1,…,uq-2), where all the components of ub are equal to zero except the ith component ui=1. Subscript “b” stands for binary. This (q-1)-tuple over GF(2) is referred to as the binary location-vector of δi. The binary location-vector of additive identity of GF(q) is an all-zero (q-1)-tuple, ub(0)=(0,0,0,…,0).Letα be an element of GF(q). The right cyclic-shift of binary location vector ub(α) of field element α gives the binary location vector ub(αδ) of field element αδ. If δ is a primitive element of GF(q), then the (q-1)-tuples of α,δα,δ2α,…,δq-2α, give a (q-1)×(q-1) circular permutation matrix Wb(α) over GF(2). The matrix Wb(α) is called a (q-1)-fold binary dispersion of α over GF(2). If α=0, then the (q-1)-fold binary dispersion of 0-element Wb(0) is a (q-1)×(q-1) all-zero matrix over GF(2).Next, replacing each element ofH(1) given in (9) by its (q-1)-fold binary matrix dispersion Wb over GF(2). We obtain an k×kω array Hb(1) over GF(2):(13)Hb1=W0,0W0,1⋯W0,kω-1W1,0W1,1⋯W1,kω-1⋮⋮⋱⋮Wk-1,0Wk-1,1⋯Wk-1,kω-1where Wi,j is an (q-1)×(q-1) circular permutation matrix over GF(2), for 0≤i<k and 0≤j<kω. Array Hb(1) gives an k(q-1)×kω(q-1) matrix over GF(2). Since the matrix Hb(1) satisfies the RC-constraint, so the null space of Hb(1) gives an LDPC code whose Tanner graph has a girth of at least 6.For any pair of integerswc and wr, for 1≤wc≤k and 1≤wr≤kω. Let Hb(1)(wc,wr) be a wc×wr subarray of Hb(1) and give a wc(q-1)×wr(q-1) matrix over GF(2). The null space of Hb(1)(wc,wr) over GF(2) gives a binary QC-LDPC code Cqc(1) of length wr(q-1) with rate at least (wr-wc)/wr and minimum distance lower bounded by wc+1. Since Hb(1)(wc,wr) satisfies the RC-constraint, the Tanner graph of Cqc(1) has a girth of at least 6. For different choices of wc and wr, the above construction method gives a class binary QC-LDPC codes for various lengths and rates.


## 4.2. A Class of Binary QC-LDPC Codes: Method II

In this subsection, we use the concept of incidence matrices to construct QC-LDPC codes based on the(v,3,1)-BDDFs. Let X=Zv be a set of v varieties or elements. A design (X,B) with nk-subsets of X, B1,B2,…,Bn, called blocks, is known as (v,n,r,k,λ)-BIBD if the following properties hold: (1) each element appears in exactly r blocks; (2) each pair of elements appears in exactly λ blocks; and (3) the block size k is small compared to the cardinality of X. A (v,n,r,k,λ)-BIBD can also be described by a v×n matrix M=(mi,j) over GF(2) defined by the following rule:(14)mi,j=1ifxi∈Bj0ifxi∉Bj.where matrix M is called the incidence matrix. The incidence matrix of a (v,n,r,k,λ)-BIBD satisfies the following properties: (1) each column of M contains exactly k 1’s; (2) each row of M contains exactly r 1’s; and (3) two distinct rows of M can agree at most λ positions.Example 15.
Let(X,B) be the following (7,7,3,3,1)-BIBD: (15)X=1,2,3,4,5,6,7,andB=124,235,346,457,561,672,713.
The incidence matrix of this(7,7,3,3,1)-BIBD is given as follows:(16)M=1000101110001001100011011000010110000101100001011.It is important to note that each row of M is a right cyclic shift of the previous row and the right cyclic shift of last row returns the first row. Also, each column of M is a downward cyclic shift of a column on its left. Therefore, M is a 7×7 circulant permutation matrix.
Consequently, for a(v,k,λ)-BDDF with λ=1, the incidence matrix M satisfies all the required properties of a parity-check matrix. Therefore, the null space of M gives a (wc,wr)-LDPC code of length n. Also, the incidence matrix M satisfies the RC-constraint with λ=1. So, the Tanner graph of M has a girth of at least 6.
Based onv,k,1-BDDFs for v=1,3mod6, consider a parity-check matrix H(2) consisting of an 1×ω array of circulant matrices given as follows:(17)H2=M1,M2,…,Mωwhere each Mi, 1≤i≤ω, represents a v×n incidence matrix over GF(2). Clearly, the matrix H(2) satisfies all the required properties of a parity-check matrix. The matrix H(2) is a v×ωn matrix over GF(2) with row and column weights 3ω and 3, respectively. The null space of H(2) gives a binary regular QC-LDPC with minimum distance at least 4, rate lower bounded by (ω-1)/ω, and a girth of at least 6.


## 5. Numerical Results

In this section, the error correction performance of two proposed classes of binary QC-LDPC codes, given in the Sections4.1 and 4.2, is compared with randomly constructed LDPC codes and QC-LDPC codes obtained from design theoretic techniques. Simulation results are obtained by BP iterative decoding with maximum number of iterations equal to 50. Also, Binary-phase-shift-keying(BPSK) transmission is assumed over an AWGN channel.Firstly, suppose we have a(73,3,1)-BDDF for v=1mod6 and GF(73) is the code construction field. Choosing wc=3 and wr=33, we construct a 3×33 subarray of Hb(1) of 72×72 circular permutation matrices over GF(2). Subarray Hb(1)(3,33) is a 216×2376 matrix with row-weight 33 and column-weight 3. The null space of Hb(1)(3,33) gives a (2376,2162) binary QC-LDPC code of rate 0.9110. Assuming BPSK transmission over AWGN channel, the bit-error rate (BER) and block-error rate (BLER) performance of proposed code decoded with Sum-product algorithm (SPA) are shown in Figure 1. Also shown in Figure 1 are the error correcting performances of (2376,2162) QC-LDPC codes constructed from design theoretic techniques in literature [28, 29] and a (2376,2162) QC-LDPC code constructed based on the subsets with distinct differences between the elements [32]. Based on the numerical results, the proposed QC-LDPC codes perform almost the same or better than their competitors in the waterfall region but outperform in the higher SNR region.Figure 1
Error-correcting performance of proposed(2376,2162) QC-LDPC code, a (2376,2162) QC-LDPC code based on cyclic difference families [29], a (2376,2162) QC-LDPC code obtained from cyclic difference families [28], and a (2376,2162) QC-LDPC code constructed based on the subsets with distinct differences between the elements [32].Secondly, suppose we have a(81,3,1)-BDDF for v=3mod6 and GF(81) is the code construction field. Choosing wc=3 and wr=18, we construct a 3×18 subarray of Hb(1) of 80×80 circular permutation matrices over GF(2). Subarray Hb(1)(3,18) is a 240×1440 matrix with row-weight equal to 18, column-weight 3. The null space of Hb(1)(3,18) gives a (1440,1202) binary QC-LDPC code of rate 0.8347. The BER and BLER performance of this code decoded with SPA is shown in Figure 2. Also shown in Figure 2 are the error correcting performances of a (1440,1202) PEG-LDPC code [8], a (1440,1202) QC-LDPC code obtained from cyclic difference families [28], and a (1440,1202) QC-LDPC code constructed from t-designs [31]. Based on the simulation results, the proposed QC-LDPC codes perform as well as their counterparts in the waterfall region but outperform in the higher SNR region.Figure 2
Error-correcting performance of proposed(1440,1202) QC-LDPC code, a (1440,1202) PEG-LDPC code [8], a (1440,1202) QC-LDPC code constructed from t-designs [31], and a (1440,1202) QC-LDPC code obtained from cyclic difference families [28].Finally, suppose we have a(133,3,1)-BDDF for v=1 mod 6. For ω=20, we have the following parameters: v=133, n=2660, wc=3, wr=60, and λ=1. Based on this design, the parity-check matrix H(2) consists of an array of 20133×133 circulant matrices over GF(2). H(2) is a 133×2660 matrix over GF(2) whose null space gives a (2660,2532) binary regular QC-LDPC code with rate 0.9518 and a girth of at least 6. The BER and BLER performance of this code decoded with SPA is shown in Figure 3. Also shown in Figure 3 are the error correcting performances of a (2660,2532) PEG-LDPC code [8], and a (2660,2532) QC-LDPC code constructed based on the subsets with distinct differences between the elements [32] and a (2660,2532) QC-LDPC code obtained from cyclic difference families [28]. Based on the simulation results, the proposed QC-LDPC codes perform as well as their counterparts in the waterfall region but outperform in the higher SNR region.Figure 3
Error-correcting performance of proposed(2660,2532) QC-LDPC code, a (2660,2532) PEG-LDPC code [8], a (2660,2532) QC-LDPC code constructed constructed based on the subsets with distinct differences between the elements [32], and a (2660,2532) QC-LDPC code obtained from cyclic difference families [28].


## 6. Conclusion

In this correspondence, two classes of binary QC-LDPC codes have been constructed based on a special type of combinatorial designs known as block disjoint difference families (BDDFs). Firstly, binary QC-LDPC codes are constructed using binary matrix dispersion of finite field elements based on BDDFs forv=1,3mod6. Secondly, binary QC-LDPC are constructed based on the incidence matrices obtained from (v,3,1)-BDDFs for v=1,3mod6. The proposed QC-LDPC codes have parity-check matrices with column-weight three and their Tanner graphs provide a girth of at least 6. Also, the proposed QC-LDPC codes provide an excellent error performance with iterative decoding over an AWGN channel. Based on the simulation results, the performance analysis shows that the proposed QC-LDPC codes of short and moderate length perform as well as their competitors in lower SNR region but outperform in the higher SNR region. Also, the codes constructed are quasicyclic in nature, so the encoding can be done with simple shift-register circuits with linear complexity.



---

*Source: 7468792-2019-02-03.xml*