# Design of Short, High-Rate DVB-S2-Like  Semi-Regular LDPC Codes

Authors: Luca Barletta; Arnaldo Spalvieri
Journal: Research Letters in Communications
 (2008)

---

## Abstract

This work focuses on high-rate (R>4/5) moderate-length (1000≤n<5000) low-density parity-check codes. High-rate codes allow to maintain good quality of the preliminary decisions
that are used in carrier recovery, while a moderate code length
allows to keep the latency low. The interleaver of the LDPC
matrix that we consider is inspired to the DVB-S2 standard
one. A novel approach for avoiding short cycles is analyzed. A
modified BP decoding algorithm is applied in order to deal with
longer cycles. Simulations and results for the AWGN channel are
presented, both for BPSK signalling and for coded modulation
based on the partition ℤ2/4ℤ2.


---

## Body

## 1. Introduction

An(n,k) LDPC code is a binary block code defined as
the null space of the sparse “parity check” matrix H(n−k)×n,
where H can be viewed as the adjacency matrix of the
bipartite graph G({C,V},E),
the Tanner graph, with hij=1 meaning that the ith c-node is connected to the jth v-node. Richardson et al. [1] studied a method named Density
Evolution (DE) for finding the pair of distributions (λ,ρ),
as n→∞,
that allows to reach the fastest BER convergence at some probability error
target ϵ,
under BP algorithm. For short and moderate-length LDPC codes, that is, for 103≤n<104,
the design of H via DE shows relatively high error floors (@Pb≈10−6), therefore a different approach is required.
The performance can be improved by conditioning the construction of H in such a way that short cycles are avoided. A
technique for the elimination of short cycles in regular LDPC codes has been
recently presented in [2]. However, regular codes are outperformed by irregular
or semiregular codes.Eroz et al. [3] proposed a particular structure of H that leads to irregular codes. This structure
has been adopted for standardization of DVB-S2 applications (the DVB-S2
standard includes 2 versions with n=64800 and n=16200) and belongs to the family of IRA codes
[4].This paper addresses the problem of designing short
DVB-S2-like codes, introducing a new technique for the elimination of cycles of
length 4 and 6.The remainder of the paper is outlined as follows.
Section2 introduces the system models taken under consideration and the
matrix structure of the DVB-S2 standard. Section 3 explains the features
adopted in designing the short-length DVB-S2-like LDPC codes. Section 4 shows
simulation results and some comparisons with short codes designed via DE.
Finally, some conclusions are drawn in Section 5.


## 2. DVB-S2-like Parity-Check Matrix

Here follow some recalls of the parity-check matrix
structure described in [3].The LDPC matrixH is composed of two
submatrices H1(n−k)×k and H2(n−k)×(n−k), H=[H1,H2];
the rightmost one is a lower bidiagonal matrix which offers the advantage of
simple systematic encoding. Specifically, taking modulo-2 additions of
consecutive rows of H2,
such that hi′=hi−1′⊕hi for i=1,…,n−k and h0′=0,
one gets the identity matrix I(n−k).
Another advantage is to avoid short cycles in Tanner graph involving low-degree
v-nodes, leading to improved performance as stated in [1].SubmatrixH1 is built as follows: chosen an opportune value M that divides both n−k and k,
randomly generate the first column of H1, h1,
and get the next M−1 columns by cyclic shifting of j((n−k)/M) positions, respectively, for j=2,…,M.
The second group of M columns is created in the same way, just after
the first columns of the new group have been generated. This procedure allows
to fill the entire submatrix H1.


## 3. Code Design

### 3.1. Short Cycle Elimination

A cycle of
lengthl in the Tanner graph is a set of l/2v-nodes and l/2c-nodes such that a path of consecutive l edges starts from a v-node (c-node) and ends
at the same v-node (c-node).Given two columnshi and hj of H,
a length-4 cycle is formed when the inner product between
the 2 columns is greater than 1:(1)hiT⋅hj≥2for some i,j∈{1,…,n:i≠j}.
This condition suggests a practical way to check the presence of length-4 cycle in a parity-check matrix.Focusing on a column ofH, hi,
let us define the set of the “cyclic-distances” between the nonzero
entries of the ith column(2)Di={dp,q(i):hp,i=1,hq,i=1},where p,q∈{1,…,n−k:p≠q} and(3)dp,q(i)={|p−q|if0<|p−q|≤n−k2,n−k−|p−q|ifn−k2<|p−q|<n−k.For example, if the nonzero
entries of hi are located at the positions {12,23,83} with n−k=100,
then Di={d12,23(i)=11,d12,83(i)=29,d23,83(i)=40}.
Also we have Di={1} for all the columns of H2,
briefly denoted with DH2={1}.Given three columnshi, hj,
and hk,
a length-6 cycle is formed when the sum of two
cyclic-distances of two distinct columns i,j equals a cyclic-distance of the third column k.
An example is shown below (4) with D2=2, D4=1,
and D5=1 a length-6 cycle is formed: d2,3(4)+d1,2(5)=d1,3(2).A complete search for the sets{Di:i=1,…,n} that avoid the presence of length-6 cycles is computationally expensive as n and the average weight of the columns grow.The problem of finding the longest(n,k) LDPC code that is length-4 and length-6 cycle free is described as follows: let D0=DH2 be the initial set of admissible
cyclic-distances (i.e., length-4 and length-6 cycle free); when a new column hc is added in the design of H1 a new set of cyclic-distances Dc is added to the current set Dj according to the following update
rule:(5)Dj+1=Dj∪Dc∪(Dj⊕Dc),as j runs in ℕ0={0,1,2,…};
the objective is to find the maximum j s.t. the set Dj is cycle free. The binary operation A⊕B between two sets A and B is defined as(6)A⊕B={min(|ai−bj|,n−k−|ai−bj|),∀i≠j}.A new column Dc is an eligible set if(7)Dj∩(Dc∪(Dj⊕Dc))=∅.A smart strategy is to choose
the cyclic distances from a class of rest modulo a small integer m:
in this way all cyclic distances will be eligible. For example, choosing the
class of rest 1 modulo m=4,
namely [1]4,
the sum of two cyclic-distances drawn from two distinct columns is in the class [1]4+[1]4=[2]4≠[1]4,
so a length-6 cycle involving 3 columns cannot be created. When the sum of two
distances is greater than (n−k)/2,
the sum is complemented to n−k as illustrated in (3); usually n−k∈[0]4 so n−k−([1]4+[1]4)=[0]4−[2]4=[2]4≠[1]4.
This strategy automatically avoid the creation of length-4 cycles.For some particular choices ofk, M, m, and the average column weight, it is possible
that the total number of eligible cyclic distances is not sufficient to build
all the k/M columns. Actually the total number of original
columns can be reduced to k/M⋅M/(n−k)=k/(n−k),
where (n−k)/M is the cyclic offset between two consecutive
columns in the same c-node M-subset. Without loss of generality, consider
the first c-node M-subset HM={hi,i=1,…,M} and its shifted replica by 1 position denoted with HM≫1.
Obviously, no cycles are created between the two subsets HM and HM≫1;
not only, but also the matrix [HM,HM≫i] for i∈{1,2,…,(n−k)/M−1} does not contain length-4 and length-6 cycles, so an original column can generate ((n−k)/M)⋅M−1=n−k−1 columns without any cycle.


### 3.2.v-Node Degree Distribution

In the semiregular construction thev-node degree
distribution has the form(8)λ(x)=2(n−k)2(n−k)+wvkx+wvk2(n−k)+wvkxwv−1,that is, the submatrix H1 has a constant column degree wv.
The parameter wv can assume only small values to keep the
low-density nature of H and hence few cycles in the factor graph.It is known that there exists a tradeoff between the
performance in the cliff region and the performance in the floor region. In
[5] it is shown that
the floor improves when wv increases. However the weight wv cannot be increased above a maximum value that
depends on the code length and the rate, in order to maintain the low-density
nature of H.
This makes it difficult to obtain good performance in the floor region with
codes of moderate length and high rate.


### 3.3. Modified BP Algorithm

The BP decoding
algorithm is optimal with tree-like factor graph, a condition practically
reached whenn is very large. When the block length
is finite, the BP becomes a suboptimal algorithm in
the sense that it no longer performs MAP decoding [6, 7].
The main idea in order to outperform the BP decoder is to include a procedure
of hard decisions on the v-nodes' posteriors, called decimation. The
modified algorithm resembles that in [8]: in the generic iteration the mutual information from
the v-nodes to c-nodes Ivc is estimated and some hard decisions are taken
on the most reliable v-nodes to reach the desired value of Ivc for the current iteration. The increment ΔIvc between two consecutive iterations is assumed
to be ΔIvc=1/lmax,
such that the expected maximum number of iteration is lmax.


## 3.1. Short Cycle Elimination

A cycle of
lengthl in the Tanner graph is a set of l/2v-nodes and l/2c-nodes such that a path of consecutive l edges starts from a v-node (c-node) and ends
at the same v-node (c-node).Given two columnshi and hj of H,
a length-4 cycle is formed when the inner product between
the 2 columns is greater than 1:(1)hiT⋅hj≥2for some i,j∈{1,…,n:i≠j}.
This condition suggests a practical way to check the presence of length-4 cycle in a parity-check matrix.Focusing on a column ofH, hi,
let us define the set of the “cyclic-distances” between the nonzero
entries of the ith column(2)Di={dp,q(i):hp,i=1,hq,i=1},where p,q∈{1,…,n−k:p≠q} and(3)dp,q(i)={|p−q|if0<|p−q|≤n−k2,n−k−|p−q|ifn−k2<|p−q|<n−k.For example, if the nonzero
entries of hi are located at the positions {12,23,83} with n−k=100,
then Di={d12,23(i)=11,d12,83(i)=29,d23,83(i)=40}.
Also we have Di={1} for all the columns of H2,
briefly denoted with DH2={1}.Given three columnshi, hj,
and hk,
a length-6 cycle is formed when the sum of two
cyclic-distances of two distinct columns i,j equals a cyclic-distance of the third column k.
An example is shown below (4) with D2=2, D4=1,
and D5=1 a length-6 cycle is formed: d2,3(4)+d1,2(5)=d1,3(2).A complete search for the sets{Di:i=1,…,n} that avoid the presence of length-6 cycles is computationally expensive as n and the average weight of the columns grow.The problem of finding the longest(n,k) LDPC code that is length-4 and length-6 cycle free is described as follows: let D0=DH2 be the initial set of admissible
cyclic-distances (i.e., length-4 and length-6 cycle free); when a new column hc is added in the design of H1 a new set of cyclic-distances Dc is added to the current set Dj according to the following update
rule:(5)Dj+1=Dj∪Dc∪(Dj⊕Dc),as j runs in ℕ0={0,1,2,…};
the objective is to find the maximum j s.t. the set Dj is cycle free. The binary operation A⊕B between two sets A and B is defined as(6)A⊕B={min(|ai−bj|,n−k−|ai−bj|),∀i≠j}.A new column Dc is an eligible set if(7)Dj∩(Dc∪(Dj⊕Dc))=∅.A smart strategy is to choose
the cyclic distances from a class of rest modulo a small integer m:
in this way all cyclic distances will be eligible. For example, choosing the
class of rest 1 modulo m=4,
namely [1]4,
the sum of two cyclic-distances drawn from two distinct columns is in the class [1]4+[1]4=[2]4≠[1]4,
so a length-6 cycle involving 3 columns cannot be created. When the sum of two
distances is greater than (n−k)/2,
the sum is complemented to n−k as illustrated in (3); usually n−k∈[0]4 so n−k−([1]4+[1]4)=[0]4−[2]4=[2]4≠[1]4.
This strategy automatically avoid the creation of length-4 cycles.For some particular choices ofk, M, m, and the average column weight, it is possible
that the total number of eligible cyclic distances is not sufficient to build
all the k/M columns. Actually the total number of original
columns can be reduced to k/M⋅M/(n−k)=k/(n−k),
where (n−k)/M is the cyclic offset between two consecutive
columns in the same c-node M-subset. Without loss of generality, consider
the first c-node M-subset HM={hi,i=1,…,M} and its shifted replica by 1 position denoted with HM≫1.
Obviously, no cycles are created between the two subsets HM and HM≫1;
not only, but also the matrix [HM,HM≫i] for i∈{1,2,…,(n−k)/M−1} does not contain length-4 and length-6 cycles, so an original column can generate ((n−k)/M)⋅M−1=n−k−1 columns without any cycle.


## 3.2.v-Node Degree Distribution

In the semiregular construction thev-node degree
distribution has the form(8)λ(x)=2(n−k)2(n−k)+wvkx+wvk2(n−k)+wvkxwv−1,that is, the submatrix H1 has a constant column degree wv.
The parameter wv can assume only small values to keep the
low-density nature of H and hence few cycles in the factor graph.It is known that there exists a tradeoff between the
performance in the cliff region and the performance in the floor region. In
[5] it is shown that
the floor improves when wv increases. However the weight wv cannot be increased above a maximum value that
depends on the code length and the rate, in order to maintain the low-density
nature of H.
This makes it difficult to obtain good performance in the floor region with
codes of moderate length and high rate.


## 3.3. Modified BP Algorithm

The BP decoding
algorithm is optimal with tree-like factor graph, a condition practically
reached whenn is very large. When the block length
is finite, the BP becomes a suboptimal algorithm in
the sense that it no longer performs MAP decoding [6, 7].
The main idea in order to outperform the BP decoder is to include a procedure
of hard decisions on the v-nodes' posteriors, called decimation. The
modified algorithm resembles that in [8]: in the generic iteration the mutual information from
the v-nodes to c-nodes Ivc is estimated and some hard decisions are taken
on the most reliable v-nodes to reach the desired value of Ivc for the current iteration. The increment ΔIvc between two consecutive iterations is assumed
to be ΔIvc=1/lmax,
such that the expected maximum number of iteration is lmax.


## 4. Results

### 4.1. BPSK Signalling

In the BPSK system, the receiver computes thea priori metrics for
the LDPC decoder(9)L0=2σ2y,where y is the received vector and σ2=N0/2 is the variance per dimension of the AWG
noise. Several LDPC codes are compared, that are different for code rate (R=9/10 and R=4/5), code length (n=1000 and n=5000). Also, we considered LDPC codes designed via
DE. The results obtained with DE are not reported here due to the poor
performance in the floor region.In Figure1, there is a comparison between the
original BP decoding algorithm and the modified version, working on the same
semiregular code with n=5000, R=0.8, and wv=8.
The modified version of the BP algorithm exploits the original version with a
constant gain in the cliff region.Figure 1
Word error rate (WER) and bit error rate (BER) of a semiregular LDPC code (n=5000, R=0.8,
and wv=8) with BP decoding and with the modified BP
algorithm (mBP).In Figure2 are plotted 8 BER curves versus Eb/N0=1/8Rσ2 in dB. The solid curves represent the
performance of the codes designed with the short cycle elimination procedure,
while the dashed curves represent the performance of the codes designed as
described in Section 2. The code with n=5000 and R=9/10 is 1 dB from capacity and the code with R=4/5 is about 1.6 dB from capacity (@Pb=10−5); the floor does not appear up to Pb=10−7.Figure 2
Bit
error rate (BER) curves of some semiregular LDPC codes with DVB-S2-like
structure. BPSK signalling.


### 4.2. Coded Modulation

Let us consider
the coded modulation based on the 16-way partitionℤ2/4ℤ2 where log216=4 coded bits c=[c1,c2,c3,c4] address one coset leader in [ℤ2/4ℤ2], and log2(128/16)=3 uncoded bits u=[u1,u2,u3] address one out of 8 subconstellations. The coded vector c is drawn from an LDPC encoder of rate R=k/n;
the normalized redundancy is ρ=4((n−k)/n)[b/2D] and the volume to noise ratio (VNR)
is(10)α2=2ρ2πeσ2.As suggested in [9] it has been adopted a partial Gray mapping rule.At the receiver metrics for thejth received symbol and each of the 4 Gray-mapped bits are computed according
to(11)L0,j(i)=12σ2(|yj−z0(i)|2−|yj−z1(i)|2)for i=1,…,4 and j=1,…,n/4,
such that 4⋅n/4=n metrics are provided to the LDPC decoder.Four different LDPC codes are compared; they differ
for code rate (R=9/10 and R=4/5 lead to overall redundancies of ρ=0.4[b/2D] and ρ=0.8[b/2D], resp.), code length (n=2000 and n=6000 mean N=500 and N=1500 2D symbols, resp.). The LDPC decoder computes lmax=30 iterations of the modified BP algorithm. In
Figure 3 are plotted 4 BER performance curves versus SNR in dB. The
longer semiregular code shows good performance and error floor below Pb=10−8.
Figure 4 shows some WER curves versus the volume to noise ratio α2,
which is recalled in (10), and the sphere lower bound on the WER for the finite
dimensionality of the lattice [10].Figure 3
Bit
error rate (BER) curves of some semiregular LDPC codes with DVB-S2-like
structure. 128-CR coded modulation.Figure 4
Word error rate (WER)
curves versus the volume to noise ratio (α2) of some semiregular LDPC codes. Coded
modulation based on the partition ℤ2/4ℤ2.


## 4.1. BPSK Signalling

In the BPSK system, the receiver computes thea priori metrics for
the LDPC decoder(9)L0=2σ2y,where y is the received vector and σ2=N0/2 is the variance per dimension of the AWG
noise. Several LDPC codes are compared, that are different for code rate (R=9/10 and R=4/5), code length (n=1000 and n=5000). Also, we considered LDPC codes designed via
DE. The results obtained with DE are not reported here due to the poor
performance in the floor region.In Figure1, there is a comparison between the
original BP decoding algorithm and the modified version, working on the same
semiregular code with n=5000, R=0.8, and wv=8.
The modified version of the BP algorithm exploits the original version with a
constant gain in the cliff region.Figure 1
Word error rate (WER) and bit error rate (BER) of a semiregular LDPC code (n=5000, R=0.8,
and wv=8) with BP decoding and with the modified BP
algorithm (mBP).In Figure2 are plotted 8 BER curves versus Eb/N0=1/8Rσ2 in dB. The solid curves represent the
performance of the codes designed with the short cycle elimination procedure,
while the dashed curves represent the performance of the codes designed as
described in Section 2. The code with n=5000 and R=9/10 is 1 dB from capacity and the code with R=4/5 is about 1.6 dB from capacity (@Pb=10−5); the floor does not appear up to Pb=10−7.Figure 2
Bit
error rate (BER) curves of some semiregular LDPC codes with DVB-S2-like
structure. BPSK signalling.


## 4.2. Coded Modulation

Let us consider
the coded modulation based on the 16-way partitionℤ2/4ℤ2 where log216=4 coded bits c=[c1,c2,c3,c4] address one coset leader in [ℤ2/4ℤ2], and log2(128/16)=3 uncoded bits u=[u1,u2,u3] address one out of 8 subconstellations. The coded vector c is drawn from an LDPC encoder of rate R=k/n;
the normalized redundancy is ρ=4((n−k)/n)[b/2D] and the volume to noise ratio (VNR)
is(10)α2=2ρ2πeσ2.As suggested in [9] it has been adopted a partial Gray mapping rule.At the receiver metrics for thejth received symbol and each of the 4 Gray-mapped bits are computed according
to(11)L0,j(i)=12σ2(|yj−z0(i)|2−|yj−z1(i)|2)for i=1,…,4 and j=1,…,n/4,
such that 4⋅n/4=n metrics are provided to the LDPC decoder.Four different LDPC codes are compared; they differ
for code rate (R=9/10 and R=4/5 lead to overall redundancies of ρ=0.4[b/2D] and ρ=0.8[b/2D], resp.), code length (n=2000 and n=6000 mean N=500 and N=1500 2D symbols, resp.). The LDPC decoder computes lmax=30 iterations of the modified BP algorithm. In
Figure 3 are plotted 4 BER performance curves versus SNR in dB. The
longer semiregular code shows good performance and error floor below Pb=10−8.
Figure 4 shows some WER curves versus the volume to noise ratio α2,
which is recalled in (10), and the sphere lower bound on the WER for the finite
dimensionality of the lattice [10].Figure 3
Bit
error rate (BER) curves of some semiregular LDPC codes with DVB-S2-like
structure. 128-CR coded modulation.Figure 4
Word error rate (WER)
curves versus the volume to noise ratio (α2) of some semiregular LDPC codes. Coded
modulation based on the partition ℤ2/4ℤ2.


## 5. Conclusion

The design of the moderate length instance of the
DVB-S2-like parity-check matrix has been considered. Several codes designed
with a semiregular approach are worked out and their performance is obtained by
running few iterations of the decoding algorithm. The proposed edge assignment
and the modified BP algorithm, with a decimation procedure, allow to lower the
error floor compared to the same codes designed via density evolution.



---

*Source: 324503-2009-02-11.xml*