1

Lattice Codes Achieve the Capacity of Common
Message Gaussian Broadcast Channels with Coded
Side Information

arXiv:1509.01332v3 [] 17 Dec 2017

Lakshmi Natarajan, Yi Hong, Senior Member, IEEE, and Emanuele Viterbo, Fellow, IEEE

Abstract—Lattices possess elegant mathematical properties
which have been previously used in the literature to show that
structured codes can be efficient in a variety of communication
scenarios, including coding for the additive white Gaussian noise
(AWGN) channel, dirty-paper channel, Wyner-Ziv coding, coding
for relay networks and so forth. We consider the family of singletransmitter multiple-receiver Gaussian channels where the source
transmits a set of common messages to all the receivers (multicast
scenario), and each receiver has coded side information, i.e., prior
information in the form of linear combinations of the messages.
This channel model is motivated by applications to multi-terminal
networks where the nodes may have access to coded versions of
the messages from previous signal hops or through orthogonal
channels. The capacity of this channel is known and follows from
the work of Tuncel (2006), which is based on random coding
arguments. In this paper, following the approach of Erez and
Zamir, we design lattice codes for this family of channels when
the source messages are symbols from a finite field Fp of prime
size. Our coding scheme utilizes Construction A lattices designed
over the same prime field Fp , and uses algebraic binning at the
decoders to expurgate the channel code and obtain good lattice
subcodes, for every possible set of linear combinations available
as side information. The achievable rate of our coding scheme is
a function of the size p of underlying prime field, and approaches
the capacity as p tends to infinity.
Index Terms—Capacity, Construction A, Gaussian broadcast
channel, lattice, multicast, side information, structured codes.

I. I NTRODUCTION

I

NFORMATION-theoretic results often rely on random
coding arguments to prove the existence of good codes.
Usually, the codebook is constructed by randomly choosing
the components of each codeword independently and identically from a judiciously chosen probability distribution. While
this technique is powerful, the resulting codebooks do not
exhibit any structure that may be of practical interest. One
such desirable structure is linearity, which allows complexity
reductions at the encoder and decoder by utilizing efficient
algebraic processing techniques. Further, in certain communication scenarios, coding schemes based on linear codes yield a
larger achievable rate region than random code ensembles, as
This work was supported by the Australian Research Council (ARC)
Discovery Project (ARC DP160101077). The material in this paper was
presented in part at the IEEE International Symposium on Information Theory,
Aachen, Germany, June 25–30, 2017.
Dr. Natarajan is with the Department of Electrical Engineering, Indian
Institute of Technology Hyderabad, Sangareddy 502 285, India (e-mail: lakshminatarajan@iith.ac.in).
Dr. Hong and Prof. Viterbo are with the Department of Electrical and
Computer System Engineering, Monash University, VIC 3800, Australia (email: {yi.hong, emanuele.viterbo}@monash.edu).

was shown by Körner and Marton [1] for a distributed source
coding problem. Structured coding schemes have been widely
studied in the literature, especially for communications in the
presence of side information and in multi-terminal networks.
For an overview of structured coding schemes we refer the
reader to [2], [3] and the references therein.
For communication in the wireless domain, structured codes
can be obtained by choosing finite subsets of points from
lattices [2], [4]–[6]. A lattice is an infinite discrete set of
points in the Euclidean space that are regularly arranged and
are closed under addition. Codes based on lattices, known
as (nested) lattice codes or Voronoi codes, are the analogues
of linear codes in wireless communications. Efficient lattice
based strategies are known for a variety of communication scenarios, such as for achieving the capacity of the point-to-point
additive white Gaussian noise (AWGN) channel [7]–[11], for
dirty-paper coding [2], [12], the Wyner–Ziv problem [2] and
communication in relay networks [13]–[16], to name only a
few.
In this paper we present good lattice strategies for communication in common message Gaussian broadcast channels, which we refer to as the multicast channel, where
receivers have prior side information about the messages being
transmitted. In particular, we assume that the transmitter is
multicasting K message symbols w1 , . . . , wK from a finite
field Fp , of prime size p, to all the receivers, and each
receiver may have coded side information about the messages:
the prior knowledge of the values of (possibly multiple) Fp linear combinations of w1 , . . . , wK . The number of linear
combinations available as side information and the coefficients
of these linear combinations can differ from one receiver
to the next. The capacity of this channel is known and
follows from the results of Tuncel [17], where the achievability
part utilizes an ensemble of codebooks generated using the
Gaussian distribution.
The multiuser channel considered in this paper is a noisy
version of a simple special case of index coding [18]–[20].
The index coding problem considers a noiseless broadcast link
where each receiver demands a subset of the source messages
and knows the values of some other subset as side information.
A generalization of the index coding problem in which the
receivers have access to linear combinations of messages
was studied recently in [21], [22]. The specific instance of
index coding where each receiver demands all the messages
from the source corresponds to a noiseless multicast channel and has a simple optimum solution based on maximum

2

distance separable (MDS) codes [23]. When the channel is
noisy, capacity-achieving coding schemes based on structured
codes are not available. In this paper we design lattice-based
strategies for multicasting over the AWGN channel where
the side information at the receivers is in the form of linear
combinations of source messages.
The case of Gaussian multicast channel with coded side
information is motivated by applications to multi-terminal
communication networks. It is known that signal interference
in wireless channels can be harnessed by decoding linear
combinations of transmit messages instead of either treating
interference as noise or decoding interference along with the
intended message [14], [15]. When such a technique is used in
a mutli-hop communication protocol, one encounters receivers
that have coded side information obtained from transmissions
in the previous phases. Similarly, in a network that consists of
both wired and wireless channels, the symbols received from
wired links can be utilized as side information for decoding
the wireless signals. If a linear network code is used in the
wired part of the network, then the side information is in the
form of linear combinations of the source messages.
Example 1 (Communciation in relay networks). Consider a
wireless network with two base stations BS1 and BS2 , that
hold message symbols w1 and w2 , respectively. The base
stations are required to multicast w1 and w2 to four user
nodes U1 , . . . , U4 through the relay node R, see Fig. 1. In
the first phase of the protocol, BS1 and BS2 encode the data
symbols w1 and w2 , and transmit the resulting codewords
simultaneously. By using the decoding technique of computeand-forward [15], U3 reliably decodes some linear combination s1 w1 + s2 w2 , s1 , s2 ∈ Fp , from the received noisy
superposition of the two transmit signals. On the other hand,
R has a higher signal-to-noise ratio and successfully decodes
both w1 and w2 by behaving as a multiple-access receiver.
Further, there is no signal interference at U1 and U2 , and these
two nodes reliably decode w1 and w2 , respectively.
We observe that the second phase of the protocol is a
common message broadcast channel with coded side information at the receivers: the relay needs to multicast w1 , w2
to four user nodes, the first three users U1 , U2 , U3 have prior
knowledge of the linear combinations w1 + 0w2 , 0w1 + w2
and s1 w1 + s2 w2 , respectively, while the fourth user has no
such side information.
Example 2 (Wireless overlay for wired networks). Assume
a network of noiseless wired links in the form of a directed
acyclic graph, where the source node vs desires to multicast K
independent messages w1 , . . . , wK ∈ Fp to a set of destination
nodes D. The wireline network employs a traditional (scalar)
linear network code [24]–[26], i.e., the symbol transmitted
on each outgoing edge of a node is an element of Fp
generated as a linear combination of the symbols received
on its incoming edges. At every destination node vd ∈ D,
the decoder attempts to recover the K message symbols from
their Fp -linear combinations received on its incoming edges.
Recovery is possible if and only if the number of linearly
independent equations available at vd is K. It is known that
the maximum number of linearly-independent equations that

(a) Multiple-access phase: The relay R decodes both w1 and w2 ,
while U1 , U2 , U3 decode w1 ,w2 and s1 w1 + s2 w2 , respectively.

(b) Multicast phase: R multicasts w1 and w2 to all four user
nodes. Three of the users have the knowledge of some linear
combination of w1 and w2 , while the fourth user has no side
information.
Fig. 1. A relay network where one encounters a common message broadcast
channel with coded side information at the receivers.

can be made available at vd is min{max-flow(vd ), K}, where
max-flow(vd ) is the maximum number of edge-disjoint paths
from vs to vd , see [26]. It follows that multicasting is possible
if and only if max-flow(vd ) ≥ K for every vd ∈ D.
Now suppose there exist destination nodes with max-flow
less than K, i.e., the communication demands are beyond the
wireline network’s capacity. A solution to meet the demands
is to broadcast a wireless signal from the source to fill the
capacity deficiency of the wired network, see Fig. 2. At
each destination, the Fp -linear combinations obtained from
the wireline network serve as side information to decode the
wireless broadcast signal.
A special case of coded side information is the Gaussian
multicast channel where each receiver has prior knowledge of
the values of some subset of the K messages. The known
capacity-achieving coding schemes for this special case are
based on random coding using i.i.d. (independent and identically distributed) codewords [17], [27]–[31]. Existence of
lattice based capacity-achieving coding schemes were proved

3

Fig. 2. Wireless multicast as an overlay for a wired network: the source
node vs encodes w1 , . . . , wK and broadcasts wirelessly to the destination
nodes v1 , . . . , v4 in order to supplement the communication through the wired
network. Each destination receives (possibly multiple) Fp -linear combinations
of the source symbols through a linear (wireline) network code and uses this
information to decode the wireless signal broadcast by vs .

in [28], [32] for the special case where the number of messages
and receivers are two and each receiver has the knowledge of
one of the messages. Constructions of binary codes for this
channel were proposed in [33]–[35]. Explicit constructions of
lattice codes were given in [36], [37] that convert receiver side
information into additional apparent coding gain in the AWGN
channel. Codes based on quadrature amplitude modulation
were constructed in [38], [39]. In [32], explicit codes based
on lattices and coded modulation have been designed that
perform within a few decibels of capacity when the number
of receivers is two and each knows one of the two messages
being transmitted.
The objective of this paper is to prove that lattice codes
can achieve the capacity of the common message Gaussian
broadcast channels with coded side information. We use the
information-theoretic framework set by Erez and Zamir [8] to
this end. The proposed coding scheme uses lattices obtained by
applying Construction A to linear codes over the prime field Fp
which is the alphabet of the source messages. The achievable
rate of our lattice-based coding scheme is a function of the
prime p, and approaches the capacity of the common message
Gaussian broadcast channel as p → ∞.
Our decoding scheme involves algebraic binning [2] where
the receiver side information is used to expurgate the channel
code and obtain a lower rate subcode. The set of linear
equations available as side information may differ from one
receiver to another, and hence, each receiver must employ
a different binning scheme for the same channel code. The
coding scheme ensures that the binning performed at each
receiver produces a good lattice subcode of the transmitted
code. Following expurgation, each receiver decodes the channel output by minimum mean square error (MMSE) scaling
and quantization to an infinite lattice. The algebraic structure
of the coding scheme facilitates the performance analysis by

decomposing the original channel into multiple independent
point-to-point AWGN channels – one corresponding to each
receiver – where each of the point-to-point AWGN channels
uses a lattice code for communication. Unlike [8], where
achievability in a point-to-point AWGN channel was proved
using error exponent analysis, we provide a direct proof based
only on simple counting arguments.
As a corollary to the main result, we obtain an alternative
proof of the goodness of lattice codes in achieving the capacity
of the point-to-point AWGN channel. Previous proofs of this
result presented in [8]–[10] also use ensembles of lattices
obtained by applying Construction A to random linear codes
over a prime field Fp ; see also [40], [41]. While [8] used
primes p that were exponential in the code length n, [9]
and [10] improved this result to let p grow as n1.5 and
n0.5 , respectively. The corollary presented in this paper further
improves these results by enabling a choice of the prime p
which is independent of the code length n but is a function
only of the gap between the desired rate and the channel
capacity.
Lattices have been used to design powerful physical-layer
coding schemes for wireless networks consisting of multiple
sources, relays and destinations [13]–[16]. In these networks
information from the source nodes is conveyed to the destination nodes through relays over multiple hops and time
slots. In each time slot, a set of nodes act as transmitters
and every other node in their range observes a linear superposition of the transmitted signals perturbed by AWGN.
Lattice coding schemes for these networks are designed such
that each receiver can reliably decode the observed noisy
superposition to a linear combination of source messages
which it then proceeds to transmit in the next time slot. Every
destination node decodes its desired messages once it collects
sufficiently many linear combinations. In contrast, in this paper
we consider a single hop interference-free transmission in a
multicast channel consisting of one transmitter and multiple
destination nodes that are aided by coded side information.
Our objective is to design coding schemes that can utilize
prior knowledge at these receivers rather than exploit wireless
interference arising from multiple simultaneous transmissions,
as often experienced in relay networks.
The organization of this paper is as follows. We introduce
the channel model in Section II-A and review the relevant
background on lattices and lattice codes in Section II-B. In
Section III, we state the main theorem, and describe the
lattice code ensemble and encoding and decoding procedures.
We prove the main theorem and state a few corollaries in
Section IV, and finally, we discuss some concluding remarks
in Section V.
Notation: Matrices and column vectors are denoted by
bold upper and lower case letters, respectively. The symbol
k · k denotes the Euclidean norm of a vector, and (·)| is the
transpose of a matrix or a vector. The Kronecker product of
two matrices A and B is A ⊗ B , I ` is the ` × ` identity
matrix, and 0 is the all zero matrix of appropriate dimension.
The symbol log(·) denotes logarithm to the base 2 and ln(·)
denotes logarithm to the base e. The expectation operator is
denoted by E. The symbol M\N denotes the elements in the

4

set M that do not belong to the set N .
II. C HANNEL M ODEL AND L ATTICE P RELIMINARIES
A. Channel Model and Problem Statement
We consider a (non-fading) common message Gaussian
broadcast channel with a single transmitter and finitely many
receivers, where all terminals are equipped with single antennas. The transmitter operates under an average power
constraint and the receivers are affected by additive white
Gaussian noise with possibly different noise powers. There are
K independent messages w1 , . . . , wK at the transmitter that
assume values with a uniform probability distribution from
a prime finite field Fp . Each receiver desires to decode all
the K messages while having prior knowledge of the values
of some Fp -linear combinations of the messages w1 , . . . , wK .
Consider a generic receiver that has access to the values um ,
m = 1, . . . , M , of the following set of M linear equations
K
X

sm,k wk = um ,

m = 1, . . . , M.

k=1

We will denote this side information configuration using the
×K
, where each row of S represents
matrix S = [sm,k ] ∈ FM
p
one linear equation. Any row of S that is linearly dependent
on the other rows represents redundant information and can be
discarded with no loss to the receiver side information, and
hence, with no loss to system performance. Hence, without
loss in generality, we will assume that the rows of S are linS ) = M , and M < K.
early independent over Fp , i.e., rank(S
Note that the values of S and M can be different across the
receivers. A receiver with no side information is represented
with an empty matrix for S (with M = 0).
A receiver in the multicast channel is completely characterized by its (coded) side information matrix S and the variance
σ 2 of the additive noise. If we assume that the average transmit
power at the source is 1, then the signal-to-noise ratio at this
receiver is SNR = σ12 . We will denote a receiver by the pair
S , σ 2 ), where S is any matrix over Fp with K columns and
(S
linearly independent rows, and σ 2 > 0. Note that uncoded
side information, i.e., the prior knowledge of the values of a
size M subset of w1 , . . . , wK , is a special case, and hence, is
contained within the definition of our channel model.
Example 3. Consider a source transmitting K = 3 symbols,
w1 , w2 , w3 , from the finite field F5 = {0, 1, 2, 3, 4}. A receiver
that has prior knowledge of the value of w2 has side information matrix S = 0 1 0 . This corresponds to the equation
0w1 + 1w2 + 0w3 , and the number of linearly independent
S ) = 1.
equations at this receiver is M = rank(S
Now consider another receiver that has the knowledge of
the values of the following three equations: w1 + 4w2 + 3w3 ,
4w1 + 3w2 and 2w1 + w2 + 3w3 . In matrix form, this side
information is represented by


1 4 3
4 3 0 ,
2 1 3
where the three rows represent the three equations, in that
order. The first row of this matrix is equal to the sum (over F5 )

of the second and third rows, and hence, the side information
from the first equation is redundant and can be discarded.
Since the remaining two rows are linearly independent, the
side information at this receiver can be represented by the
following matrix that consists of these two rows,


4 3 0
S=
.
2 1 3
The number of linearly independent equations at this receiver
S ) = 2.
is M = rank(S
From elementary linear algebra we know that if the values
um of M linearly independent combinations of the variables
w1 , . . . , wK are given, then the set of all possible solutions
of (w1 , . . . , wK ) is a coset of a (K − M ) dimensional linear
subspace of FK
p . Since the a priori probability distribution of
w1 , . . . , wK is uniform, we conclude that, given the side information values um , m = 1, . . . , M , the probability distribution
of (w1 , . . . , wK ) is uniform over this coset. Using the fact that
the number of elements in the coset is pK−M , we observe
that the conditional entropy of (w1 , . . . , wK ) given the side
information is

H (w1 , . . . , wK | u1 , . . . , uM ) = log pK−M
= (K − M ) log p.

(1)

Suppose we want to transmit, on the average, one realization
of (w1 , . . . , wK ) in every κ uses of the broadcast channel. The
transmission rate of each message is R = κ1 log p b/dim (bits
per real dimension or bits per real channel use).
For the simplicity of exposition, we consider only the
symmetric case where all the K messages are required to
be transmitted at the same rate R. The general scenario,
where the messages are of different rates, can be reduced
to the symmetric case through rate-splitting: if there are K 0
messages with transmission rates r1 , . . . , rK 0 , respectively,
then by splitting each of these original sources into multiple
virtual sources, one can generate a set of K sources (K ≥ K 0 )
such that their rates R1 , . . . , RK are as close to each other as
required.
We will assume that the encoding at the transmitter is
performed on a block of ` independent realizations of the
K message symbols, i.e., the source jointly encodes K message vectors w 1 , . . . , w K ∈ F`p . The transmitter uses an ndimensional channel code X ⊂ Rn together with a function
ρ : F`p × · · · × F`p → X
to jointly encode the K message vectors. The number of
codewords in X is pK` , and we will assume that the codebook
X satisfies the per-codeword power constraint
xk2
kx
≤ 1, for all x ∈ X .
(2)
n
The average number of channel uses to transmit each realization of (w1 , . . . , wK ) is κ = n` . The resulting rate of
transmission of each of the K messages is

log p`
`
= log p b/dim.
n
n
The sum rate of all the messages is K`
n log p b/dim.

5

S , σ 2 ) of the multicast channel uses its own side information (S
S , u 1 , . . . , u M ) to expurgate the channel code X and obtain a
Fig. 3. Each receiver (S
S , u 1 , . . . , u M ). Note that the resulting subcodes can be different across the receivers. In order to achieve the capacity of the multicast channel,
subcode X (S
we require that each of these expurgated codes be good for channel coding over the point-to-point AWGN channel.

S , σ 2 ) over a block of ` realizations
The side information at (S
PK
of the K message symbols is of the form k=1 sm,kw k =
S ) and u m ∈ F`p .
u m , m = 1, . . . , M , where M = rank(S
This side information allows the receiver to conclude that the
transmitted codeword must belong to the following subcode
S , u 1 , . . . , u M ) of X ,
X (S
n
w 1 , . . . , w K ) w 1 , . . . , w K ∈ F`p ,
ρ(w
K
X

sm,kw k = u m

o
for m = 1, . . . , M .

(3)

k=1

S , σ 2 ) decodes the channel output
The optimal decoder at (S
vector to the nearest codeword x̂ of this subcode, and the error
probability at this receiver is the probability that the estimated
x̂
message tuple ρ−1 (x̂
x̂) is not equal to the transmit message
w 1 , . . . , w K ). In order to achieve the optimal performance at
(w
S , σ 2 ), we thus require that the expurgated
a given receiver (S
S , u 1 , . . . , u M ) be a good channel code for the pointcode X (S
to-point AWGN channel. In the multicast channel that consists
of multiple receivers, the side information matrix S can vary
from one receiver to the next, and hence, the expurgated codes

can be different at each receiver, see Fig. 3. Hence, a capacityachieving channel code X is such that the resulting expurgated
code at every receiver is a good channel code for the AWGN
channel.

Problem Statement
Problem Setup: Consider a common message Gaussian
broadcast channel with single transmitter and N receivers.
The transmitter desires to multicast K independent messages from a prime field Fp subject to the unit power
constraint (2) on the transmit codeword. Each of the N
2
S 1 , σ12 ), . . . , (S
S N , σN
receivers (S
) has coded side information
corresponding to the side information matrix S i ∈ FpMi ×K ,
i = 1, . . . , N , and experiences an additive white Gaussian
noise of variance σi2 , i = 1, . . . , N . Without loss of generality,
we assume that each of the side information matrices S i has
S i ) = Mi . Using the
linearly independent rows, i.e., rank(S
information-theoretic arguments of [17], which is based on the
average performance of an ensemble of randomly generated
codebooks, it can be shown that the (symmetric) capacity of

6

this multicast channel is


1
1
1
C = min
· log2 1 + 2 .
σi
i∈{1,...,N } (K − Mi ) 2

(4)

The proof of this result is similar to the proof of Theorem 6
of [17] which considers a discrete memoryless common message broadcast channel where the side information at each
receiver is, in general, a random variable jointly distributed
with the source messages (w1 , . . . , wK ). A sketch of the proof
that C is the capacity for the Gaussian multicast channel
with coded side information at the receivers is given in the
appendix.
Problem Statement: Let , ζ > 0 be fixed positive real
numbers and let R ≤ C − . We seek to determine whether
there exists a lattice code for the multicast channel with coded
side information at the receivers that transmits each of the K
messages with rate at least (R − ) such that the probability
of decoding error at each of the N receivers is at the most ζ.
In this paper we answer the above stated problem in the
affirmative under the assumption that the prime field Fp is
sufficiently large. In particular, we prove the existence of a
lattice code with the saidproperties when the prime p satisfies

the inequality p ≥ max 22KR , (2 4 − 1)−1 2−R . Unlike the
capacity (4) which holds for any value of p, our result on
the optimality of lattice codes requires that p vary with the
tolerance . The larger the gap to capacity , the smaller is the
size requirement on the prime field Fp .
B. Lattice Preliminaries
We now briefly recall the necessary properties of lattices
and lattice codes, and establish our notation and terminology.
The material presented in this section consists of standard
ingredients used in the literature, and is mainly based on [5],
[8], [42], [43].
1) Lattices and Lattice Codes: Throughout this manuscript
we consider n-dimensional lattices Λ with full-rank generator
matrix. The closest vector lattice quantizer corresponding to Λ
is denoted by the function QΛ : Rn → Λ, and the volume of
0) is denoted
its (fundamental) Voronoi region V(Λ) = Q−1
Λ (0
by Vol(Λ). For any λ ∈ Λ, λ + V(Λ) is the set of all points
in Rn that are mapped to λ under QΛ , and it has the same
volume Vol(Λ) as V(Λ). For any two distinct lattice points
λ 1 6= λ 2 , the sets λ 1 + V(Λ) and λ 2 + V(Λ) are disjoint.
x] mod Λ = x − QΛ (x
x),
The modulo-Λ operation, defined as [x
satisfies the following properties for all x , x 1 , x 2 ∈ Rn
x] mod Λ ∈ V(Λ),
[x


x1 + x 2 ] mod Λ = [x
x1 ] mod Λ + x 2 mod Λ, and (5)
[x
x] mod Λ = 0 if and only if x ∈ Λ.
[x
(6)
We will denote the n-dimensional ball of radius r with center
x ∈ Rn | kx
x − s k ≤ r}, and
s ∈ Rn as B(ss, r), i.e. B(ss, r) = {x
the volume of a unit-radius ball in n dimensions by Vn . It
follows that the volume of B(ss, r) equals Vn rn . The covering
radius of the lattice Λ is denoted by rcov (Λ) and the effective
radius of Λ by reff (Λ). We recall that reff (Λ) ≤ rcov (Λ) and

1
Vol(Λ) n
.
(7)
reff (Λ) =
Vn

Rogers [44] showed that for every dimension n there exists a
lattice Λ such that
 n1
1
rcov (Λ) 
≤ c n (ln n) 2 log 2πe
,
(8)
reff (Λ)
where c is a constant. Note that the right hand side of the
above inequality converges to 1 as n → ∞. A sequence of
lattices of increasing dimension n is said to be Rogers-good
→ 1. Rogers’ result (8) shows that such a sequence
if rrcov
eff
exists (see also [45]).
Let Λc ⊂ Λ be a pair of nested lattices and d ∈ V(Λc )
be a fixed vector. A (nested) lattice code or a Voronoi code
(Λ − d )/Λc is the set (Λ − d ) mod Λc obtained by applying
the mod Λc operation on the points of the lattice translate
Λ − d . The code consists of all the points in Λ − d that lie
within the Voronoi region of Λc , i.e., (Λ − d ) ∩ V(Λc ). The
lattice Λc is called the coarse lattice or the shaping lattice,
Λ is called the fine lattice or the coding lattice, and d is the
dither vector. The cardinality of this code is |(Λ − d )/Λc | =
c)
x ∈ (Λ − d)/Λc
|Λ/Λc | = Vol(Λ
Vol(Λ) , and every codeword point
xk ≤ rcov (Λc ). Note that Λ/Λc is a lattice code with
satisfies kx
zero dither.
2) Lattice Codes from Linear Codes over a Finite Field:
In this subsection we briefly describe the method proposed
in [15] to construct a pair Λc ⊂ Λ of nested lattices, and
recall its relevant properties. This construction uses a coarse
lattice Λc and a linear code C to generate a fine lattice Λ such
that |Λ/Λc | = |C |.
Let g(·) denote the natural map that embeds Fp =
{0, 1, . . . , p − 1} into Z. When applied to vectors, g(·) acts
independently on each component of a vector. Let C ⊂ Fnp be
a linear code of rank L, 1 ≤ L ≤ n,

C = Gw | w ∈ FL
p ,
where G is the n × L generator matrix with full column rank,
and w is the message encoded to C . The set g(C ) + pZn
obtained by tiling copies of g(C ) at every vector of pZn is
a lattice in Rn and is known as the Construction A lattice
of the linear code C [5]. Note that the number of points in
g(C )+pZn contained in the Voronoi region of the lattice pZn
is |C | = pL . We obtain Λ by scaling down the Construction A
lattice by p−1 and transforming it by the generator matrix B c
of Λc
Λ = B c p−1 (g(C ) + pZn ) = B c p−1 g(C ) + B c Zn
= B c p−1 g(C ) + Λc .
Since C contains the all zero codeword, it follows that
Λ ⊃ B c p−1 g(00) + Λc = Λc . We observe that applying the
transformation B c p−1 to the lattice pZn (instead of the lattice
g(C ) + pZn ) generates Λc (instead of Λ). Hence, Λ/Λc has
the same algebraic structure as that of (g(C ) + pZn )/pZn ,
which in turn, is equivalent to the linear code C . In particular,
|Λ/Λc | = |C | = pL .

(9)

The following lemma provides an explicit bijection between
the message vectors w ∈ FL
p encoded by C and the points in
the lattice code Λ/Λc . This result, which is originally from [15,
Lemma 5], is proved below for completeness.

7



Gw
Lemma 1. The map w → B c p−1 g (Gw
Gw) mod Λc is a
bijection between FL
p and Λ/Λc .

the single-user AWGN channel, and we have the following
corollary.

L
Proof: From (9), we know that |Λ/Λc | = |FL
p| = p .
Hence, it only remains to show that no two distinct messages
w A and w B are mapped to the
point in
 same
 Λ/Λc . As−1 Gw
suming
the
contrary,
we
have
B
p
g(Gw
)
mod Λc =
A
c


Gw B ) mod Λc . Using (5) and (6), we obtain
B c p−1 g(Gw

Corollary 1. Consider a single user AWGN channel where
the input is subject to unit power constraint and the noise
variance at the receiver is σ 2 . Let  > 0 be any constant and
let


1
1
R ≤ log 1 + 2 − .
2
σ

Gw A ) − B c p−1 g(Gw
Gw B ) ∈ Λc .
B c p−1 g(Gw
B −1
pB
c ,

Gw A ) −
Multiplying both sides by
we obtain g(Gw
Gw B ) ∈ pZn . Reducing this result modulo-p, we have
g(Gw
Gw B = 0 over Fp . Since this implies G (w
w A −w
wB ) = 0
Gw A −Gw
over Fp while w A − w B 6= 0 and G has full column rank, we
have arrived at a contradiction.
In order to prove capacity achievability, we will rely on
random coding arguments to show the existence of a good
choice of G. As in [15], we will assume that G is a random
matrix chosen with uniform probability distribution on Fn×L
.
p
The following result is useful in upper bounding the decoding
error probability over the ensemble of random codes.
0} be a given
Lemma 2 ([15], [41], [45]). Let w ∈ FL
p \{0
non-zero
vector,
and
let
G
be
uniformly
distributed
in Fn×L
.
p


−1 Gw
Then B c p g(Gw
Gw) mod Λc is uniformly distributed over
p−1 Λc ∩ V(Λc ), i.e., over the lattice code p−1 Λc /Λc .
III. L ATTICE C ODES FOR THE C OMMON M ESSAGE
G AUSSIAN B ROADCAST C HANNEL WITH C ODED S IDE
I NFORMATION
We will assume that the number of messages K and a design
rate R are given, and show that there exist good lattice codes of
sufficiently large dimension n that encode K messages over an
appropriately chosen prime field Fp at rates close to R b/dim.
In order to rigorously state the main result, we consider a fixed
non-zero tolerance  > 0 that determines the gap to capacity.
Theorem 1 (Main theorem). Let the number of messages
K, design rate R and tolerance  > 0 be given. For every
sufficiently large prime integer p, there exists a sequence of
lattice codes of increasing dimension n that encode K message
vectors over Fp such that the rate of transmission of each
message is at least (R − ) b/dim and the probability of error
S , σ 2 ) decays exponentially in n if
at a receiver (S


1
1
S )).
log 1 + 2 ≥ (R + ) (K − rank(S
(10)
2
σ
To prove Theorem 1, we utilize the lattice code ensemble
introduced in [15]; see Section II-B2 of this paper. A Rogers’
good lattice is chosen as the coarse lattice Λc . The fine lattice
Λ is obtained from the generator matrix B c of the coarse lattice
Λc and a linear code C over a large enough prime field Fp
using the construction described in Section II-B2.
The multicast channel considered in Theorem 1 reduces
to the traditional single-user AWGN channel if the number
of messages K = 1, and the multicast channel consists of
one receiver with an empty side information matrix S , i.e.,
S ) = 0. Hence, Theorem 1 provides an alternative proof
rank(S
of the existence of lattice codes that achieve the capacity of

For every sufficiently large prime integer p, there exists a sequence of lattice codes of increasing dimension n constructed
from linear codes over Fp (as described in Section II-B2)
such that the rate of each lattice code is at least R − 
and the probability of decoding error at the receiver decays
exponentially in n.
The relation of Corollary 1 to existing results on the
optimality of Construction A based lattice codes in single-user
AWGN channel is described in detail in Section IV-D2.
In the rest of this section we describe the construction
of random lattice codes, and the encoding and decoding
operations used to prove Theorem 1. We provide the proof
of the Theorem 1 in Section IV.
A. Random lattice code ensemble
1) Prime p: Given the design rate R, number of messages
K and tolerance  > 0, we require p to satisfy the constraint


(11)
p ≥ max 22KR , (2 4 − 1)−1 2−R .
The coding schemes of this paper are based on Construction A
lattices which are obtained by lifting linear codes over Fp to
the Euclidean space Rn . The generator matrices of these Fp linear codes are constructed randomly, and the first constraint
in (11), viz. p ≥ 22KR , will allow us to show that these
randomly constructed generator matrices are full-ranked with
probability close to 1.
The proof of Theorem 1 given in Section IV involves the
derivation of an upper bound on the probability of decoding
error averaged over an ensemble of lattice codes derived from

Construction A. We will use the inequality p ≥ (2 4 −1)−1 2−R
from (11) to show that this upper bound is exponentially small
in dimension n. Note that this inequality implies


p ≥ (2 4 − 1)−1 2−(R+)(K−M )
for any integer M satisfying 0 ≤ M ≤ K − 1. Rearranging
the terms in the above inequality we obtain
1
p 2(R+)(K−M )



+ 1 ≤ 24 .

(12)

2) Message length `: Once p is fixed, we choose ` as the
largest integer that satisfies
`
log p ≤ R.
(13)
n
The left-hand side in the above inequality is the actual rate at
which the lattice code encodes each message, while R is the
design rate. The difference between the two is at the most
`+1
`
log p
log p − log p =
n
n
n

8

Fig. 4.

The encoding operation at the transmitter that maps the messages w 1 , . . . , w K to a point in (Λ − d )/Λc .

which converges to 0 as n → ∞. It follows that the code rate
`
n log2 p tends to the design rate R as n → ∞, and hence,
`
n log2 p ≥ R −  for all sufficiently large n.
3) Coarse Lattice Λc : From (8) in Section II-B1, we know
that for a given  > 0 and for all sufficiently large n, there
exists an n-dimensional lattice Λc such that

rcov (Λc )
≤ 24 .
reff (Λc )

We will choose such a Rogers-good lattice as Λc , and scale it
so that
√
rcov (Λc ) = n.

√
It follows that reff (Λc ) ≥ 2− 4 rcov (Λc ) = 2− 4 n. Using the
definition of the effective radius (7), we arrive at the following
lower bound on the volume of the Voronoi region of Λc
n

n
Vol(Λc ) = Vn reff
(Λc ) ≥ Vn n 2 2−

n
4

.

(14)

4) Fine Lattice Λ: The fine lattice is obtained by the
construction of [15] described in Section II-B2. The length
of the linear code C is n, and its rank L = K` is the number
of message symbols to be encoded by the lattice code. Note
that this requires that K` < n be true. Using (13) and the
property p ≥ 22KR , we have
K` ≤

nKR
nKR
n
≤
=
log p
2KR
2

(15)

which ensures that K` < n. If G ∈ Fn×K`
is the generator
p
matrix of C , then Λ = B c p−1 g(C ) + Λc . We will choose G
uniformly random over the set of all n × K` matrices of Fp ,
resulting in a random ensemble of fine lattices Λ.
5) Dither vector d : We will rely on random coding arguments to prove the existence of a translate d such that the code
(Λ −dd)/Λc performs close to capacity. We will assume that d
is distributed uniformly in V(Λc ) and is chosen independently
of G . This random dither d is usually viewed as a common
randomness available at the transmitter
and the receivers [8].
√
Note that kddk ≤ rcov (Λc ) = n.

C , and maps it to a point t ∈ Rn using Construction A as
follows


Gw
t = B c p−1 g (Gw
Gw) mod Λc .
(16)
From the discussion in Section III-A, we know that
Gw
B c p−1 g(Gw
Gw) ∈ Λ, and hence, t ∈ Λ/Λc . Finally, the transmit
codeword x is generated by dithering t ,


Gw
x = [tt − d ] mod Λc = B c p−1 g (Gw
Gw) − d mod Λc . (17)
This sequence of operations
is illustrated in Fig. 4. Note that
√
xk ≤
since rcov (Λ√c ) = n, each codeword x satisfies kx
xk2 /n ≤ 1.
rcov (Λc ) = n, and hence, the power constraint kx
It is straightforward to show that the dithering operation (17)
is a one-to-one correspondence between t ∈ Λ/Λc and
x ∈ (Λ −dd)/Λc . Further, from Lemma 1 we know that (16) is
a bijection between the message space FK`
p and the undithered
codewords Λ/Λc if G is full rank. Hence, to ensure that no two
messages are mapped to the same codeword, we only require
that the random matrix G be full rank. It can be shown that
(see [45])
G) < K`) ≤ p−(n−K`) .
P (rank(G
We will only require a relaxation based on the above inequality. From (15), we have K` ≤ n2 . Similarly, since p is a prime
integer, we have p ≥ 2, and hence,
G) < K`) ≤ 2−(n− 2 ) = 2− 2 .
P (rank(G
n

n

(18)

C. Decoding
The receiver employs a two stage decoder: in the first stage
the receiver identifies the subcode of (Λ−dd)/Λc corresponding
to the available side information, and in the second stage it
decodes the channel output to a point in this subcode.
1) Using Side Information to Expurgate Codewords: The
S , σ 2 ) over a block of ` realizations of
side information at (S
the K messages is of the form
K
X

sm,kw k = u m ,

m = 1, . . . , M.

(19)

k=1

B. Encoding
We will now describe the encoding operation ρ at the
w1, . . . , w K ) ∈
transmitter that maps the message vectors (w
F`p × · · · × F`p to a codeword x ∈ (Λ − d )/Λc . The encoder
first concatenates
| the K messages into the vector w =
w |1 , · · · , w |K , encodes w to a codeword in the linear code

The receiver desires to identify the set of all possible values
|
of the message vector w = w |1 , · · · , w |K that satisfy (19).
|
|
|
`
∈ FM
Using the notation u = u 1 , · · · , u M
p , the side
information (19) can be rewritten compactly in terms of w
and u as
S ⊗ I `) w = u,
(S
(20)

9

where ⊗ denotes the Kronecker product of matrices and I ` is
the `×` identity matrix over Fp . Observe that (20) is an underdetermined system of linear equations, and the set of solutions
K`×(K−M )`
is a coset of the null space of S ⊗ I ` . Let AS ∈ Fp
S ⊗ I ` )A
AS = 0 , i.e.,
be a rank (K − M )` matrix such that (S
the columns of AS form a basis of the null space of S ⊗ I ` .
Then the set of all solutions to (20) is
n
o
)`
v + AS w̃ | w̃ ∈ F(K−M
,
(21)
p
where v is the coset leader. From (16), we conclude that the
undithered codeword must be of the form


)`
Gv + GAS w̃
t = B c p−1 g (Gv
w̃) mod Λc , w̃ ∈ F(K−M
.
p
(22)
We will now use the property of g(·) that for any a , b ∈ Fnp ,
a + b ) = g(a
a) + g(bb) mod p.
g(a
Gv + GAS w̃
Gv
GAS w̃
Therefore, g(Gv
w̃) = g(Gv
Gv) + g(GA
w̃) + pcc for
some c ∈ Zn . Using this in (22), we obtain


Gv
GAS w̃
t = B c p−1 g (Gv
Gv) + B c p−1 g (GA
w̃) + B cc mod Λc
h


Gv
GAS w̃
= B c p−1 g (Gv
Gv) + B c p−1 g (GA
w̃) mod Λc
i
+ [ B cc ] mod Λc mod Λc




Gv
GAS w̃
= B c p−1 g (Gv
Gv) + B c p−1 g (GA
w̃) mod Λc mod Λc ,
(23)
where we have used (5), (6) and the fact that B cc ∈ Λc . Since
the receiver knows v , the component of t unavailable from the
side information is


GAS w̃
t̃ = B c p−1 g (GA
w̃) mod Λc .
(24)
Let CS ⊂ Fnp be the subcode of C with generator matrix GAS ,
and ΛS be the lattice obtained by applying Construction A to
CS and transforming it by B c p−1 , i.e.,
ΛS = B c p−1 g(CS ) + Λc .
Using GAS instead of G in Lemma 1, we see that t̃ ∈ ΛS /Λc
and that (24) is a one-to-one correspondence between w̃ ∈
(K−M )`
Fp
and t̃ ∈ ΛS /Λc as long as GAS is full rank. Together
with (17), (23), and (24), we conclude that the transmit vector
x belongs to the following lattice subcode of (Λ − d )/Λc ,

Gv
ΛS + B c p−1 g (Gv
Gv) − d /Λc =


Gv
t̃ + B c p−1 g(Gv
Gv) − d mod Λc t̃ ∈ ΛS /Λc .
(25)
The decoding problem at the second stage is to estimate t̃t̃, or
equivalently w̃
w̃, from the channel output.
2) MMSE Scaling and Lattice Decoding: Let the channel
S , σ 2 ) be y = x + n , where n
output at the receiver (S
is a Gaussian vector with zero mean and variance σ 2 per
dimension. The received vector is scaled by the coefficient
α, resulting in
x + αn
n = x + αn
n − (1 − α)x
x.
αyy = αx

(26)

This MMSE pre-processing improves the effective signal-tonoise ratio of the system beyond the channel signal-to-noise

ratio σ12 and allows the lattice decoder to perform close to
capacity [8], [46]. Let
n − (1 − α)x
x
z = αn
be the effective noise term√in (26). Using the facts that x and
xk ≤ n, and n has zero mean, we have
n are independent, kx
xk2 + α2 E kn
nk2 − 2α(1 − α) E x |n
E kzz k2 = (1 − α)2 E kx
≤ (1 − α)2 n + α2 σ 2 n,
where E is the expectation operator. The choice of
α = 1/(1 + σ 2 ) minimizes this upper bound and yields
E kzz k2 ≤ n σ 2 /(1 + σ 2 ), which is less than the Gaussian noise
nk2 = nσ 2 . In the rest of the paper we will assume
power Ekn
that α = 1/(1 + σ 2 ) and use the notation
σz2 =

σ2
.
1 + σ2

(27)

The lower bound (10) on signal-to-noise ratio can be rewritten
in terms of σz2 as
σz2 ≤ 2−2(R+)(K−M ) .

(28)

Gv
From (25), we know that x = t̃ + B c p−1 g(Gv
Gv) − d + λ c
for some λ c ∈ Λc . After MMSE scaling, the decoder removes
Gv
the contributions of the dither d and the offset B c p−1 g(Gv
Gv)
y
from αy to obtain
Gv
y 0 = αyy − B c p−1 g(Gv
Gv) + d = t̃ + λ c + z .
The decoder proceeds by quantizing y 0 to the lattice ΛS and
reducing the result modulo Λc . If the noise z is sufficiently
‘small’, then this sequence of operations will yield




QΛS (yy0 ) mod Λc = QΛS (t̃ + λ c + z ) mod Λc


= t̃ + λ c mod Λc = t̃t̃.
(29)
Given t̃t̃, the receiver uses (23) to obtain the undithered
w |1 , . . . , w |K )| , as
codeword
t , and hence the

 message vector (w
−1 Gv
t = B c p g(Gv
Gv) + t̃ mod Λc . To conclude, the decoder
obtains the estimate t̂ of the undithered codeword t from the
received vector y as
h
i

t̂ =
Gv
QΛS (yy 0 ) mod Λc + B c p−1 g(Gv
Gv) mod Λc


Gv
= QΛS (yy0 ) + B c p−1 g(Gv
Gv) mod Λc



Gv
Gv
= QΛS αyy − B c p−1 g(Gv
Gv) + d + B c p−1 g(Gv
Gv) mod Λc
which shows that the mod Λc operation arising from (29) can
be ignored. The steps involved in the decoding operation are
illustrated in Fig. 5.
Note that the effective information vector w̃ is not encoded
in the point t̃ ∈ ΛS , but is encoded in the coset t̃ + Λc .
The error event for this decoder is QΛS (yy0 ) ∈
/ t̃ + Λc , i.e.,
QΛS (t̃ + λ c + z ) ∈
/ t̃ + Λc , which is equivalent to the event
QΛS (zz ) ∈
/ Λc . Hence, a decoding error occurs if and only if
z is closer to a point in ΛS \Λc than any vector in the coarse
lattice Λc , i.e., if and only if
E : QΛS (zz ) ∈ ΛS \Λc .

(30)

10

Fig. 5.

S , σ 2 ). The vector v and the lattice ΛS are determined using the side information available at the receiver.
The decoding operation at the receiver (S

IV. P ROOF OF M AIN T HEOREM
In this section we first state and prove two technical lemmas
(Section IV-A), use these lemmas to show that the error
S , σ 2 ) is small (Secprobability at a given fixed receiver (S
tion IV-B), and then complete the proof of the main theorem
by showing that the error probability at every receiver of
the multicast channel is simultaneously small (Section IV-C).
Finally, we state some important corollaries of the main
theorem (Section IV-D).
A. Technical Lemmas
The first result, which is a direct generalization of [9,
Lemma 1] and [10, Lemma 2.3], gives an upper bound on
the number of lattice points lying inside a ball.
Lemma 3. For any s ∈ Rn , r > 0 and any n-dimensional
lattice Λc ,
|Λc ∩ B(ss, r)| ≤

Proof: We will prove (32) for every fixed realization of x
in V(Λc ), which shows that the statement of the lemma is true
for any distribution of x on V(Λc ). In the rest of the proof we
will assume that x ∈ V(Λc ) is an arbitrary fixed vector and n
2
xk2 ≤ rcov
(Λc ) = n, we have
is Gaussian distributed. Using kx
n − (1 − α)x
x k2
kzz k2 = kαn
nk2 + (1 − α)2 kx
xk2 − 2α(1 − α)x
x |n
= α2 kn
nk2 + (1 − α)2 n − 2α(1 − α)x
x |n .
≤ α2 kn

Hence, P kzz k2 > nσz2 (1 + δ) is upper bounded by

nk2 + (1 − α)2 n − 2α(1 − α)x
x|n > nσz2 (1 + δ) .
P α2 kn
From the definition (27) of σz2 , we have nσz2 (1 + δ) =
nα2 σ 2 (1 + δ) + n(1 − α)2 (1 + δ). Hence, the above upper
bound corresponds to the event

Vn
n
(rcov (Λc ) + r) ,
Vol(Λc )

where Vn is the volume of a unit ball in Rn .
Proof: Let R = (Λc ∩ B(ss, r)) + V(Λc ) be the set of
all points in Rn that are mapped to one of the points in
Λc ∩ B(ss, r) by the lattice quantizer QΛc . Since R is a union
of the pairwise disjoint sets λ + V(Λc ), λ ∈ Λc ∩ B(ss, r), and
since each of these sets has volume Vol(Λc ), we have
Vol(R) = Vol(Λc ) |Λc ∩ B(ss, r)|.

Lemma 4. Let x be uniformly distributed in V(Λc ) and δ > 0
be any positive number. Then

n(δ−ln(1+δ))
nσ 2 δ 2
2
+ e− 4 . (32)
P kzz k2 > nσz2 (1 + δ) ≤ e−

(31)

Using the fact that V(Λc ) ⊂ B(00, rcov (Λc )), we have
R = (Λc ∩ B(ss, r)) + V(Λc ) ⊂ B(ss, r) + V(Λc )
⊂ B(ss, r) + B(00, rcov (Λc )) ⊂ B(ss, r + rcov (Λc )),
where the last step follows from triangle inequality. Consequently, we have an upper bound on the volume of R,
Vol(R) ≤ Vol ( B (ss, r + rcov (Λc )) ) = Vn (r + rcov (Λc ))n .
Using this result with (31) proves the lemma.
As in [9], [10], [40], we will rely on the fact that, with
very high probability,
the norm of the noise z is not much
p
larger than nσz2 . The probability that the effective noise z
is ‘large’ is exponentially small in n. The proof of this result
is given below.

nk2 + (1 − α)2 n − 2α(1 − α)x
x |n >
α2 kn
nα2 σ 2 (1 + δ) + n(1 − α)2 (1 + δ). (33)
The event (33) occurs only if at least one of the following two
events occurs
nk2 > nα2 σ 2 (1 + δ), or
EA : α2 kn
(34)
2
|
2
x
n
EB : (1 − α) n − 2α(1 − α)x
> n(1 − α) (1 + δ).
Therefore,
P(kzz k2 > nσz2 (1 + δ)) ≤ P(EA ∪ EB ) ≤ P(EA ) + P(EB ).
We will now individually upper bound P(EA ) and P(EB ), and
thereby complete the proof.
A rearrangement of
 terms in (34) yields P(EA ) =
P k σ1 n k2 > n(1 + δ) . This is the probability that a Gaussian
vector with unit variance per dimension lies outside the sphere
of squared radius n(1 + δ). The following is a well known
upper bound on this probability (see [47])
P(EA ) ≤ e−

n(δ−ln(1+δ))
2

.

x|n > n(1−α)2 δ.
The event EB is equivalent to −2α(1−α)x
2
Using α = 1/(1 + σ ), we can show that this is same as

11

x |n < −nδσ 2 /2. Since x |n is a zero mean Gaussian random
xk2 , we have
variable with variance σ 2 kx




nσδ
nδσ 2
|
=Q
,
P(EB ) = P x n < −
xk
2
2kx
xk ≤
where Q(·)√is the Gaussian tail function. Using kx
rcov (Λc ) = n and the Chernoff bound Q(y) ≤ exp(−y 2 /2),
we arrive at
P(EB ) ≤ e−

nσ 2 δ 2
4

.

This completes the proof.
B. Error probability at a single receiver
In this subsection we derive an upper bound on the decoding
S , σ 2 ) when averaged
error probability PS at a receiver (S
over the ensemble of lattice codes generated by choosing G
uniformly over Fn×K`
and d uniformly over V(Λc ).
p
The following result from [8], known as the Crypto lemma,
captures an important characteristic of random dithering.
Lemma 5 ([8]). Let t ∈ V(Λc ) be any random vector. If d
is independent of t and is uniformly distributed over V(Λc ),
then x = [tt − d ] mod Λc is independent of t and uniformly
distributed over V(Λc ).
The property that the transmit vector x is statistically inden −(1−α)x
x
pendent of t implies that the effective noise z = αn
is independent of the transmit message. This facilitates the
error probability analysis through the observation that the error
event (30) is statistically independent of t̃t̃.
For distinct messages w̃ to be mapped to distinct points t̃t̃,
we require that GAS be full rank. Since AS is full rank, this
is same as requiring that G be full rank. Apart from the event
E : QΛS (zz ) ∈ ΛS \Λc , we assume that the decoder declares an
error whenever the event
G < K`)
G : rank(G
S , σ2 )
occurs. Hence, the error probability PS at the receiver (S
satisfies
PS = P(G ∪ E) ≤ P(G) + P(E).
(35)
From (18), we already know that P(G) is exponentially small
in n.

Using the given design tolerance , p
we set δ = 2 2 − 1,
which is positive if  > 0. Let rz = n(1 + δ)σz2 be the
radius of the typical noise vector and Brz = B(00, rz ). Then,

when averaged over the ensemble of random lattice codes.
Proof: From (30), we note that the decoder is in error
when z is closer to some coset t0 + Λc , with t0 ∈ ΛS /Λc
and t0 6= 0 , than any point in Λc . The number of competing
cosets is |ΛS /Λc \ {00}| = p(K−M )` − 1, and we index them
(K−M )`
using the non-zero vectors w 0 ∈ Fp
\{00}. To each w 0 ,
we associate the coset corresponding to the coset leader


GAS w0 ) mod Λc .
t0 = B c p−1 g(GA
(37)
Since G is random, the coset leader t0 associated with a given
w0 is a random vector. Given that z ∈ Brz and 0 ∈ Λc , the
Euclidean distance between z and Λc is at the most kzz −00k ≤
rz . Hence, for an error event to occur, there must exist a coset
t0 + Λc at a distance less than rz from z , i.e., |(tt0 + Λc ) ∩
B(zz , rz )| 6= 0. Indexing the cosets by w0 , we upper bound
P(E|zz ∈ Brz ) using (38) given in the top of the next page.
The last inequality in (38) follows from the observation

1 (tt0 + Λc ) ∩ B(zz , rz ) 6= 0 ≤ (tt0 + Λc ) ∩ B(zz , rz ) ,
where 1 {·} is the indicator function. Note that the expectation
operation in (38) is with respect to the random vector t0 as
well as the effective noise z .
The matrix AS has full column rank, and hence, AS w0 6= 0
for every w0 6= 0 . Using (37) and applying Lemma 2,
we see that t0 is uniformly distributed in p−1 Λc /Λc =
p−1 Λc ∩ V(Λc ). Further, from Lemma 5 the distribution of
t0 is independent of z. Hence, the probability mass function
of t0 equals | p−1 Λc /Λc |−1 = p−n over every element of
the set p−1 Λc /Λc . Using this result, we further upper
bound P(E|zz ∈ Brz ) as in (39) in the next page, where the
last
from the fact that the set of cosets
 equality follows
a ∈ p−1 Λc /Λc form a partition of p−1 Λc . Since the
a + Λc |a
number of competing w0 in (39) is less than p(K−M )` , and
p−1 Λc ∩ B(zz , rz ) = |Λc ∩ B(pzz , prz )|, we obtain

P(E|zz ∈ Brz ) ≤ p−n p(K−M )` E |Λc ∩ B(pzz , prz )| z ∈ Brz .
Using Lemma 3, we bound the number of lattice points inside
the ball B(pzz , prz ), and obtain
P(E|zz ∈ Brz ) ≤ p−n p(K−M )`

Vn
n
(rcov (Λc ) + prz ) .
Vol(Λc )

Using the bounds p(K−M )` ≤ 2nR(K−M ) , from (13);
n
n
)
Vol(Λc ) ≥ Vn n 2 2− 4 , from (14); σz ≤ 2−(R+)(K−M
√ ,
from p (28);
and
the
relations
rcov (Λc ) = n,

rz = n(1 + δ)σz2 , and 1 + δ = 2 2 , we obtain the sequence
P(E) = P(zz ∈ Brz ) P(E|zz ∈ Brz ) + P(zz ∈
/ Brz ) P(E|zz ∈
/ Brz ) of equalities and upper bounds leading to (40) shown in the
n(K−M )
≥ 2n , and
≤ P(E|zz ∈ Brz ) + P(zz ∈
/ Brz ).
(36) next page. Since K − M ≥ 1, we have 2
hence, the upper bound (40) can be further relaxed as

n
Lemma 4 provides an exponential upper bound on P(zz ∈
/ Brz ).
n
1
In the following theorem we show that P(E|zz ∈ Brz ) is also
P(E|zz ∈ Brz ) ≤ 2− 2
+
1
.
p 2(R+)(K−M )
exponentially small in n. The proof of this result uses the
technique of [9], [10] to bound the number of lattice points Using the inequality (12), which immediately follows from the
choice of the prime integer p, we have
lying in an n-dimensional ball.

n
n
n
1
1
S , σ 2 ) with 2 log 1 + σ2 >
Theorem 2. For any receiver (S
P(E|zz ∈ Brz ) ≤ 2− 2 2 4 = 2− 4 .
S )), and for all large enough n,
(R + ) (K − rank(S
Note that this upper bound holds for all sufficiently large
n
P(E|zz ∈ Brz ) ≤ 2− 4
values of n.

12




[


P(E|zz ∈ Brz ) ≤ P 



(tt0 + Λc ) ∩ B(zz , rz ) 6= 0


z ∈ Brz 

(K−M )`
0}
w0 ∈Fp
\{0



P (tt0 + Λc ) ∩ B(zz , rz ) 6= 0 z ∈ Brz

X

≤

(K−M )`
0}
w0 ∈Fp
\{0



E (tt0 + Λc ) ∩ B(zz , rz ) z ∈ Brz .

X

≤

(38)

(K−M )`
w0 ∈Fp
0}
\{0

P(E|zz ∈ Brz ) ≤

X

=

X

X

a + Λc ) ∩ B(zz , rz )| z ∈ Brz
P(tt0 = a ) E |(a



w0 a ∈p−1 Λc /Λc

X

a + Λc ) ∩ B(zz , rz )| z ∈ Brz
p−n E |(a



w0 a ∈p−1 Λc /Λc

= p−n

X

X

X


a + Λc ) ∩ B(zz , rz )| z ∈ Brz = p−n
E |(a
E p−1 Λc ∩ B(zz , rz ) z ∈ Brz . (39)

w0 a ∈p−1 Λc /Λc

w0

√
n
p
Vn
2
n
+
p
n(1
+
δ)σ
n
n
z
Vn n 2 2− 4
n
n
n  √
n  √
n p
2nR(K−M ) 2 4
n p
2nR(K−M ) 2 4
−(R+)(K−M )
2
+ n(1 + δ)σz
=
+ n(1 + δ)2
=
n
n
p
p
n2
n2
!n
n
n
2nR(K−M ) 2 4 n
1
−(R+)(K−M
)
p
=
+2
n 2 (1 + δ) 2
n
n2
p (1 + δ)

n
n
n 
n
n
1
2nR(K−M ) 2 2
1
≤ 2nR(K−M ) 2 4 2 4
+ 2−(R+)(K−M )
≤ n(R+)(K−M )
+
1
p
2
p 2(R+)(K−M )
n

n
2nR(K−M ) 2 2
1
+
1
.
(40)
= nR(K−M ) n(K−M )
2
2
p 2(R+)(K−M )

P(E|zz ∈ Brz ) ≤ p−n 2nR(K−M )

We will now combine the result of Theorem 2 with (35)
and (36), and upper bound the error probability PS at the
S , σ 2 ) as
receiver (S

for all sufficiently large n. We remark that the minimum
required value of n for this upper bound to hold depends only
, and is independent of the side information matrix S .

PS ≤ P(G) + P(zz ∈
/ Brz ) + P(E | z ∈ Brz ).
C. Completing the proof of the main theorem

Using Theorem 2, Lemma 4 and (18), we obtain
n

PS ≤ 2− 2 + e−

n(δ−ln(1+δ))
2

+ e−

nσ 2 δ 2
4

+ 2−

n
4

,

(41)

for sufficiently large n. Let σmin > 0 be the least noise
standard deviation σ among the finitely many receivers in
2
the multicast channel. Then we have σ 2 δ 2 /4 ≥ σmin
δ 2 /4.

2
Also, δ − ln(1 + δ) > 0 as long as δ = 2 − 1 is positive.
Consequently, the parameter



 2 2 
1
δ − ln(1 + δ)
σmin δ

ε = min
, log e
, log e
,
2
2
4
4
is positive, and the value of each of the terms on the right-hand
side of (41) is at the most 2−nε . Hence the error probability
S , σ 2 ) can be upper bounded as
at the receiver (S
PS ≤ 4 · 2−nε ,

(42)

The bound (42) shows that the error probability for a fixed
side information matrix S , averaged over the random code
ensemble, tends to 0 as the code dimension increases. Hence,
there exists a choice of lattice code (which is chosen for the
given side information matrix S ) with a small error probability
at this receiver. We want to prove a slightly stronger result,
viz., there exists a lattice code such that the decoding error
probability for every possible side information matrix S is
small as long as the receiver SNR is large enough. In order to
prove this result, we consider a hypothetical multicast network
that consists of one receiver for each possible choice of the
matrix S . Note that two distinct values of the matrix S that
have identical row space constitute equivalent receiver side
information configurations. Hence, it is enough to consider a
multicast channel that consists of one receiver corresponding

13

to each possible subspace of FK
p , where the dimension of
the subspace can be between 0 and K − 1. A subspace of
dimension M , 0 ≤ M ≤ K − 1, can be mapped to an
M × K matrix whose rows form a basis of the subspace. This
map embeds the set S of all non-equivalent choices of side
M ×K
information matrix S into ∪K−1
, which is the set of all
M =0 Fp
matrices over Fp with K columns and at the most K −1 rows.
Hence, the number of receivers |S| can be upper bounded as
|S| ≤

K−1
X

×K
=
FM
p

M =0

K−1
X

2

pM K ≤ KpK .

(43)

M =0

S , σ 2 ), S ∈ S, satisfies the
We assume that each receiver (S
lower bound (10) on SNR and outputs an estimated message
S ) using its own channel observation. We say that
vector ŵ
ŵ(S
the multicast network is in error if any of the receivers
commits a decoding error. Using a union bound argument and
the upper bounds (42) and (43), we see that the network error
probability Pnet averaged over the random ensemble of lattice
codes satisfies
!
[
S ) 6= w }
Pnet = P(network error) = P
{ŵ
ŵ(S
S ∈S

≤

X

X

S ) 6= w }) =
P ({ŵ
ŵ(S

S ∈S

PS

S ∈S
2

≤ 4K pK 2−nε ,

(44)

which tends to 0 as n becomes arbitrarily large. Hence, for
every sufficiently large n, there exists a lattice code such
that the network error probability is as small as desired. In
particular, this implies that there exists a choice of lattice
code such that the decoding error probability at every receiver
S , σ 2 ), S ∈ S, is simultaneously small. This completes the
(S
proof of the main theorem.
D. Corollaries
1) Almost all lattice codes are good: Using standard arguments based on Markov inequality [8], [9], [46], we show that
almost all codes from the random lattice code ensemble yield
a small error probability. In order to prove this, it is sufficient
to show that for almost all lattice codes the network error
probability is small over the hypothetical multicast channel
that consists of one receiver for each possible side information
matrix.
For a given dimension n, all the lattice codes in the random
code ensemble use the same coarse lattice Λc , but differ in the
choice of the fine lattice Λ and/or the dither vector d . Let
X(Λ, d ) = P(network error |Λ, d )
denote the network error probability for a given choice of Λ, d
in the hypothetical multicast channel. If Λ and d are chosen
randomly, then X is a random variable. From (44), we know
that the expected value of X, which is equal to the average
network error rate Pnet , is small. Suppose we want a lower
bound on the fraction of random codes with error probability
nε
at the most 2− 2 . Using Markov inequality, we have
2

P X > 2−

nε
2



≤

2
nε
E (X)
4K pK 2−nε
= 4K pK 2− 2 .
nε ≤
nε
−
2 2
2− 2

It follows that, asymptotically in n, for almost all choices of
the fine lattice Λ and dither vector d , the resulting lattice code
(Λ − d )/Λc provides an exponentially small error probability
in the multicast channel, i.e.,
nε 
lim P X ≤ 2− 2 = 1.
n→∞

2) Goodness in single-user AWGN channel: Our model
of multicast channel includes as a special case the singletransmitter single-receiver AWGN channel with no side information at the receiver, i.e., number of messages K = 1, side
S) = M =
information matrix S is the empty matrix and rank(S
0. The decoder for this receiver uses the ` × ` identity matrix
for AS and the all zero vector for v , see (21). Specializing
the main theorem for a single receiver with M = 0, we
immediately deduce that the ensemble of random lattice codes
achieves the capacity of the single-user AWGN channel and
hence arrive at Corollary 1.
It is well known that (nested) lattice codes, and lattice
constellations in general, can achieve the capacity of the pointto-point AWGN channel [7]–[11]. Our corollary to the main
theorem provides an alternate proof of this result which is
based only on simple counting arguments.
The proof technique presented in this paper relies on lattices
obtained by applying Construction A to random linear codes
over a large enough prime field Fp . This technique was
introduced by Loeliger in [40] and used in [8]–[10] to prove
the goodness of lattice codes in AWGN channel. Each of these
results requires a different choice of the prime p and places
different requirements on the characteristics of the coarse
lattice Λc . The following are some of the properties that have
been used in the literature:
• Rogers-good: the ratio of covering radius rcov (Λc ) to the
effective radius reff (Λc ) of the lattice must be close to 1,
see (8). Such a lattice is also said to be good for covering.
• MSE-good: the value of the lattice parameter
Z
1
xk2 dx
x,
kx
2
n Vol(Λc )1+ n V(Λc )
known as the normalized second moment, is close to
1/2πe, see [45]. Every Rogers-good lattice is also MSEgood, and hence, this is a weaker requirement.
• Poltyrev-good: such a lattice, when used as an infinite
constellation, achieves the capacity of an AWGN channel
in which the transmitter has no power constraints [45],
[47]. These lattices are resilient against additive white
Gaussian noise.
The achievability result of [8] requires Λc to be simultaneously Rogers-good and Poltyrev-good, and uses p = 2nR ,
i.e., the prime field Fp used for Construction A varies with
the dimension of the lattice code and the size of the field
increases exponentially in n. The random code ensemble of [9]
uses an MMSE-good lattice for Λc , lets p grow as n1.5 , and
can accommodate a wide class of channel noise statistics,
including white Gaussian noise. The code construction of [10]
requires p to be at least n0.5 , needs no dithering operation, i.e.,
uses d = 0 , but is known to achieve capacity only if SNR > 1.
In comparison, our proof method uses a fixed (albeit large)

14

value of p and holds for any SNR > 0, while requiring that
Λc be Rogers-good.
V. C ONCLUSION
We have showed that lattice codes are optimal for common message broadcast in Gaussian channels where receivers
have side information in the form of linear combinations
of source messages. We used random lattice ensembles obtained by applying Construction A to linear codes over appropriately
large prime fields Fp . The lower bound p ≥


max 22KR , (2 4 − 1)−1 2−R on the value of p does not
necessarily pose a limitation in communication applications.
For instance, in the relay network of Example 1, the first
phase of the protocol, namely compute-and-forward [15], only
requires that np → 0 as n → ∞, which can be met by our
scheme by varying p with the dimension n: for instance, by
choosing p to be the smallest prime greater than or equal
to nβ for a fixed β > 1. This will also ensure that the

inequality p ≥ max 22KR , (2 4 − 1)−1 2−R holds for all
sufficiently large values of n. Similarly, with Example 2, where
the broadcast signal supplements a wired multicast network, it
is known that wireline network codes meeting the max-flow
bound exist over every large enough finite field [26]. Hence,
we can choose p to be sufficiently large to simultaneously
optimize both the wired and wireless parts of the hybrid
network. On the other hand, designing lattice strategies for
a fixed small size of the finite field, especially sizes that are
powers of two, may have greater practical significance.
The capacity of the Gaussian broadcast channel with receiver side information under general message demands, such
as with private message requests, is known only for some
special cases [29], [48], [49]. The proofs for achievability in
these cases utilize ensembles of codebooks generated using
the Gaussian distribution together with dirty-paper and superposition coding. It will be interesting to examine if the lattice
structure of the codes proposed in this paper can be exploited
to derive new capacity results beyond the known cases.
A PPENDIX
C APACITY OF THE C OMMON M ESSAGE G AUSSIAN
B ROADCAST C HANNEL WITH C ODED S IDE I NFORMATION
Consider the problem setup with a single transmitter and N
2
S 1 , σ12 ), . . . , (S
S N , σN
receivers (S
) as described in Section II-A.
We now provide a sketch of the proof that C, defined in (4),
is the capacity of this channel.
A. Converse
Suppose there exists a coding scheme that achieves rate
R in the multicast channel with vanishing decoding error
probability at all the receivers. Let the scheme transmit one
realization of (w1 , . . . , wK ) for every κ channel uses, i.e.,
R = κ1 log2 p. From (1) the conditional entropy of each
S i , σi2 ), given
realization of (w1 , . . . , wK ) at the ith receiver (S
the corresponding coded side information, is (K − Mi ) log2 p.
The per-channel use conditional entropy of the message is thus
(K − Mi ) log2 p
= (K − Mi ) R.
κ

In order to guarantee reliable communication it is necessary
that the mutual information between the channel input at the
transmitter and the channel output at the ith receiver be greater
than the conditional entropy (K − Mi ) R. Since the input
power is constrained to be at the most 1 and the noise variance
2
at the ith receiver
 is σi , the maximum mutual information is
1
1
2 log2 1 + σi2 , and hence we have


1
1
(K − Mi ) R < log2 1 + 2 , or equivalently,
2
σi


1
1
1
R<
· log2 1 + 2 .
(K − Mi ) 2
σi
Considering all the N receivers we immediately deduce that
R < C.
B. Achievability
The proof of achievability closely follows the proof of
Theorem 6 of [17] and the standard textbook argument used
for the achievability of the capacity of single-user AWGN
channel. Let  > 0 be any constant. For a given code length
n choose the message length ` as the largest integer such that
the rate R = n` log2 p satisfies


1
1−
1
· log2 1 + 2
− 3.
R < min
σi
i∈{1,...,N } (K − Mi ) 2
As n → ∞, it is straightforward to show that R converges
to the right-hand side of the above inequality. For each of
|
w |1 , . . . , w |K ) ∈ FK`
the 2nKR message vectors w = (w
p ,
w ) ∈ Rn each of whose components
associate a codeword x (w
are generated independently using the Gaussian distribution
with zero mean and variance (1 − ). These 2nKR vectors
constitute the randomly-generated n-dimensional codebook X .
Encoding: If the source message is w , the transmitter
w ) over n channel uses.
broadcasts the vector x (w
S i , σi2 ) that obDecoding: Consider the ith receiver (S
y
serves the channel output i and the side information
PK (i)
(i)
(i)
k=1 sm,k w k = u m , m = 1, . . . , Mi , where S i = [sm,k ].
As in (3), the receiver determines the subcode Xsub =
(i)
S i , u (i)
X (S
1 , · · · , u Mi ) of the codebook X that corresponds to
the set of all message vectors w which are consistent with
the observed coded side information. Among the codewords
in Xsub , the decoder chooses the vector that is jointly (weakly)
-typical with y i . If there exists a unique such codeword x (ŵ
ŵ)
x(ŵ
that additionally satisfies the power constraint kx
ŵ)k2 ≤ n,
the receiver declares ŵ as the decoded message. Otherwise the
receiver declares a decoding error.
Given that Xsub consists of 2n(K−Mi )R vectors generated
independently using the Gaussian distribution with zero mean
and variance (1 − ) and


1
1−
(K − Mi ) R < log2 1 + 2
− 3,
2
σi
it is routine to show that the probability of decoding error
at the ith receiver, averaged over the ensemble of codebooks,
decays exponentially with code length n [50, proof of Theorem 10.1.1]. It follows that the probability that any of the N
receivers commits a decoding error is also exponentially small

15

in n. Hence, there exists at least one codebook X that transmits
each message at rate R with the decoding error probability at
all the receivers as small as desired. Letting n → ∞ and
 → 0, we observe that any rate R < C is achievable.
ACKNOWLEDGMENT
The authors would like to thank the anonymous reviewers
whose comments have improved the content and the presentation of this paper.
R EFERENCES
[1] J. Körner and K. Marton, “How to encode the modulo-two sum of binary
sources (corresp.),” IEEE Trans. Inf. Theory, vol. 25, no. 2, pp. 219–221,
Mar. 1979.
[2] R. Zamir, S. Shamai, and U. Erez, “Nested linear/lattice codes for
structured multiterminal binning,” IEEE Trans. Inf. Theory, vol. 48,
no. 6, pp. 1250–1276, Jun. 2002.
[3] B. Nazer and M. Gastpar, “The case for structured random codes in
network capacity theorems,” European Transactions on Telecommunications, vol. 19, no. 4, pp. 455–474, 2008.
[4] G. Forney, “Coset codes. I. Introduction and geometrical classification,”
IEEE Trans. Inf. Theory, vol. 34, no. 5, pp. 1123–1151, Sep. 1988.
[5] J. H. Conway and N. Sloane, Sphere packings, lattices and groups. New
York: Springer-Verlag, 1999.
[6] R. de Buda, “The upper error bound of a new near-optimal code,” IEEE
Trans. Inf. Theory, vol. 21, no. 4, pp. 441–445, Jul. 1975.
[7] 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.
[8] U. Erez and R. Zamir, “Achieving 12 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.
[9] O. Ordentlich and U. Erez, “A simple proof for the existence of “good”
pairs of nested lattices,” IEEE Trans. Inf. Theory, vol. 62, no. 8, pp.
4439–4453, Aug. 2016.
[10] N. Di Pietro, “On infinite and finite lattice constellations for the additive
white Gaussian Noise Channel,” Theses, Université de Bordeaux, Jan.
2014. [Online]. Available: https://tel.archives-ouvertes.fr/tel-01135575
[11] C. Ling and J.-C. Belfiore, “Achieving AWGN channel capacity with
lattice Gaussian coding,” IEEE Trans. Inf. Theory, vol. 60, no. 10, pp.
5918–5929, Oct. 2014.
[12] U. Erez, S. Shamai, and R. Zamir, “Capacity and lattice strategies for
canceling known interference,” IEEE Trans. Inf. Theory, vol. 51, no. 11,
pp. 3820–3833, Nov. 2005.
[13] W. Nam, S.-Y. Chung, and Y. H. Lee, “Capacity of the Gaussian twoway relay channel to within 12 bit,” IEEE Trans. Inf. Theory, vol. 56,
no. 11, pp. 5488–5494, Nov. 2010.
[14] M. Wilson, K. Narayanan, H. Pfister, and A. Sprintson, “Joint physical
layer coding and network coding for bidirectional relaying,” IEEE Trans.
Inf. Theory, vol. 56, no. 11, pp. 5641–5654, Nov. 2010.
[15] 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.
[16] C. Feng, D. Silva, and F. R. Kschischang, “An algebraic approach to
physical-layer network coding,” IEEE Trans. Inf. Theory, vol. 59, no. 11,
pp. 7576–7596, Nov. 2013.
[17] E. Tuncel, “Slepian-Wolf coding over broadcast channels,” IEEE Trans.
Inf. Theory, vol. 52, no. 4, pp. 1469–1482, Apr. 2006.
[18] Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, “Index coding with side
information,” IEEE Trans. Inf. Theory, vol. 57, no. 3, pp. 1479–1494,
Mar. 2011.
[19] N. Alon, E. Lubetzky, U. Stav, A. Weinstein, and A. Hassidim, “Broadcasting with side information,” in Proc. 49th IEEE Symp. Foundations
of Computer Science (FOCS), Oct. 2008, pp. 823–832.
[20] S. El Rouayheb, A. Sprintson, and C. Georghiades, “On the index coding
problem and its relation to network coding and matroid theory,” IEEE
Trans. Inf. Theory, vol. 56, no. 7, pp. 3187–3195, Jul. 2010.
[21] K. Shum, M. Dai, and C. W. Sung, “Broadcasting with coded side
information,” in Personal Indoor and Mobile Radio Communications
(PIMRC), 2012 IEEE 23rd International Symposium on, Sep. 2012, pp.
89–94.

[22] N. Lee, A. Dimakis, and R. Heath, “Index coding with coded sideinformation,” IEEE Commun. Lett., vol. 19, no. 3, pp. 319–322, Mar.
2015.
[23] Y. Birk and T. Kol, “Informed-source coding-on-demand (ISCOD) over
broadcast channels,” in Proc. 17th Annu. Joint Conf. IEEE Computer and
Communications Societies (INFOCOM), vol. 3, Mar. 1998, pp. 1257–
1264.
[24] S.-Y. Li, R. Yeung, and N. Cai, “Linear network coding,” IEEE Trans.
Inf. Theory, vol. 49, no. 2, pp. 371–381, Feb. 2003.
[25] R. Koetter and M. Medard, “An algebraic approach to network coding,”
IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 782–795, Oct. 2003.
[26] R. W. Yeung, Information Theory and Network Coding. New York:
Springer Science+Business Media, LLC, 2008.
[27] L.-L. Xie, “Network coding and random binning for multi-user channels,” in Proc. 10th Canadian Workshop on Information Theory (CWIT),
Jun. 2007, pp. 85–88.
[28] G. Kramer and S. Shamai, “Capacity for classes of broadcast channels
with receiver side information,” in Proc. IEEE Information Theory
Workshop (ITW), Sep. 2007, pp. 313–318.
[29] Y. Wu, “Broadcasting when receivers know some messages a priori,” in
Proc. IEEE Int. Symp. Information Theory (ISIT), Jun. 2007, pp. 1141–
1145.
[30] T. Oechtering, C. Schnurr, I. Bjelakovic, and H. Boche, “Broadcast
capacity region of two-phase bidirectional relaying,” IEEE Trans. Inf.
Theory, vol. 54, no. 1, pp. 454–458, Jan. 2008.
[31] F. Xue and S. Sandhu, “PHY-layer network coding for broadcast channel
with side information,” in Information Theory Workshop, 2007. ITW ’07.
IEEE, Sep. 2007, pp. 108–113.
[32] T. Wang, S. C. Liew, and L. Shi, “A lattice approach for optimal
rate-diverse wireless network coding,” arXiv preprint, 2015. [Online].
Available: http://arxiv.org/abs/1509.07250
[33] L. Xiao, T. Fuja, J. Kliewer, and D. Costello, “Nested codes with
multiple interpretations,” in Proc. 40th Annu. Conf. Information Sciences
and Systems (CISS), Mar. 2006, pp. 851–856.
[34] F. Barbosa and M. Costa, “A tree construction method of nested cyclic
codes,” in Proc. IEEE Information Theory Workshop (ITW), Oct. 2011,
pp. 302–305.
[35] Y. Ma, Z. Lin, H. Chen, and B. Vucetic, “Multiple interpretations for
multi-source multi-destination wireless relay network coded systems,”
in Proc. IEEE 23rd Int. Symp. Personal Indoor and Mobile Radio
Communications (PIMRC), Sep. 2012, pp. 2253–2258.
[36] L. Natarajan, Y. Hong, and E. Viterbo, “Lattice index coding,” IEEE
Trans. Inf. Theory, vol. 61, no. 12, pp. 6505–6525, Dec. 2015.
[37] Y.-C. Huang, “Lattice index codes from algebraic number fields,” in
Proc. IEEE Int. Symp. Information Theory (ISIT), Jun. 2015, pp. 2485–
2489.
[38] L. Natarajan, Y. Hong, and E. Viterbo, “Index codes for the Gaussian
broadcast channel using quadrature amplitude modulation,” IEEE Commun. Lett., vol. 19, no. 8, pp. 1291–1294, Aug. 2015.
[39] ——, “Capacity of coded index modulation,” in Proc. IEEE Int. Symp.
Information Theory (ISIT), Jun. 2015, pp. 596–600.
[40] H.-A. Loeliger, “Averaging bounds for lattices and linear codes,” IEEE
Trans. Inf. Theory, vol. 43, no. 6, pp. 1767–1773, Nov. 1997.
[41] D. Krithivasan and S. S. Pradhan, “A proof of the existence
of good nested lattices,” Jul. 2007. [Online]. Available: http:
//www.eecs.umich.edu/techreports/systems/cspl/cspl-384.pdf
[42] J. Forney, G.D., “Multidimensional constellations–Part II. Voronoi constellations,” IEEE J. Sel. Areas Commun., vol. 7, no. 6, pp. 941–958,
Aug. 1989.
[43] R. Zamir, Lattice Coding for Signals and Networks: A Structured Coding Approach to Quantization, Modulation, and Multiuser Information
Theory. Cambridge University Press, 2014.
[44] C. A. Rogers, “Lattice coverings of space,” Mathematika, vol. 6, pp.
33–39, 1959.
[45] U. Erez, S. Litsyn, and R. Zamir, “Lattices which are good for (almost)
everything,” IEEE Trans. Inf. Theory, vol. 51, no. 10, pp. 3401–3416,
Oct. 2005.
[46] J. Forney, G.D., “On the role of MMSE estimation in approaching the
information-theoretic limits of linear Gaussian channels: Shannon meets
Wiener,” in Proc. 2003 Allerton Conf., Oct. 2003.
[47] G. Poltyrev, “On coding without restrictions for the AWGN channel,”
IEEE Trans. Inf. Theory, vol. 40, no. 2, pp. 409–417, Mar. 1994.
[48] B. Asadi, L. Ong, and S. Johnson, “The capacity of three-receiver
AWGN broadcast channels with receiver message side information,” in
Proc. IEEE Int. Symp. Information Theory (ISIT), Jun. 2014, pp. 2899–
2903.

16

[49] J. Sima and W. Chen, “Joint network and Gelfand-Pinsker coding
for 3-receiver Gaussian broadcast channels with receiver message side
information,” in Proc. IEEE Int. Symp. Information Theory (ISIT), Jun.
2014, pp. 81–85.
[50] T. M. Cover and J. A. Thomas, Elements of Information Theory. John
Wiley & Sons, 1991.

Yi Hong (S’00–M’05–SM’10) is currently a Senior Lecturer at the Department of Electrical and Computer Systems Eng., Monash University,
Melbourne, Australia. She obtained her Ph.D. degree in Electrical Engineering
and Telecommunications from the University of New South Wales (UNSW),
Sydney, and received the NICTA-ACoRN Earlier Career Researcher Award at
the Australian Communication Theory Workshop, Adelaide, Australia, 2007.
Dr. Hong was an Associate Editor for the IEEE W IRELESS C OMMUNI CATIONS L ETTERS and the Transactions on Emerging Telecommunications
Technologies (ETT). She was the General Co-Chair of the IEEE Information
Theory Workshop 2014, Hobart; the Technical Program Committee Chair
of the Australian Communications Theory Workshop 2011, Melbourne; and
the Publicity Chair at the IEEE Information Theory Workshop 2009, Sicily.
She was a Technical Program Committee member for several leading IEEE
conferences. Her research interests include communication theory, coding and
information theory with applications to telecommunication engineering.

Lakshmi Natarajan is an Assistant Professor in the Department of Electrical
Engineering, Indian Institute of Technology Hyderabad. He received the
B.E. degree from the College of Engineering, Guindy, in electronics and
communication in 2008, and the Ph.D. degree from the Indian Institute of
Science, Bangalore, in 2013. Between 2014 and 2016 he held a post-doctoral
position at the Department of Electrical and Computer Systems Engineering,
Monash University, Australia. His primary research interests are coding and
information theory for communication systems.
Dr. Natarajan is an Editor of the IEEE W IRELESS C OMMUNICATIONS
L ETTERS. He was the recipient of the Seshagiri-Kaikini Medal 2013-14
for best Ph.D. thesis, Department of Electrical Communication Engineering,
Indian Institute of Science, Bangalore. He was recognized as an Exemplary
Reviewer by the editorial board of the IEEE W IRELESS C OMMUNICATIONS
L ETTERS in 2013, 2015 and 2016. He served as the Local Arrangements CoChair of the 2016 Australian Communications Theory Workshop, Melbourne
and the 2016 Australian Information Theory School, Melbourne.

Emanuele Viterbo (M’95–SM’04–F’11) is currently a Professor in the
ECSE Department and an Associate Dean in Graduate Research at Monash
University, Melbourne, Australia. He received his Ph.D. in 1995 in Electrical
Engineering, from the Politecnico di Torino, Torino, Italy. From 1990 to 1992
he was with the European Patent Office, The Hague, The Netherlands, as a
patent examiner in the field of dynamic recording and error-control coding.
Between 1995 and 1997 he held a post-doctoral position in the Dipartimento
di Elettronica of the Politecnico di Torino. In 1997-98 he was a postdoctoral research fellow in the Information Sciences Research Center of AT&T
Research, Florham Park, NJ, USA. From 1998-2005, he worked as Assistant
Professor and then Associate Professor, in Dipartimento di Elettronica at
Politecnico di Torino. From 2006-2009, he worked in DEIS at University
of Calabria, Italy, as a Full Professor.
Prof. Viterbo is an ISI Highly Cited Researcher since 2009. He was an
Associate Editor of the IEEE T RANSACTIONS ON I NFORMATION T HEORY,
the European Transactions on Telecommunications and the Journal of Communications and Networks, and Guest Editor for the IEEE J OURNAL OF S E LECTED T OPICS IN S IGNAL P ROCESSING : S PECIAL I SSUE ON M ANAGING
C OMPLEXITY IN M ULTIUSER MIMO S YSTEMS. Prof. Viterbo was awarded
a NATO Advanced Fellowship in 1997 from the Italian National Research
Council. His main research interests are in lattice codes for the Gaussian and
fading channels, algebraic coding theory, algebraic space-time coding, digital
terrestrial television broadcasting, digital magnetic recording, and irregular
sampling.

