1

Multilevel LDPC Lattices with Efficient
Encoding and Decoding and a Generalization
of Construction D0
arXiv:1712.08201v1 [] 21 Dec 2017

Paulo Ricardo Branco da Silva and Danilo Silva, Member, IEEE

Abstract
Lattice codes are elegant and powerful structures that not only can achieve the capacity of the
AWGN channel but also are a key ingredient to many multiterminal schemes that exploit linearity
properties. However, constructing lattice codes that can realize these benefits with low complexity is
still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for
multilevel binary LDPC lattices constructed via Construction D0 whose complexity is linear in the total
number of coded bits. Moreover, a generalization of Construction D0 is proposed that relaxes some of
the nesting constraints on the component codes, leading to a simpler and improved design. Based on this
construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage
lattice decoding is comparable to that of polar lattices on the power-unconstrained AWGN channel and
close to that of conventional (non-lattice) coded modulation schemes on the power-constrained AWGN
channel.

Index Terms
Check splitting, Construction D0 , lattice codes, lattices, low-density parity-check (LDPC) codes,
multilevel coding, multistage decoding, Poltyrev setting, progressive edge-growth (PEG) algorithm.
This work supported in part by CAPES-Brazil under Grant 1587757 and in part by CNPq-Brazil under Grants 429097/2016-6
and 310343/2016-0. A preliminary version of this paper (in Portuguese) was presented at the XXXV Simpósio Brasileiro de
Telecomunicações e Processamento de Sinais, São Pedro, Brazil, September 2017.
P. R. B. da Silva and D. Silva are with the Department of Electrical and Eletronic Engineering, Federal University of Santa
Catarina, Florianopolis-SC, Brazil (e-mails: pauloricardo.branco@gmail.com; danilo.silva@ufsc.br).
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which
this version may no longer be accessible.

2

I. I NTRODUCTION
Lattice codes [1], the analogue of linear codes in the Euclidean space, have attracted an increasing
amount of attention in recent years. Their rich structure provides an elegant and powerful solution not only
to achieving the capacity of the additive white Gaussian noise (AWGN) channel [2], [3], but also to many
multiterminal information theory problems that exploit linearity properties. Applications include (see [1]
and references therein): distributed source coding [4], physical-layer security [5], and communication over
Gaussian networks [1]—in particular, lattice codes are essential to the compute-and-forward strategy for
relay networks [6] and to integer-forcing methods for MIMO channels [7].
Despite their theoretical success, constructing lattice codes that can realize their benefits with low
complexity has remained a challenging problem. In particular, practical lattice codes that can match
the encoding and decoding speeds of state-of-art channel codes combined with bit-interleaved coded
modulation (BICM) [8], [9] are yet to be proposed. Part of the reason may have to do with the
computational advantages of binary codes, which cannot always be exploited in lattice constructions.
Indeed, much of the literature on lattice codes, including most proofs of achievable rates, considers
lattices constructed by the so-called Construction A [1], [3], [10]–[12]. The basic (real-valued) version
of this construction relies on a single p-ary linear code (where p is a prime) used in conjunction with
p-PAM modulation. For high spectral efficiency, p needs to be large. Unfortunately, even if the underlying

code has encoding and decoding complexity that is linear in the block length, the computational cost
of processing a p-ary symbol is much higher in practice than log2 p times that of a binary symbol,
leading to a comparatively high overall complexity. For instance, the belief propagation decoder in [11]
has complexity O(p2 n). The situation is similar with lattices that are designed and decoded directly
in Euclidean space, such as low-density lattice codes (LDLC) [13], [14], whose decoder must process
continuous functions.
Alternative lattice constructions that leverage the use of binary codes are the multilevel Construction D
and Construction D0 [10], which rely on a family of L nested binary linear codes used in conjunction with
2L -PAM modulation. The former (latter) describes a lattice through the generator (parity-check) matrices

of the nested component codes. When used together with multistage decoding (MSD) [15], [16], each
component code can be individually encoded and decoded over the binary field, leading to a significant
complexity reduction—at the price of an increased delay due to the sequential operation.
Construction D has been used in [17] to produce turbo lattices and in [18] to construct polar lattices;
the latter are shown to be capacity-achieving for the AWGN channel, as well as AWGN-good (i.e.,
they achieve Poltyrev’s limit on density of lattice points relative to noise level on a power-unconstrained

3

AWGN channel [19]). Their encoding and decoding complexity, however, is O(Ln log n), which may still
be excessively high if n is large. A low-complexity alternative to polar codes are low-density parity-check
(LDPC) codes [20], which are known to be encodable and decodable in linear time, despite not being
provably capacity-achieving. Thus, constructing low-complexity capacity-approaching multilevel LDPC
lattices seems to be a relevant problem.
Multilevel LDPC lattices with Construction D0 were intially proposed in [21] and subsequently extended
in [22] to irregular codes; however, these works consider only joint decoding1 of the component codes,
whose complexity is exponential in L, while the encoding complexity is not addressed. Multistage
decoding of LDPC lattices is considered in [25], but the proposed construction is actually based on
Construction D applied to the generator matrices of the component LDPC codes, which are generally
dense, leading to high-complexity encoding. Single-level LDPC lattices with linear-time encoding and
decoding are proposed in [26], but since all the higher levels are uncoded, their performance in terms of
block error rate quickly degrades as the block length increases.
To the best of our knowledge, multilevel LDPC lattices with efficient encoding and decoding have not
been proposed before and filling this gap is the purpose of this paper. The current state of the literature
may be explained by the following major challenges found with Construction D0 :
•

Since Construction D0 defines a lattice indirectly through parity-check equations, which in turn couple
the individual levels in non-binary modular equations, the component codes cannot be independently
encoded. The influence of the encoding of a level on the subsequent ones is clear when encoding
is done through a generator matrix of the lattice, as in Construction D, but such a matrix is absent
in Construction D0 (and normally should not be computed if one wishes to efficiently encode an
LDPC code);

•

For the same reason, multistage decoding would in principle require the influence of all past levels
to be removed—by re-encoding and subtracting from the received vector—before the current level
is decoded. Thus, an efficient encoding would be required for multistage decoding to be efficient.

•

Even if we ignore the issue of efficient encoding, Construction D0 requires not only the component
codes, but also their parity-check matrices, to be nested (i.e., one matrix must contain the other
as a submatrix), a constraint that makes it very hard to design good degree distributions for the
component LDPC codes. In particular, the lowest-rate component code must have a significantly
higher average variable-node degree than the highest-rate component code, and check-concentrated

1

Note that the multistage decoder mentioned in [22] is unsuitable for Construction D0 since it relies on independent encoding

of levels through the Code Formula [23], which does not generally produce lattices [24].

4

degree distributions become impossible. Consequently, Construction D0 LDPC lattices with two or
more levels tend to exhibit a poor performance.
We tackle these problems through a reinterpretation of Construction D0 . Our main technical contributions are summarized as follows:
•

We present two alternative descriptions of Construction D0 , one of which enables sequential encoding
of the component codes. The contribution of past levels on the current level is subsumed by a
syndrome vector that the current codeword must satisfy. Apart from that, the actual encoding of
a level is done entirely over the binary field. Moreover, as the syndrome vector can be computed
directly from parity-check equations, the need for explicit re-encoding is avoided for multistage
decoding.

•

We discuss how existing linear-time algorithms for encoding and decoding LDPC codes can be
adapted to handle affine (i.e., cosets of linear) LDPC codes without a significant increase of complexity. It follows that multilevel LDPC lattices can be always be decoded with complexity O(Ln)
and can be encoded also with complexity O(Ln) if the component codes admit linear-time encoding.

•

We propose a generalization of Construction D0 that relaxes the nesting constraints on the paritycheck matrices of the component codes (which themselves must remain nested). This new construction significantly enlarges the design space for good component codes (or, strictly speaking, for good
component decoders, as the difference between the two constructions is only in the allowed paritycheck matrices), enabling the design of multilevel LDPC lattices with much better performance.
This contribution may also be of independent interest from a mathematical perspective.

•

We propose an efficient method to construct the parity-check matrices of the remaining component
codes given only the parity-check matrix of the highest-rate LDPC code, while respecting the
conditions of the generalized Construction D0 . We also present a variation of this basic method
aimed at maximizing girth and another that enables linear-time encoding.

In addition, we present examples of linear-time encodable and decodable two-level LDPC lattices
designed for Poltyrev’s scenario of a power-unconstrained AWGN channel, as well as for the conventional
coded modulation scenario of an AWGN channel constrained to PAM modulation with equiprobable
signaling. Simulation results show that, in the former case, the proposed lattices achieve performance
comparable to that of polar lattices, while, in the latter case, they achieve performance only slight inferior
to that of conventional coded modulation without a lattice constraint. This last result is based on the use
of a lattice decoder, a simpler decoder that ignores the constellation boundaries. If, instead, a conventional
multilevel decoder is used, then the performance becomes indistinguishable from that of conventional

5

multilevel codes.
It is worth mentioning that, although we have opted to use binary codes for simplicity and computational
efficiency, our results can be straightforwardly generalized to a general prime p, as well as to Complex
Construction D0 lattices over a complex ring [10], [23], [27].
The remainder of this paper is organized as follows. Section II reviews basic concepts on lattices, while
Section III reviews the channel models considered in the paper. In Section IV, we present alternative
descriptions of Construction D0 , which are then used in Section V to derive efficient multilevel encoding
and multistage decoding for Construction D0 LDPC lattices. In Section VI, a generalization of Construction
D0 is proposed that reduces the nesting constraints to a minimum while still satisfying the requirements for
sequential encoding. In Section VI, we propose and extend an efficient method to construct Generalized
Construction D0 LDPC lattices, which we call check splitting. Section VIII presents design examples and
corresponding simulation results and Section IX presents our conclusions.
II. P RELIMINARIES
In the following, we review basic concepts on lattices, in particular, Construction D0 . For further details,
we refer the reader to [1], [10], [16].

A. Lattices
A lattice Λ ⊆ Rn is a discrete subgroup of Rn . This implies that Λ is closed to integer linear
combinations and may be expressed as Λ = {uG, u ∈ Zn }, where G ∈ Rn×n is a generator matrix.
A fundamental region of Λ is a set RΛ ⊆ Rn such that any x ∈ Rn can be uniquely expressed
as x = λ + r, where λ ∈ Λ and r ∈ RΛ . Every fundamental region has the same volume, which is
denoted by V (Λ). A fundamental region RΛ defines a quantizer QΛ : Rn → Λ and a modulo-Λ operation
Rn → RΛ as QΛ (x) = λ and x mod Λ = r, respectively, where x = λ + r. In particular, the Voronoi
region of Λ (around the origin) is the set VΛ of points that are closer to 0 than to any other lattice point,
with ties decided arbitrarily but such that VΛ is a fundamental region.
The second moment (per dimension) of Λ is defined as PΛ =

1
2
n E[kxk ],

where x is a random

vector uniformly distributed over VΛ , and the normalized second moment of Λ is defined as G(Λ) =
PΛ /V (Λ)2/n .

A sublattice Λ0 ⊆ Λ is a subset of Λ which is itself a lattice. If Λ and Λ0 ⊆ Λ are lattices, then
C = Λ ∩ RΛ0 is said to be a nested lattice code. Note that |C| = V (Λ0 )/V (Λ).

6

B. Figures of Merit
The probability of error Pe (Λ, σ 2 ) of a lattice Λ ⊆ Rn is defined as the probability of a random
Gaussian vector z ∈ Rn with independent entries of zero mean and variance σ 2 falling outside VΛ .
Given that the density of Λ is inversely proportional to V (Λ), it is convenient to define the volumeto-noise ratio (VNR) as2
γΛ (σ) ,

V (Λ)2/n
2πeσ 2

(1)

which gives a measure of the density of Λ relative to the noise level.
It is well-known [1], [16] that, if Pe (Λ, σ 2 ) ≈ 0, then γΛ (σ) is necessarily greater than 1, or 0 dB.
This fundamental limit is known as the Poltyrev limit or the sphere bound. On the other hand, for all
σ 2 > 0 and all Pe > 0, there exists a sequence of n-dimensional lattices with Pe (Λ, σ 2 ) ≤ Pe such that
limn→∞ γΛ (σ) = 1. Lattices with this property are said to be good for AWGN coding.

C. Construction D0
Let ϕ : Z → Z/2Z ∼
= F2 be the natural reduction homomorphism, extended to vectors and matrices
in a component-wise fashion. Let C0 ⊆ C1 ⊆ · · · ⊆ CL−1 ⊆ Fn2 be a family of nested linear codes. For
` = 0, . . . , L − 1, let k` be the dimension of C` , let R` = k` /n, and let m` = n − k` . For convenience,

define mL = 0. Note that
m0 ≥ m1 ≥ · · · ≥ mL−1 ≥ mL .

Let h1 , . . . , hm0 ∈ {0, 1}n and



h1


 . 
H` =  .. 


hm`

(2)

` ×n
be such that3 ϕ (H` ) ∈ Fm
is a parity-check matrix for C` , for ` = 0, . . . , L − 1. The application of
2

Construction D0 [10] results in the lattice
Λ = {v ∈ Zn : hj vT ≡ 0

(mod 2`+1 ),

m`+1 < j ≤ m` , 0 ≤ ` ≤ L − 1}.

(3)

Note that Λ = C + 2L Zn , where
C = Λ ∩ [0, 2L )n

(4)

2

The VNR is also commonly defined [1] without the term 2πe in the denominator.

3

Note that we define hi and H` over Z rather than over F2 , which allows us to simplify notation when dealing with lattices.

7

is a lattice code. In particular, V (Λ) = 2n(L−R) , where
R = R(C) ,

1
log2 |C|.
n

(5)

If matrices H0 , . . . , HL−1 are sparse, i.e., if C0 , . . . , CL−1 are LDPC codes, then Λ is said to be an
LDPC lattice [21].
III. C HANNEL M ODELS
In this section we describe the channels assumed for transmission with and without power constraint.

A. Power-Unconstrained Channel
In the design of lattice codes, one is often interested in addressing the coding problem separately
from the shaping problem. This leads to the so-called (power-)unconstrained AWGN channel studied by
Poltyrev [19], over which any lattice point may be transmitted without restrictions. In that case, the main
performance metric of a lattice is its probability of error for a given VNR.
A practical way to approach this problem, which often simplifies the decoding and the code design,
is the two-level partition proposed in [16]. Given a lattice Λ ⊆ Rn , a sublattice Λ0 ⊆ Λ is chosen such
that the modulo-Λ0 operation (as well as the enumeration of elements of Λ0 ) is easy to implement. In
this manner, Λ can be partitioned as Λ = C + Λ0 , where C = Λ ∩ RΛ0 is a lattice code and RΛ0 is a
fundamental region defining the modulo-Λ0 operation.
In order to transmit x ∈ Λ, vectors c ∈ C and λ0 ∈ Λ0 are chosen independently. The point x is
transmitted as the sum of these two components, i.e., x = c + λ0 . Let y = x + z be the channel output,
where z ∈ Rn is a white Gaussian noise vector with variance σ 2 per component. Decoding from y is as
follows. First,
r = y mod Λ0 = c + z mod Λ0

(6)

is computed, eliminating the influence of λ0 . Next, a decoder for code C is applied on the modulo-Λ0
equivalent channel described above, from which the estimate ĉ ∈ C is obtained. Finally, ĉ is subtracted
from y, resulting in
y0 = y − ĉ = (c − ĉ) + λ0 + z,

(7)

and a decoder for Λ0 is applied, obtaining the estimate λˆ0 ∈ Λ0 and, consequently, x̂ = ĉ + λˆ0 .
It follows by the union bound that
Pe (Λ, σ 2 ) ≤ Pe (C, σ 2 , Λ0 ) + Pe (Λ0 , σ 2 )

(8)

8

where Pe (C, σ 2 , Λ0 ) is the probability of error for the code C when used on the channel in (6). For brevity,
we denote Pe (C, σ 2 , Λ0 ) simply by Pe (C, σ 2 ) when the modulo channel is clear from the context.
In particular, if Λ ⊆ Zn is an L-level Construction D0 lattice, we naturally choose Λ0 = 2L Zn and
R(Λ0 ) = [0, 2L )n , so that the mod Λ0 operation becomes simply mod 2L over Z.

B. Power-Constrained Channel
In the case of the conventional, power-constrained AWGN channel, one can directly reuse the results
of the previous subsection by transforming the channel into a modulo-lattice additive noise channel, as
described in [1], [3].
Let Λ ⊆ Rn be a lattice and let Λ0 ⊆ Λ be a sublattice with Voronoi region V(Λ0 ). Let X =
(Λ + d) ∩ V(Λ0 ) be a dithered lattice code [1], where d ∈ Rn is a shift or dither vector. The channel

output is given by y = x + z, where x ∈ X is the transmitted vector and z is a white Gaussian noise
vector with variance σ 2 per component. Define P = n1 E[kxk2 ] and SNR = P/σ 2 .
Let C = Λ ∩ RΛ0 be a lattice code, where RΛ0 is a fundamental region of Λ0 defining some convenient
modulo-Λ0 operation. Note that we can equivalently express
x = c + d + λ0

(9)

where c ∈ C is a codeword and λ0 ∈ Λ0 is a shaping vector chosen such that x ∈ V(Λ0 ).
At the receiving end, lattice decoding is applied after MMSE scaling and removal of the dither vector.
More precisely, first the vector
r = αy − d mod Λ0 = c + zeff mod Λ0

(10)

zeff = (α − 1)x + αz

(11)

is computed, where

is the effective noise and
α=

SNR
1 + SNR

is the MMSE coefficient. Then, a decoder for code C is applied on the modulo-Λ0 equivalent channel (10),
which effectively ignores the shaping region. It follows that the probability of error is upper bounded by
2 ), where
Pe (C, σeff
2
σeff
= (α − 1)2 P + α2 σ 2

(12)

is the per-component variance of zeff . Note that the special case α = 1 (or SNR → ∞) reduces to the
channel in (6).

9

It is shown in [3] that, if the dither is chosen uniformly at random over RΛ0 , such a scheme can
approach the AWGN channel capacity to within

1
2

log2 (2πeG(Λ0 )) bits.

Here, we adopt a fixed dither4 and choose RΛ0 = V(Λ0 ) − d so that λ0 = 0 in (9), leading to a
straightforward encoder. Moreover, if Λ ⊆ Zn is an L-level Construction D0 lattice, we choose Λ0 = 2L Zn ,
d = (d, . . . , d), d = −(2L − 1)/2 and R(Λ0 ) = V(Λ0 ) − d = [0, 2L )n . This implies that X ⊆ Mn , where

the set M = {d + i : i = 0, . . . , 2L − 1} can be interpreted as a 2L -PAM constellation. We also assume

that the marginal distribution of the entries of x is uniform over M, leading to P = 22L − 1 /12.
Thus, our approach fits within the realm of (and can be compared to) unshaped coded modulation,
while at the same time providing a lattice codebook structure suitable for lattice decoding, which can be
exploited in multiterminal problems.
IV. A LTERNATIVE D ESCRIPTIONS FOR C ONSTRUCTION D0
In this section, alternative descriptions for Construction D0 are proposed, which are essential for the
remaining results of this paper.
Theorem 1 (Matrix Description): Let Λ be a lattice defined by (3). Then
n
o
Λ = v ∈ Zn : H` vT ≡ 0 (mod 2`+1 ), 0 ≤ ` ≤ L − 1 .

(13)

Proof: Let Λ and Λnew denote the sets defined by (3) and (13), respectively. Note that Λnew can be
equivalently expressed as
Λnew = {v ∈ Zn : hj vT ≡ 0 (mod 2`+1 ),
0 < j ≤ m` , 0 ≤ ` ≤ L − 1}.

(14)

Clearly, Λnew ⊆ Λ, since m`+1 ≥ 0, for all 0 ≤ ` ≤ L − 1. We now prove Λ ⊆ Λnew . Let v ∈ Λ. Thus,
hj vT ≡ 0

(mod 2i+1 )

for all mi+1 < j ≤ mi and all 0 ≤ i ≤ L − 1. It follows that
hj vT ≡ 0

(mod 2`+1 )

for all 0 ≤ ` ≤ i, all mi+1 < j ≤ mi and all 0 ≤ i ≤ L − 1, or, equivalently, for all mi+1 < j ≤ mi , all
` ≤ i ≤ L − 1 and all 0 ≤ ` ≤ L − 1, or, equivalently, for all 0 = mL < j ≤ m` and all 0 ≤ ` ≤ L − 1.

Thus, v ∈ Λnew . This proves that Λ ⊆ Λnew , and thus Λnew = Λ, completing the proof.

4

See [1, Section 9.9] for a discussion on fixed dithers.

10

Lemma 1: Let H0 , . . . , HL−1 be matrices satisfying (2), let v ∈ Zn , and let 1 ≤ ` ≤ L − 1. If
H`−1 vT ≡ 0 (mod 2` ), then H` vT ≡ 0 (mod 2` ).

Proof: The proof follows immediately since, by definition, H` is a submatrix of H`−1 .
We state the following result with slight generality since this will be useful later on. For convenience,
define an empty summation as the all-zero vector with the appropriate size.
Theorem 2 (Sequential Encoding): Let C = Λ ∩ [0, 2L )n be a lattice code carved from a lattice Λ
defined by (13). Suppose that the corresponding matrices H0 , . . . , HL−1 satisfy Lemma 1 and are such
` ×n
that ϕ(H` ) ∈ Fm
, ` = 0, . . . , L − 1, are full-rank. Consider the following procedure:
2

1) Sequentially, for ` = 0, 1, . . . , L − 1, choose some vector c` ∈ C` (s` ), where

C` (s` ) , v ∈ {0, 1}n : H` vT ≡ s`

(mod 2)

(15)

and s` ∈ {0, 1}m` is given by
−H`

s` =

2) Finally, compute c =

PL−1
`=0

P`−1
i=0
2`

2i cT
i

mod 2.

(16)

2` c` .

The procedure described above is well-defined. Moreover, let Cseq be the set of all possible vectors
c ∈ Zn produced by this procedure. Then Cseq = C .

Proof: First, we prove that the procedure is well-defined, i.e., that
H`

`−1
X

2i cT
i ≡0

(mod 2` )

(17)

i=0

for ` > 0, so that s` can always be computed. Note that a solution for c` always exists, since H` is
full-rank modulo 2. We proceed by induction. Note that the base case ` = 0 is already established by
definition, since s0 = 0. Let ` > 0 and suppose that c0 , . . . , c`−1 and s`−1 have been computed. Thus,
2`−1 s`−1 + H`−1

`−2
X

`
2i cT
i =2 a

i=0

for some a ∈

Zm`−1 .

But

H`−1 cT`−1

≡ s`−1 (mod 2), i.e., H`−1 cT`−1 = s`−1 + 2b, for some b ∈ Zm`−1 .

It follows that
`

`−1

2 a=2

(H`−1 cT`−1

− 2b) + H`−1

`−2
X
i=0

= −2` b + H`−1

`−1
X

2i cT
i

i=0

or simply
H`−1

`−1
X
i=0

2i cT
i ≡0

(mod 2` ).

2i cT
i

11

Now (17) follows by Lemma 1, completing the induction.
Since the procedure is well-defined, the set Cseq is also well-defined. We now prove that Cseq = C .
First, let c ∈ C . Then, for all 0 ≤ ` ≤ L − 1,
0 ≡ H` cT
≡ H`

(mod 2`+1 )

L−1
X

2i cTi

(mod 2`+1 )

i=0

≡

H` 2` cT`

+ H`

`−1
X

2i cTi

(mod 2`+1 )

i=0

and therefore
H` cT`

≡

−H`

≡ s`

P`−1
i=0
2`

2i cTi

(mod 2)

(mod 2).

Thus, c can be generated by the procedure described, which implies C ⊆ Cseq . Now, let c ∈ Cseq . For all
0 ≤ ` ≤ L − 1, we have that
H ` cT
`

≡ s` ≡

−H`

P`−1
i=0
2`

2i cT
i

(mod 2)

which implies
`

2

H` cT
`

+ H`

`−1
X

`+1
2i cT
a
i =2

i=0

for some a ∈

Zm` ,

and therefore
H` cT ≡ H`

`
X

2i cTi

(mod 2`+1 )

i=0

≡0

(mod 2`+1 ).

It follows that c ∈ C . This proves that Cseq ⊆ C and thus C = Cseq , completing the proof.
The following result has been used in the literature (e.g., [21], [22]) without an explicit proof.5 Here,
the proof follows immediately from Theorem 2.

5

The classical result in [10, Chapter 8, Theorem 14] assumes that “some rearrangement of h1 , . . . , hm0 forms the rows of an

upper triangular matrix,” which allows the linear congruences to be independently solved. However, this assumption is ommitted
in the definition of Construction D’ that commonly appears in the literature, such as in [21], [22], [24] and here. While it is
always possible to find some h1 , . . . , hm0 of this form given a family of nested codes, an explicit proof was lacking that the
result still holds even for specific h1 , . . . , hm0 that are not of this form.

12

Corollary 1: Let C satisfy the conditions of Theorem 2, and let C` be the null space of ϕ(H` ), for
` = 0, . . . , L − 1. Then
|C| = |C0 | · · · · · |CL−1 |

(18)

R(C) = R(C0 ) + · · · + R(CL−1 ).

(19)

and therefore

Example 1: Let C be the code described in Theorem 2 for L = 3 and matrices


1 1 1 1




H0 = 1 0 1 0


1 1 0 0


1 1 1 1

H1 = 
1 0 1 0
h
i
H2 = 1 1 1 1 .
We construct c ∈ C by sequential encoding through the vectors c0 , c1 , c2 ∈ {0, 1}4 . First, we choose
some c0 satisfying
H0 cT
0 ≡ 0 (mod 2)
T
for instance, c0 = (1, 1, 1, 1). Then, we compute s1 = −H1 cT
0 /2 mod 2 = (0, 1) and choose some c1

satisfying
H1 cT
1 ≡ s1

(mod 2)

T
for instance, c1 = (0, 1, 1, 0). Next, we compute s2 = −(H2 2cT
1 + H2 c0 )/4 mod 2 = 0 and choose

some c2 satisfying
H2 cT
2 ≡ s2

(mod 2)

for instance, c2 = (0, 0, 1, 1). Finally, we obtain c = c0 + 2c1 + 4c2 = (1, 1, 1, 1) + (0, 2, 2, 0) +
(0, 0, 4, 4) = (1, 3, 7, 5). Note that c = (1, 3, 5, 7) satisfies all conditions in (13), so c ∈ C .

V. E NCODING AND D ECODING
In this section, we show that, if the component codes of an LDPC lattice admit efficient encoding and
decoding, then the same claim is valid for the corresponding lattice code.

13

A. Systematic Encoding
Let us assume ` ∈ {0, . . . , L − 1} and suppose that, for i = 0, . . . , ` − 1, the vectors xi ∈ C(si ) have
been previously calculated. Given an information vector u ∈ {0, 1}k` , we wish to determine the vector
h
i
p ∈ {0, 1}m` such that c` = u p ∈ C` (s` ).
First, we note that s` in (16) can always be calculated efficiently, granted that H` is a sparse matrix.
Suppose, possibly through row and column permutations, that H` can be expressed in the form


A B T
,
H` = 
(20)
C D E
where A ∈ {0, 1}(m` −g)×(n−m` ) , B ∈ {0, 1}(m` −g)×g , T ∈ {0, 1}(m` −g)×(m` −g) is lower triangular,
C ∈ {0, 1}g×(n−m` ) , D ∈ {0, 1}g×g , E ∈ {0, 1}g×(m` −g) , and g is small in comparison to n. Here, g

is called the gap of the approximate lower triangular form. For the case where s` = 0, i.e., when it is
desired to obtain H` cT
` ≡ 0 (mod 2), it is shown in [28] that the calculation of p can be performed
with complexity of order O(n + g 2 ) = O(n).
For a generic s` , we can rewrite the congruence in (15) as
T

H0` c0` ≡ 0

where H0` = [−s`

(mod 2),

(21)

H` ] and c0` = [1

0
c` ]. In this fashion, we
 observe
 that H` can
 still be expressed in
h
i
A0
A
, while c0 = u0 p ,
the form (20), with the first block of columns replaced by   = −s`
`
C0
C
h
i
with u0 = 1 u . These changes do not alter the order of complexity. In fact, assuming that s` has

already been calculated, it is easily observed in Tables I and II of [28] that the only modification needed
on the algorithm of [28] is an increase of m` additions.
Under these hypotheses, we conclude that the lattice code C admits systematic encoding with complexity
O(Ln).

B. Multi-Stage Decoding
P
`
n
Let c = L−1
`=0 2 c` ∈ C be the transmitted codeword, where c` ∈ {0, 1} , and let r = c + z mod
2L Zn be the received vector, where z is a noise vector of variance σ 2 per component. Note that the

above definition describes the power-unconstrained channel; for the power-constrained version, we simply
2 , as discussed in Section III-B.
replace z with zeff and σ 2 with σeff

14

Multi-stage decoding of C is inspired by [16]. Suppose that the vectors c` have been correctly decoded
for i = 0, 1, . . . , ` − 1. We compute
r−

r` =

P`−1
i=0
2`

2i ci

!
mod 2

z
= c` + ` mod 2.
2



(22)
(23)

This may be interpreted as the transmission of c` ∈ C` (s` ) through a modulo-2 channel subject to
additive noise z/2` . In particular, maximum-likelihood decoding on this channel would be given by
ĉ` = argmaxc` ∈C` (s` ) p(r` |c` ). Thus, provided that each s` can be efficiently computed from the previous

levels, efficient encoding is not needed for efficient multistage decoding.
To obtain low complexity decoding with near optimum performance, the iterative belief propagation
algorithm can be used, which has O(n) complexity for sparse matrices and a limited number of iterations.
The algorithm has as its input a vector LLR ∈ Rn with the log-likelihood ratio (LLR) of each component
r`j of the received vector r` , which is defined as


p(r`j |c`j = 0)
LLRj = ln
,
p(r`j |c`j = 1)

j = 1, . . . , n.

(24)

However, this algorithm assumes codewords c` belonging to a linear code, as opposed to an affine
code C` (s` ).
We can exploit this algorithm for the problem at hand using the lengthened linear code C`0 ⊆ Fn+1
2
defined by the parity-check matrix H0` = [−s`

H` ], which remains sparse. In this case, the admissible

codewords must be restricted to the form c0` = [1 c` ], in accordance with (21). In order to impose this
constraint, it suffices to provide as an input LLR vector the vector given as
h
i
LLR0 = ∞ LLR ,

(25)

indicating that it is certain that the first symbol of the codeword is equal to 1.
We conclude that the decoding of C can be realized with complexity O(Ln). By means of the union
bound, the probability of error satisfies

Pe (C, σ 2 ) ≤ Pe (C0 , σ 2 ) + Pe C1 , (σ/2)2 + · · · +

+ Pe CL−1 , (σ/2L−1 )2
where, for 0 ≤ ` ≤ L − 1, Pe (C` , (σ/2` )2 ) is the probability of error of C` on channel (23).

(26)

15

VI. A G ENERALIZATION OF C ONSTRUCTION D0
A significant limitation of Construction D0 is the requirement that not only the component codes but
also their corresponding parity-check matrices H` be nested, i.e., that H` be a submatrix of H`−1 . This
constraint complicates the design of LDPC codes as it requires, for instance, that the average column
weight of H`−1 be strictly (and often significantly) higher than that of H` , conflicting with the optimum
design of LDPC codes for their corresponding target rates. In principle, one could eliminate this constraint
entirely and redefine Construction D0 by means of expression (13). However, with that approach there
would be no guarantee of the cardinality of C (as given by (18)), let alone the possibility of sequential
encoding, thus compromising essential properties of the construction. The reason is that a congruence
modulo 2`+1 in (13) applies not only to level ` but also to all levels i < ` through a reduction modulo
2i+1 . Thus, sequential encoding is not possible unless these new congruences for previous levels are

completely redundant. This idea is captured by Lemma 1, which is the fundamental ingredient enabling
sequential encoding and the guarantee of cardinality as an immediate consequence.
However, requiring that H` be a submatrix of H`−1 is simple, but it is not the only way of satisfying
Lemma 1. Instead, we can relax the nesting constraint on matrices H` by enforcing the more general
constraint
H` ≡ F` H`−1

(mod 2` )

(27)

for some integer matrix F` , from which Lemma 1 immediately follows. Clearly, requiring that H` be a
submatrix of H`−1 is a special case of this constraint.
Definition 1 (Generalized Construction D0 ): Let the matrices H` ∈ Zm` ×n , ` = 0, . . . , L − 1, be such
that
1) ϕ(H` ) is full-rank, for ` = 0, . . . , L − 1;
2) H` ≡ F` H`−1 (mod 2` ), for some F` ∈ Zm` ×m`−1 , for ` = 1, . . . , L − 1.
The lattice
n
Λ = v ∈ Zn : H` vT ≡ 0

(mod 2`+1 ), 0 ≤ ` ≤ L − 1

o

is said to be obtained by the Generalized Construction D0 applied to H0 , . . . , HL−1 . Equivalently, we
can express Λ as Λ = C + 2L Zn , where C = Λ ∩ [0, 2L )n is a lattice code.
It follows immediately that the set Λ defined above is indeed a lattice.
The emphasis of Definition 1 is on the parity-check matrices H` , rather than on the component codes.
The interpretation based on nested component codes can be reestablished by taking C` ⊆ Fn2 to be the
` ×n
null space of ϕ(H` ) ∈ Fm
. Clearly, as a consequence of (27), we have C0 ⊆ C1 ⊆ · · · ⊆ CL−1 .
2

16

The main result of this section is given the by following theorem.
Theorem 3: Let C be a lattice code satisfying Definition 1. Then C admits sequential encoding according
to Theorem 2. Moreover, |C| = |C0 | · · · · · |CL−1 |.
Proof: The proof follows immediately since Theorem 2 only relies on (13) and Lemma 1.
It is easy to see that all of the results of Section V are still valid for the Generalized Construction D0 .
Example 2: Let



2 7 4

F1 = 
11 9 6
h
i
F2 = 3 5
be arbitrarily chosen integer matrices, and let

1


H0 = 1

1

1
H1 = F1 H0 mod 2 = 
0
h
H2 = F2 H1 mod 4 = 3

1 1
0 1
1 0
0 1
1 0
1 3


1


0

0

0

1
i
1 .

Note that ϕ(H0 ), ϕ(H1 ) and ϕ(H2 ) are full-rank. Generalized Construction D0 applied to matrices H0 ,
H1 , and H2 produces a lattice code C with L = 3 levels and rate R =

1
n

log2 |C| =

1
4

log2 (21+2+3 ) = 1.5

bits per dimension.
Note that H2 is non-binary, as may be any of the matrices H` , for ` ≥ 2. Nevertheless, all the
encoding and decoding operations are still performed over F2 with ϕ(H` ), except for the computation
of the syndrome s` in (16).
VII. N ESTED LDPC C ODES BY C HECK S PLITTING
In this section, we propose a method to construct suitable binary matrices H0 , . . . , HL−1 that satisfy
the conditions of Generalized Construction D0 . Our approach is to sequentially construct matrix H`−1
based on matrix H` , for ` = L − 1, . . . , 1, assuming we are given the parity-check matrix HL−1 of the
highest-rate code and the desired number of rows for the remaining matrices, mL−2 , . . . , m0 .
Our method guarantees that, for each new level, the column weights of the initial matrix are preserved,
i.e., all component codes will share the same variable-node degree distribution. While this approach may

17

not lead to an optimal design for all rates, it allows us to choose, for instance, all component codes to
be regular LDPC codes with variable-node degree dv = 3, which we can expect to exhibit at least a
reasonable performance. Note that this choice is simply not available with the original Construction D0 .
We also present variations of the basic method aimed at maximizing girth and at allowing linear-time
encoding, inspired by the progressive edge growth (PEG) algorithm [29].
For the remainder of the section, it suffices to consider the following problem: given a full-rank matrix
B ∈ {0, 1}b×n and a desired number of rows m > b, construct a full-rank matrix H ∈ {0, 1}m×n with

the same sequence of column weights and such that B = FH, for some F ∈ Zb×m .
Since an equivalent representation of a binary matrix H is a Tanner graph (a bipartite graph, with m
check nodes and n variable nodes, having H ∈ {0, 1}m×n as incidence matrix), we use the two concepts
interchangeably.

A. Check Splitting
We first describe a general method based on the splitting of parity-check equations, which we refer to
as check splitting6 for short. The basic idea is illustrated in Fig. 1, where a check node is split in two
without changing the variable nodes on which the corresponding edges are incident.
For all H = [H(i, j)] ∈ {0, 1}m×n , let J (H) = (J1 (H), . . . , Jm (H)), where each Ji (H) = {j ∈
{1, . . . , n} : H(i, j) 6= 0} is a set containing the indices of the nonzero entries of the ith row of H.

Similarly, let I(H) = (I1 (H), . . . , In (H)), where each Ij (H) = {i ∈ {1, . . . , m} : H(i, j) 6= 0} is a
set containing the indices of the nonzero entries of the j th column of H.
Let m ≥ b and let p : {1, . . . , m} → {1, . . . , b} be a surjective mapping. A matrix H ∈ {0, 1}m×n
is said to be obtained from B ∈ {0, 1}b×n by check splitting based on the parent mapping p if, for all
i = 1, . . . , b, the set {Ji (H) : i ∈ p−1 (k)} forms a partition of Jk (B), where p−1 (k) = {i ∈ {1, . . . , m} :
p(i) = k} is the preimage of k under p.

Clearly, check splitting preserves column weights, since every nonzero entry of B appears in H in
the same column, although possibly in a different row. Moreover, it is easy to see that B = FH, where
F ∈ {0, 1}b×m is such that J (F) = (p−1 (1), . . . , p−1 (b)), i.e., adding the rows of H with indices in
p−1 (k) gives precisely the k th row of B.

Example 3: Starting with
h
i
H2 = 1 1 1 1 1 1 1 1
6

Our definition of check splitting differs from that in [30], which introduces a variable node connecting the check nodes

produced from splitting.

18

c1
e v1

e v2

v1

v2

e v3

e v4

v3

c1,1
e v1

v1

e v2

c1,2
e v3

v2

v4

e v4

v3

v4

Fig. 1. Example of check splitting. Check node c1 is split into two check nodes c1,1 and c1,2 . The number of edges is preserved
and each edge remains incident on the same variable node.

we can partition it into


1 0 0 1 0 1 1 0

H1 = 
0 1 1 0 1 0 0 1
which, in turn, can be partitioned into

0


1
H0 = 

0

0


0 0 1 0 1 0 0


0 0 0 0 0 1 0
.

1 0 0 0 0 0 1

0 1 0 1 0 0 0

Note that H1 = F1 H0 and H2 = F2 H1 , where


1 1 0 0

F1 = 
0 0 1 1
h
i
F2 = 1 1 .
Note that all matrices are binary and that each column has the same weight, namely 1.
A useful property of check splitting, which follows from [31, Lemma 8], is that it cannot reduce girth.
Thus, in particular, H is guaranteed to be free of 4-cycles if B is so.

19

Algorithm 1 PEG-based check splitting
Input: B ∈ {0, 1}b×n , m
Output: H ∈ {0, 1}m×n
1:

Create the parent mapping p.

2:

Initialize H ← 0.

3:

for j = 1, . . . , n do

4:

for k ∈ Ij (B) do

5:

I ← p−1 (k)

6:

I ← {i ∈ I : dH (i, j) = maxi0 ∈I dH (i0 , j)}

7:

I ← {i ∈ I : |Ji (H)| = mini0 ∈I |Ji0 (H)|}

8:

Choose some i ∈ I and set H(i, j) ← 1.

9:
10:

end for
end for

B. PEG-Based Check Splitting
While girth preservation is a desirable feature, one typically expects a lower-rate code to have a better
cycle distribution than a higher-rate code of the same length, preferably a larger girth. This is possible
in the check splitting procedure if checks are split in a way that breaks short cycles in which they
are involved. More generally, it is conceivable that a judicious choice of check splits may increase the
performance of the resulting code.
In the following, we propose a check splitting algorithm, inspired by the PEG algorithm [29], that
attempts to maximize the girth of the resulting matrix. For all i = 1, . . . , m and all j = 1, . . . , n, let
dH (i, j) denote the distance from check node i to variable node j in the Tanner graph induced by H,

where dH (i, j) = ∞ if there is no path joining these nodes. As shown in Algorithm 1, the proposed
method greedly processes each (k, j) nonzero entry of B, adding a corresponding entry in H in the same
column j but in some child row i ∈ p−1 (k) that satisfy two goals: first, it should maximize the distance to
variable node j of the resulting Tanner graph; second, if multiple possibilities remain, a check of lowest
degree is chosen. The algorithm can be interpreted as a generalization of the PEG algorithm where, for
each iteration, the set of allowed checks is restricted to p−1 (k), as shown in line 5. (The original PEG
algorithm is essentially recovered if this line is replaced by I ← {1, . . . , m}.)
A secondary goal of the algorithm is to make the weights of the resulting rows as uniform as possible,
which is also a desirable feature of a good LDPC code. However, some care must be taken to ensure

20

Algorithm 2 Create the parent mapping for Algorithm 1
Input: B ∈ {0, 1}b×n , m
Output: p : {1, . . . , m} → {1, . . . , b}
1:

Set p(i) = i for i = 1, . . . , b.

2:

for i = b + 1, . . . , m do

3:

K ← {1, . . . , m}

4:

K ← {k ∈ K : µp (k) = maxk0 ∈K µp (k 0 )}

5:

Choose some k ∈ K and set p(i) ← k .

6:

end for

that the parent mapping p is indeed suitable to result in concentrated weights, which is accomplished by
Algorithm 2. Specifically, for each ith row of H, this algorithm chooses as its parent row in B one that
achieves maximum metric
µp (k) ,

|Jk (B)|
−1
|p (k)| +

1

(28)

which can be interpreted as the average weight of a corresponding child row after the parent assignment
is made (i.e., a row is chosen that can most tolerate a further split).
C. Triangular PEG-Based Check Splitting
A drawback of Algorithm 1 is that it generally does not produce matrices that have an approximate
triangular structure. We propose a simple adaptation that ensures such a structure, thereby enabling
efficient encoding. The algorithm takes a base matrix B of the form (20) with gap g and returns a
check-splitted matrix H in the same form and with the same gap g . Thus, B and H will have exactly
the same encoding complexity.
For ease of notation, we assume that B is actually in approximate upper triangular form, which can
be easily accomplished by left-right and up-down flipping of a matrix in the form (20). The resulting
matrix H is similarly given in the same form.
The proposed method, which is again inspired from [29], is given in Algorithm 3. The differences
from Algorithm 1 are essentially the inclusion of lines 5–9, which add a 1 in the g th subdiagonal,
and the modification in line 11, which restrict the valid choices of child rows to those above the g th
subdiagonal. The crucial assumption is that p(g + j) ∈ Ij (B) for all j = 1, . . . , m − g , since a 1 can
only be added in position (g + j, j) of H if a 1 exists in position (k0 , j) of B, where k0 = p(g + j) is
the corresponding parent row. This property can be ensured during the creation of the parent mapping
by a simple modification in line 3 of Algorithm 2, as shown in Algorithm 4.

21

Algorithm 3 Triangular PEG-based check splitting
Input: B ∈ {0, 1}b×n , g , m
Output: H ∈ {0, 1}m×n
1:

Create the parent mapping p.

2:

Initialize H ← 0.

3:

for j = 1, . . . , n do

4:

K ← Ij (B)

5:

if j ≤ m − g then

6:

H(g + j, j) ← 1

7:

k0 ← p(g + j)

8:

K ← K \ {k0 }

9:
10:

end if
for k ∈ K do

11:

I ← p−1 (k) ∩ {1, . . . , min{g + j − 1, m}}

12:

I ← {i ∈ I : dH (i, j) = maxi0 ∈I dH (i0 , j)}

13:

I ← {i ∈ I : |Ji (H)| = mini0 ∈I |Ji0 (H)|}

14:

Choose some i ∈ I and set H(i, j) ← 1.

15:
16:

end for
end for

Algorithm 4 Create the parent mapping for Algorithm 3
3: K ← Ii−g (B)
(Note: only the differences from Algorithm 2 are shown.)

VIII. S IMULATION R ESULTS
This section discusses the design of LDPC lattices with L = 2 coded levels, as well as its performance
on the AWGN channel with and without power constraint.
In all examples of Generalized Construction D0 lattices, two nested codes C0 ⊆ C1 , with parity-check
matrices H0 ∈ {0, 1}m0 ×n and H1 ∈ {0, 1}m1 ×n , respectively, are designed as variable-regular LDPC
codes with variable-node degree dv = 3. For any given choice of m0 and m1 , the matrix H1 is constructed
via the triangular version of the PEG algorithm [29], modified to allow for a gap g , which is chosen to
be g = 18, while H0 is obtained from H1 via triangular PEG-based check splitting with the same gap.
Thus, the resulting lattices are guaranteed to have efficient encoding.

22

10 0

Block error rate

10 -1

10 -2

10 -3

10 -4
LDPC (generalized D′ )
LDPC (original D′ )
Polar
Poltyrev limit

10 -5

10 -6
0

0.5

1

1.5

2

2.5

3

3.5

VNR (dB)

Fig. 2. Block error rate for 2-level lattices of dimension 1024 with multistage decoding: LDPC lattices via Generalized
Construction D0 with check splitting, LDPC lattices via the original Construction D0 , and polar lattices (curve extracted from
[18]). The Poltyrev limit is also shown.

A. Power-Unconstrained Channel
We construct an LDPC lattice Λ = C + 4Zn with the Generalized Construction D0 applied to matrices
H0 and H1 . In order to allow a fair comparison with the results in [18], we use the same design

parameters, namely, block length (dimension) n = 1024 and block error probability Pe ≤ 10−5 .
The design of m0 and m1 , or, equivalently, of rates R0 and R1 , can be done using the equal error
probability rule [15] applied to the union-bound estimate
Pe (Λ, σ 2 ) ≤ Pe (C0 , σ 2 ) + Pe (C1 , (σ/2)2 ) + Pe (4Zn , (σ/4)2 )

(29)

obtained by combining (8) and (26). Under this rule, the goal is to make the three terms above approximately equal to 10−5 /3.
Given that level 2 (uncoded) allows a simple modulo-4Zn lattice decoder (essentially a PAM detector),
it is easy to compute the noise level that results in the desired block error probability, which is verified
to be σ = 0.3379.
The code rates were found in an iterative process of design and simulation, which, for the desired error
probability, resulted in R0 = 0.2383 (m0 = 780) and R1 = 0.9043 (m1 = 98). Thus, the total coded rate
is R = 1.1426, leading to a VNR of 1.6823, or 2.2590 dB, for the given noise level.
Fig. 2 shows simulation results for the block error rate of Λ as a function of the VNR. Decoding was
performed as described in Section V-B, where for each component code the belief propagation decoder

23

performed a total of 50 iterations. Each simulation point was obtained after at least 100 block errors.
For comparison, the performance of a polar lattice with n = 1024 (based on a one-dimensional lattice
partition) from [18] is also shown. As can be seen, the LDPC lattice appears to slightly outperform the
polar lattice at the target error rate of 10−5 . After that point, the slope of the curve appears to become
less steep; this is due to the uncoded component of the lattice, which dominates the error rate for high
SNR, and is also expected for the polar lattice.
To illustrate the motivation for the Generalized Construction D0 , Fig. 2 also shows the performance of
our best attempt at designing an LDPC lattice via the original Construction D0 . This lattice is constructed
based on the same design parameters as before, but now H0 is constrained to be a submatrix of H1 . Both
matrices are constructed together via the extended PEG algorithm from [21], which takes as input the
number of rows and the variable-node degree distribution for each level. Assuming variable-regular degree
distributions, we found experimentally the values of d0v = 6 and d1v = 3 to give the best performance (note
that d0v ≥ d1v due to the nesting constraint). For the rate design, we obtained R0 = 0.0967 (m0 = 925)
and R1 = 0.9043 (m1 = 98) using the equal error probability rule under multistage decoding. As can
be seen, the resulting lattice requires a much larger VNR for the same target error rate, which is due
to the poor performance of C0 . Indeed, compared to the previous design, the design of C1 remained
essentially unchanged, while R0 had to be significantly decreased in order for C0 to meet the desired
error rate. This poor performance can be partly explained by the fact that C0 has vastly spread check
degrees; more precisely, the check degrees are distributed on the values 3, 4, 31 and 32. This is in sharp
contrast to the C0 obtained by Generalized Construction D0 with check splitting, whose check degrees are
concentrated between 3 and 5. (There is evidence and it is a standing conjecture that check-concentrated
degree distributions are optimal [20].)
B. Power-Constrained Channel
We construct an LDPC lattice code C with Generalized Construction D0 applied to matrices H0 and
H1 . Note that this corresponds to a multilevel coded (MLC) 4-PAM modulation scheme with Ungerboeck

labeling [15], [23], constrained so as to produce a lattice code. Decoding is performed using lattice MSD
as described in sections III-B and V-B. We set the total rate at R = 1.5 bits per symbol, the block length
at n = 2048, and the target block error probability at Pe = 10−3 .
The rate design follows the equal error probability rule based on the union bound estimate (26), so
C0 and C1 are designed for Pe (C0 , σ 2 ) = Pe (C1 , (σ/2)2 ) = 10−3 /2. After an iterative process of design

and simulation, we found that the target error rate was obtained for rates R0 = 0.5244 (m0 = 974) and
R1 = 0.9756 (m1 = 50) at σ = 0.3033, leading to an SNR of 11.33 dB.

24

10 0

Block error rate

10 -1

10 -2

Lattice-MLC / Lattice-MSD
Lattice-MLC / MSD
MLC / MSD
BICM
Shannon limit

10 -3

9

9.5

10

10.5

11

11.5

SNR (dB)

Fig. 3. Block error rate for unshaped LDPC coded 4-PAM modulation schemes: lattice-constrained MLC with lattice MSD;
lattice-constrained MLC with conventional MSD; unconstrained MLC with conventional MSD; and BICM. All schemes have
total rate of R = 1.5 bits per symbol and block length n = 2048 symbols. The input-constrained Shannon limit is also shown.

In order to compare with conventional, non-lattice coded modulation schemes, we have designed
an MLC 4-PAM modulation scheme with Ungerboeck labeling for conventional (non-lattice) multistage
decoding, as well as a 4-PAM BICM scheme with Gray labeling. In both schemes, decoding is performed
in the conventional way by computing the LLRs of each bit under AWGN, which takes the finite
constellation into account. The MLC scheme is composed of two variable-regular LDPC codes with
block length n = 2048 and column weight dv = 3 constructed independently (without any nesting
constraints) using the PEG algorithm. The rates of the component codes, R0 = 0.5259 (m0 = 971) and
R1 = 0.9741 (m1 = 53) were again found by the equal error probability rule. The BICM scheme uses a

variable-regular LDPC code with block length 4096, variable node degree dv = 3, and rate 3/4. Note that
all schemes have the same spectral efficiency (R = 1.5 bits per symbol) and same delay in modulation
symbols (n = 2048).
Fig. 3 shows the performance of the three schemes. As before, the belief propagation decoder of
each code was run for a total of 50 iterations and each simulation point was obtained after at least 100
block errors. As can be seen, the LDPC lattice code achieves a performance about 0.4 dB below that of
non-lattice coded modulation schemes at a block error rate of 10−3 . In order to understand whether the
loss in performance is due to the nesting constraints of the component codes or to the suboptimal lattice
decoder, we have also simulated a lattice-constrained MLC scheme under conventional MSD. The design
parameters are exactly the same as those of the conventional MLC/MSD scheme, the only difference is

25

that the matrix H0 is obtained from H1 by check splitting, so as to satisfy conditions of Construction D0 .
Clearly, the loss can be be attributed to lattice decoding, since the resulting performance is apparently
indistinguishable from that of unconstrained MLC, as can be seen in Fig. 3. Note that lattice decoding is
essential for most applications of lattice codes in multiterminal problems, such as compute-and-forward
[6] and integer-forcing [7], so this degradation may be tolerable if it is surpassed by the overall benefits
of using lattice codes.
IX. C ONCLUSION
We have proposed a new multilevel lattice construction based on nested linear codes that generalizes
Construction D0 . This new construction relaxes some of the nesting constraints on the parity-check
matrices of the component codes, significantly facilitating their design. In particular, this approach
enables the design of nested LDPC codes whose performance appears to be indistinguishable from that
of independent (non-nested) LDPC codes with the same rates. We have also proposed a general principle
for constructing nested codes based on the partitioning of parity-check equations, as well as a practical
method, inspired by the PEG algorithm, to construct LDPC subcodes of large girth that can be efficiently
encoded. Overall, the resulting LDPC lattice codes constructed by our methods can be encoded and
decoded with complexity that is linear in both the block length and the number of levels.
Simulation results indicate that our LDPC lattice codes have a performance comparable to that of polar
lattices for the Poltyrev scenario and only slightly inferior to conventional (non-lattice) coded modulation
techniques for the input-constrained AWGN channel, even under lattice decoding. The latter degradation
seems a small price to pay for the potential benefits afforded by the lattice structure in multiterminal
applications.
R EFERENCES
[1] R. Zamir, Lattice Coding for Signals and Networks.

Cambridge, UK: Cambridge University Press, 2014.

[2] R. Urbanke and B. Rimoldi, “Lattice codes can achieve capacity on the AWGN channel,” IEEE Trans. Inf. Theory, vol. 44,
no. 1, pp. 273–278, Jan. 1998.
[3] U. Erez and R. Zamir, “Achieving 1/2 log (1+SNR) on the AWGN channel with lattice encoding and decoding,” IEEE
Trans. Inf. Theory, vol. 50, no. 10, pp. 2293–2314, Oct. 2004.
[4] D. Krithivasan and S. S. Pradhan, “Lattices for distributed source coding: Jointly Gaussian sources and reconstruction of
a linear function,” IEEE Trans. Inf. Theory, vol. 55, no. 12, pp. 5628–5651, Dec. 2009.
[5] C. Ling, L. Luzzi, J. C. Belfiore, and D. Stehlé, “Semantically secure lattice codes for the Gaussian wiretap channel,”
IEEE Trans. Inf. Theory, vol. 60, no. 10, pp. 6399–6416, Oct. 2014.
[6] B. Nazer and M. Gastpar, “Compute-and-forward: Harnessing interference through structured codes,” IEEE Trans. Inf.
Theory, vol. 57, no. 10, pp. 6463–6486, Oct. 2011.

26

[7] J. Zhan, B. Nazer, U. Erez, and M. Gastpar, “Integer-forcing linear receivers,” IEEE Trans. Inf. Theory, vol. 60, no. 12,
pp. 7661–7685, Dec. 2014.
[8] G. Caire, G. Taricco, and E. Biglieri, “Bit-interleaved coded modulation,” IEEE Trans. Inf. Theory, vol. 44, no. 3, pp.
927–946, May 1998.
[9] D. Declercq, M. Fossorier, and E. Biglieri, Channel Coding: Theory, Algorithms, and Applications. Amsterdam: Elsevier,
2014.
[10] J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, 3rd ed. New York, NY: Springer-Verlag, 1999.
[11] N. di Pietro, J. J. Boutros, G. Zémor, and L. Brunel, “Integer low-density lattices based on construction A,” in 2012 IEEE
Information Theory Workshop, Sep. 2012, pp. 422–426.
[12] N. di Pietro, G. Zémor, and J. J. Boutros, “New results on Construction A lattices based on very sparse parity-check
matrices,” in 2013 IEEE International Symposium on Information Theory, Jul. 2013, pp. 1675–1679.
[13] N. Sommer, M. Feder, and O. Shalvi, “Low-density lattice codes,” IEEE Trans. Inf. Theory, vol. 54, no. 4, pp. 1561–1585,
Apr. 2008.
[14] R. A. P. Hernandez and B. M. Kurkoski, “The three/two Gaussian parametric LDLC lattice decoding algorithm and its
analysis,” IEEE Trans. Commun., vol. 64, no. 9, pp. 3624–3633, Sep. 2016.
[15] U. Wachsmann, R. F. H. Fischer, and J. B. Huber, “Multilevel codes: Theoretical concepts and practical design rules,”
IEEE Trans. Inf. Theory, vol. 45, no. 5, pp. 1361–1391, Jul. 1999.
[16] G. D. Forney, M. D. Trott, and S.-Y. Chung, “Sphere-bound-achieving coset codes and multilevel coset codes,” IEEE Trans.
Inf. Theory, vol. 46, no. 3, pp. 820–850, May 2000.
[17] A. Sakzad, M. R. Sadeghi, and D. Panario, “Construction of turbo lattices,” in 2010 48th Annual Allerton Conference on
Communication, Control, and Computing (Allerton), Sep. 2010, pp. 14–21.
[18] Y. Yan, L. Liu, C. Ling, and X. Wu, “Construction of capacity-achieving lattice codes: Polar lattices,” arXiv:1411.0187,
Nov. 2014. [Online]. Available: http://arxiv.org/abs/1411.0187
[19] G. Poltyrev, “On coding without restrictions for the AWGN channel,” IEEE Trans. Inf. Theory, vol. 40, no. 2, pp. 409–417,
Mar. 1994.
[20] T. J. Richardson and R. L. Urbanke, Modern Coding Theory.

Cambridge University Press, 2008.

[21] M.-R. Sadeghi, A. Banihashemi, and D. Panario, “Low-density parity-check lattices: Construction and decoding analysis,”
IEEE Trans. Inf. Theory, vol. 52, no. 10, pp. 4481–4495, Oct. 2006.
[22] Y. S. Choi, I. J. Baik, and S. Y. Chung, “Iterative decoding for low-density parity-check lattices,” in 10th International
Conference on Advanced Communication Technology, 2008. ICACT 2008, vol. 1, Feb. 2008, pp. 358–361.
[23] G. D. Forney, “Coset codes—Part I: Introduction and geometrical classification,” IEEE Trans. Inf. Theory, vol. 34, no. 5,
pp. 1123–1151, Sep. 1988.
[24] W. Kositwattanarerk and F. Oggier, “Connections between Construction D and related constructions of lattices,” Des. Codes
Cryptogr., vol. 73, no. 2, pp. 441–455, Nov. 2014.
[25] A. Vem, Y.-C. Huang, K. Narayanan, and H. Pfister, “Multilevel lattices based on spatially-coupled LDPC codes with
applications,” in 2014 IEEE International Symposium on Information Theory (ISIT), Jun. 2014, pp. 2336–2340.
[26] H. Khodaiemehr, M. R. Sadeghi, and A. Sakzad, “Practical encoder and decoder for power constrained QC LDPC-lattice
codes,” IEEE Trans. Commun., vol. 65, no. 2, pp. 486–500, Feb. 2017.
[27] C. Feng, D. Silva, and F. R. Kschischang, “Lattice network coding over finite rings,” in 2011 12th Canadian Workshop
on Information Theory (CWIT), May 2011, pp. 78–81.

27

[28] T. J. Richardson and R. L. Urbanke, “Efficient encoding of low-density parity-check codes,” IEEE Trans. Inf. Theory,
vol. 47, no. 2, pp. 638–656, Feb. 2001.
[29] X.-Y. Hu, E. Eleftheriou, and D. M. Arnold, “Regular and irregular progressive edge-growth Tanner graphs,” IEEE Trans.
Inf. Theory, vol. 51, no. 1, pp. 386–398, Jan. 2005.
[30] M. Good and F. R. Kschischang, “Incremental redundancy via check splitting,” in 23rd Biennial Symposium on
Communications, 2006, 2006, pp. 55–58.
[31] A. Subramanian, A. Thangaraj, M. Bloch, and S. W. McLaughlin, “Strong secrecy on the binary erasure wiretap channel
using large-girth LDPC codes,” IEEE Trans. Inf. Forensics Secur., vol. 6, no. 3, pp. 585–594, Sep. 2011.

