1

Capacity Results for Finite-Field X-Channels
with Delayed CSIT
Alireza Vahid
Department of Electrical Engineering
University of Colorado Denver

arXiv:1801.03066v1 [cs.IT] 9 Jan 2018

alireza.vahid@ucdenver.edu

Abstract
We establish the capacity region of the two-user Finite-Field Fading X-Channel with delayed channel state
information at the transmitters. We consider the most general case in which each transmitter has a common message
for both receivers and a private message for each one of them. We derive a new set of outer-bounds for this problem
that rely on an extremal entropy inequality. This inequality quantifies the ability of each transmitter in favoring one
receiver over the other in terms of the delivered entropy when both receivers must obtain a baseline entropy. We
show that the outer-bounds can be achieved by treating the X-Channel as a combination of a number of well-known
problems such as the interference channel and the multicast channel. The capacity-achieving strategies of these subproblems must be interleaved and carried on simultaneously in certain regimes in order to achieve the X-Channel
outer-bounds.
Index Terms
X-Channel, finite-field model, channel capacity region, interference channel, delayed CSIT.

I. I NTRODUCTION
Alongside the two-user interference channel [1]–[4], the two-user X-Channel is a canonical example to study
the impact of interference in communication networks. In the X-Channel, each transmitter has a common message
intended for both receivers as well as a private message intended for each receiver. This problem has been studied
extensively in the literature and several interference management techniques have been proposed [5]–[7]. For instance
under instantaneous channel state information (CSI) model, it was shown in [6] that interference alignment can
provide a gain over baseline techniques (e.g., orthogonalization). This gain is expressed in terms of degrees-offreedom (DoF) which captures the asymptotic behavior of the network normalized by the capacity of the point-topoint channel when power tends to infinity.
Attaining instantaneous channel state information at the transmitters (CSIT) in many real-world scenarios may
not be feasible. In such cases, a more realistic model is the delayed CSIT in which by the time the CSI arrives

2

at the transmitters, the channel has already changed to a new state. Under the delayed CSIT model, authors in [8]
developed a scheme that achieves 6/5 DoF. Later, it was shown that if we limit ourselves to linear encoding
functions, then 6/5 is indeed the optimal DoF [9]. These results provide valuable insight into the behavior of
X-Channels. However, in information and communication theory, the ultimate goal is to understand the behavior of
wireless networks for any signal-to-noise ratio (SNR). In other words, we are interested in capacity results rather
than DoF-type results. Moreover, while one might argue that most practical communication protocols are linear,
limiting the encoding functions to be linear removes the majority of potential encoding functions and from an
information-theoretic perspective, this is not desirable. Finally, authors in [8] and [9] study a subset of X-Channels
in which transmitters only have private messages for the receivers and the issue of common messages in X-Channels
is not addressed, and as we will show, including common messages introduces new challenges.
In this work, we address these issues by deriving the capacity region of X-Channels with delayed CSIT and
common messages under a finite-field fading model introduced in [10]. In this model, the channel gains at each
time are drawn from the binary field according to some Bernoulli distribution. The input-output relation of this
channel model at time t is given by
Yi [t] = Gii [t]Xi [t] ⊕ Giī [t]Xī [t],

i = 1, 2,

(1)

where ī = 3 − i, the channel gains Gii [t], Giī [t] are in the binary field, Xi [t] ∈ {0, 1} is the transmit signal of
transmitter i at time t, and Yi [t] ∈ {0, 1} is the observation of receiver i at time t. All algebraic operations are in
F2 . In the delayed CSIT model, we assume that the transmitters at time t have access to
4

Gt−1 = (G11 [`], G12 [`], G21 [`], G22 [`])t−1
`=1 .

(2)

The X-Channel poses several new challenges when compared to the interference channel. In the interference
channel, each transmitter has a private message for its corresponding receiver and to maximize the overall achievable
rate, each transmitter tries to minimize the interference subspace at the unintended receiver. In the context of
X-Channels, however, each transmitter has a private message for each one of the receivers which changes the
interference dynamics of the problem since receivers are now interested in signals of both transmitters. On top of
this, each transmitter has to deliver a common message to the receivers. In this work, we establish the capacity
region of finite-field fading X-Channels under the delayed CSIT assumption. We derive a new set of outer-bounds
for this problem. We also propose a distributed transmission strategy that harvests the delayed CSI to combine and
to repackage previously communicated signals in order to deliver them efficiently. We show that this transmission
strategy matches the outer-bounds, thus, characterizing the capacity region.
To derive the outer-bounds, we rely on an extremal entropy inequality to capture both the impact of delayed
CSIT and the challenge of delivering the common messages. This inequality quantifies the ability of a transmitter
to favor one receiver over the other in terms of provided entropy when: (1) both receivers need to obtain some

3

common entropy, and (2) the transmitter has access to the delayed channel state information. In particular, this
extremal inequality quantifies β such that the following inequality holds for any input distribution:
H (Y1n |W0 , W2 , Gn ) − β {H (Y2n |W2 , Gn ) − I (W0 ; Y2n |W2 , Gn )} ≤ 0.

(3)

where W0 indicates the common message, and Wi is the private message for Rxi . Using (3) and a genie-aided
argument, we obtain the outer-bounds.
To achieve the outer-bounds, we treat the X-Channel as a combination of a number of well-known problems for
which the capacity region is known. By adjusting different rates for the X-Channel, we can recover several other
problems such as the interference channel, the multicast channel, the broadcast channel, and the multiple-access
channel. We demonstrate how to utilize the capacity-achieving strategies of such problems in a systematic way in
order to achieve the capacity region of the X-Channel. We show that, however, if we treat the X-Channel as a
number of disjoint sub-problems, we will not achieve the capacity and in some regimes, we need to interleave the
capacity-achieving strategies of different sub-problems and execute them simultaneously.
The rest of the paper is organized as follows. In Section II we formulate the problem. In Section III we present
our main results and provide some insights. Sections IV and V are dedicated to the proof of the main results.
Section VI concludes the paper.
II. P ROBLEM F ORMULATION
Gt-1

W01,W11,W21

f1(.)

X1[t]

Tx1

[t]
G 21

W02,W12,W22

f2(.)

X2[t]

Tx2

Rx1

G11[t]

Y1[t]

G

G22[t]

12 [
t

]

Rx2

Y2[t]

Gt-1

Fig. 1. Two-user Binary Fading X-Channel. All signals and the channel gains are in the binary field.

We consider the two-user Binary Fading X-Channel as illustrated in Fig. 1 with two transmitters and two
receivers1 . In the binary fading model, the channel gain from transmitter Txj to receiver Rxi at time t is denoted by
Gij [t], i, j ∈ {1, 2}. The channel gains are either 0 or 1 (i.e. Gij [t] ∈ {0, 1}), and they are distributed as independent

Bernoulli random variables (independent across time and space). We consider the homogeneous setting in which
d

Gij [t] ∼ B(p),
1

i, j = 1, 2,

(4)

In this work, we focus on the binary field. Extending the results from the binary field to larger Galois fields is possible and rather

straightforward.

4
4

for 0 ≤ p ≤ 1, and we define q = 1 − p.
At each time t, the transmit signal of Txj is denoted by Xj [t] ∈ {0, 1}, and the received signal at Rxi is given
by
Yi [t] = Gii [t]Xi [t] ⊕ Giī [t]Xī [t],

i = 1, 2,

(5)

where the summation is in F2 , and ī = 3 − i.
We define the channel state information (CSI) at time t to be the quadruple
4

G[t] = (G11 [t], G12 [t], G21 [t], G22 [t]) ,

(6)

and for natural number k , we set
4

Gk = (G[1], G[2], . . . , G[k])> ,

(7)

where G[t] is defined in (6). Finally, we set
4

Gtii Xit ⊕ Gtiī Xīt = [Gii [1]Xi [1] ⊕ Giī [1]Xī [1], . . . , Gii [t]Xi [t] ⊕ Giī [t]Xī [t]]> .

(8)

In this work, we consider the delayed CSIT model in which at time t each transmitter has the knowledge
of the channel state information up to the previous time instant (i.e. Gt−1 ) and the distribution from which the
channel gains are drawn (i.e. B(p)), t = 1, 2, . . . , n. Since receivers only decode the messages at the end of the
communication block, without loss of generality, we assume that the receivers have instantaneous knowledge of
the CSI.
For the X-Channel, we consider the scenario in which Txj , j = 1, 2, wishes to reliably communicate
1) message W0j ∈ {1, 2, . . . , 2nR0j } to both receivers,
2) message W1j ∈ {1, 2, . . . , 2nR1j } to Rx1 ,
3) and message W2j ∈ {1, 2, . . . , 2nR2j } to Rx2 ,
during n uses of the channel. We assume that the messages and the channel gains are mutually independent and
the messages are chosen uniformly at random.
For transmitter Txj , let messages W0j , W1j , and W2j be encoded as Xjn using the encoding function fj (.), which
depends on the available CSI at Txj , see Fig. 1. Receiver Rxi is interested in decoding W0 and Wi given by
4

W0 = (W01 , W02 ) ,
4

Wi = (Wi1 , Wi2 ) ,

and it will decode the messages using the decoding function gi (.):

4
c0 , W
ci =
W
gi (Yin , Gn ).

(9)

(10)

An error occurs when



c0 , W
ci =
W
6 (W0 , Wi ) .

(11)

5

The average probability of decoding error is given by


4
c0 , W
ci 6= (W0 , Wi )]],
λi,n = E[P [ W

i = 1, 2,

(12)

where the expectation is taken with respect to the random choice of messages.
We define
4

R0 = R01 + R02 ,
4

R1 = R11 + R12 ,
4

R2 = R21 + R22 .

(13)

A rate tuple (R0 , R1 , R2 ) is said to be achievable, if there exists encoding and decoding functions at the
transmitters and the receivers respectively, such that the decoding error probabilities λ1,n , λ2,n go to zero as n
goes to infinity. The capacity region is the closure of all achievable rate tuples.
III. M AIN R ESULTS
In this section, we present the capacity region of the two-user Binary Fading X-Channel under the delayed CSIT
assumption, and we provide some technical insights and interpretations of the main results.

A. Statement of the Main Results
The following theorem establishes the capacity region of the two-user Binary Fading X-Channel with private and
common messages under the delayed CSIT assumption.
Theorem 1. The capacity region, C , of the two-user Binary Fading X-Channel with private and common messages
under delayed CSIT assumption as described in Section II is the set of all non-negative rates satisfying:

 BC Bounds : 0 ≤ R + β R + R  ≤ βp,
ij
0j
īj
 XC Bounds : R + β (R + R ) ≤ β 1 − q 2  ,
i
0
ī

(14)

for i, j ∈ {1, 2}, R0 , R1 , R2 defined in (13), and
β = 2 − p.

(15)

The capacity region is described by two sets of outer-bounds. The first set is referred to as the Broadcast
Channel (BC) bounds. These bounds describe the capacity region of the broadcast channel formed by one of the
transmitters and the two receivers assuming the other transmitter is eliminated. These bounds can be thought of as
the generalization of the results in [11]–[13] for the two-user case to include common messages. The second set is
referred to as the X-Channel (XC) bounds. We note that adding the two BC bounds results in
Ri + β (Rī + R0 ) ≤ 2βp,

(16)

6

which is dominated by the XC bounds since for any 0 ≤ p ≤ 1, we have
1 − q 2 = 2p − p2 ≤ 2p.

(17)

The derivation of the outer-bounds relies on an extremal entropy inequality that quantifies the ability of each
transmitter in favoring one receiver over the other in terms of the available entropy subject to two constraints:
(1) both receivers need to obtain a baseline entropy (to capture the common messages), and (2) transmitters have

access to the delayed CSI. This inequality characterizes the limit to which the unwanted subspace at one receiver
can be scaled down while the desired subspace at the other receiver is maximized. We use this inequality and a
genie-aided argument to derive the new outer-bounds.
The two-user X-Channel can be thought of as a generalization and a combination of several well-known problems.
For instance, if R11 and R12 are the only non-zero rates, then the problem is equivalent to the multiple-access channel
formed at Rx1 , and if R12 and R22 are the only non-zero rates, then the problem is equivalent to the broadcast
channel formed by Tx2 . We demonstrate how to utilize the capacity-achieving strategies of other problems, such as
the interference channel and the multicast channel, in a systematic way in order to achieve the capacity region of
the X-Channel. We show that, however, if we treat the X-Channel as a number of disjoint sub-problems, we will
not achieve the capacity in some regimes. In fact, in such regimes, we need to interleave the capacity-achieving
strategies of different sub-problems and execute them simultaneously.

B. Illustration of the Main Results
To illustrate the results of Theorem 1, we focus on the symmetric case for p = 0.5, i.e.
R01 = R02 ,
R1 = R2 .

(18)

Fig. 2 depicts the two-dimensional region of (R1 , R2 ) for R0 ∈ {0, 1/4, 1/2, 3/4}. In this figure for a given R0 ,
we define
CSUM (R0 ) = R0 + sup (R1 + R2 ) .

(19)

R1 =R2

An interesting observation is that the sum of R01 and R02 (i.e. R0 ) determines the size of the region rather than
the individual values. For instance, Fig. 2(c) is the same for (R01 , R02 ) = (1/4, 1/4), (R01 , R02 ) = (0, 1/2), and
(R01 , R02 ) = (1/2, 0). Moreover, as R0 increases, the symmetric capacity, CSUM (R0 ), decreases. The reason is

that providing more common entropy to the receivers reduces the ability of each transmitter in favoring one over
the other in terms of available entropy. In other words, providing more common entropy to the receivers reduces
transmitters’ ability in performing interference alignment.

7

3/4

½

½

(0.45,0.45)

(0.3,0.3)

½

½

3/4

(a)

(b)

1/4
(0.15,0.15)

1/4

(c)

(d)

Fig. 2. The two-dimensional region of (R1 , R2 ) for R0 ∈ {0, 1/4, 1/2, 3/4}. As R0 increases, the symmetric capacity, CSUM , decreases.

3/4

½

(0.5,0.375)
(0.45,0.45)
point-to-point
capacity
MAC
capacity

½

3/4

Fig. 3. The capacity region of the two-user Binary Fading Interference Channel with delayed CSIT (shaded region in the figure) is included
in the capacity region of the two-user Binary Fading X-Channel with delayed CSIT and R0 = 0.

C. Comparison to the Interference Channel
For the two-user Binary Fading Interference Channel [10], there is no common message (i.e. R0 = 0), and
each transmitter only has a message for one receiver (i.e. R12 = R21 = 0). Fig. 3 depicts the capacity region
of the X-Channel for R0 = 0 which includes the capacity region of the interference channel. We note that in
the X-Channel, individual rates are limited by the capacity of the multiple-access channel (MAC) formed at each

8


receiver (i.e. 1 − q 2 ), whereas in the interference channel the limit is the capacity of the point-to-point channel
(i.e. p). Moreover, for some values of p, the symmetric capacity of the X-Channel is strictly larger than that of the
interference channel. This issue is further discussed in Section V-C and Fig. 8.

D. The Broadcast Channel Bounds
So far, we focused on R1 and R2 and as a result, the BC bounds did not play a role. As mentioned earlier, the
BC bounds describe the capacity region of the broadcast channel formed by one of the transmitters and the two
receivers assuming the other transmitter is eliminated. Suppose we set R02 , R12 , and R22 equal to 0 (i.e. eliminating
the second transmitter), and we focus on R01 , R11 , and R21 . These rates correspond to Tx1 and are governed by
the BC bounds as depicted in Fig. 4.

½
(0.3,0.3)

1/4

(0.15,0.15)

1/4

½

Fig. 4. The BC bounds govern the behavior of the rates associated with each transmitter (Tx1 in this figure).

IV. C ONVERSE P ROOF OF T HEOREM 1
In this section, we provide the converse proof of Theorem 1. The proof of the BC bounds has some similarities
to that of the XC bounds and when possible we omit the duplications in the proofs.
BC Bounds: We first derive the Broadcast Channel bounds, i.e.

Rij + β Rīj + R0j ≤ βp.

(20)

By symmetry, it suffices to prove (20) for i = j = 1. As mentioned before, this bound corresponds to the Broadcast
Channel formed by Tx1 when Tx2 is eliminated. In our proof, this fact is captured by conditioning on W02 , W12 ,

9

and W22 . We have
n (R11 + β (R21 + R01 )) = H (W11 ) + β (H (W21 ) + H (W01 ))
(a)

= H (W11 |W01 , W02 , W21 , W12 , W22 ) + β (H (W21 |W02 , W12 , W22 ) + H (W01 |W02 , W12 , W22 ))

(b)

≤ I (W11 ; Y1n , Gn |W01 , W02 , W21 , W12 , W22 )

+ β (I (W21 ; Y2n , Gn |W02 , W12 , W22 ) + I (W01 ; Y2n , Gn |W02 , W12 , W22 )) + nn
(c)

= I (W11 ; Y1n |W01 , W02 , W21 , W12 , W22 , Gn )

+ β (I (W21 ; Y2n |W02 , W12 , W22 , Gn ) + I (W01 ; Y2n |W02 , W12 , W22 , Gn )) + nn
= H (Y1n |W01 , W02 , W21 , W12 , W22 , Gn ) − H (Y1n |W0 , W1 , W2 , Gn ) +βH (Y2n |W02 , W12 , W22 , Gn )
|
{z
}
= 0

− β (H

(Y2n |W02 , W12 , W21 , W22 , Gn )

−I

(W01 ; Y2n |W02 , W12 , W22 , Gn ))

+ nn

(d)

≤ βH (Y2n |W02 , W12 , W22 , Gn ) + nn

(e)

= βH (Y2n |X2n , W02 , W12 , W22 , Gn ) + nn
(f )

= βH (Gn11 X1n |X2n , W02 , W12 , W22 , Gn ) + nn ≤ nβp + nn .

(21)

where n → 0 as n → ∞; (a) follows from the independence of messages; (b) follows from Fano’s inequality;
(c) holds since messages are independent of channel realizations; (d) follows from Claim 1 below; (e) follows the

fact that X2n is a function of (W02 , W12 , W22 , Gn ); (f ) holds since G11 [t]X1 [t] ∈ {0, 1}. Dividing both sides by n
and letting n → ∞, we get
R11 + β (R21 + R01 ) ≤ βp.

(22)

R22 + β (R12 + R02 ) ≤ βp.

(23)

Similarly, we can obtain

Claim 1. For the two-user Binary Fading X-Channel with private and common messages under delayed CSIT
assumption as described in Section II, we have
H (Y1n |W01 , W02 , W21 , W12 , W22 , Gn )
− β {H (Y2n |W02 , W12 , W21 , W22 , Gn ) − I (W01 ; Y2n |W02 , W12 , W22 , Gn )} ≤ 0.

(24)

The proof of Claim 1 follows step by step that of Claim 2 that we will present and prove below and thus omitted.

10

XC Bounds: As mentioned before, the XC bounds cannot be obtained from the BC bounds. However, the derivation
resembles the one we provided for the BC bounds with some modifications. To derive the XC bounds, we have
n (R1 + β (R2 + R0 )) = H (W1 ) + β (H (W2 ) + H (W0 ))
(a)

= H (W1 |W0 , W2 ) + β (H (W2 ) + H (W0 |W2 ))

(b)

≤ I (W1 ; Y1n , Gn |W0 , W2 ) + β (I (W2 ; Y2n , Gn ) + I (W0 ; Y2n , Gn |W2 )) + nn

(c)

= I (W1 ; Y1n |W0 , W2 , Gn ) + β (I (W2 ; Y2n |Gn ) + I (W0 ; Y2n |W2 , Gn )) + nn

= H (Y1n |W0 , W2 , Gn ) − H (Y1n |W0 , W1 , W2 , Gn ) +βH (Y2n |Gn )
|
{z
}
= 0

− β (H (Y2n |W2 , Gn ) − I (W0 ; Y2n |W2 , Gn )) + nn
(d)

(e)

≤ βH (Y2n |Gn ) + nn ≤ nβ(1 − q 2 ) + nn .

(25)

where n → 0 as n → ∞; (a) follows from the independence of messages; (b) follows from Fano’s inequality; (c)
holds since messages are independent of channel realizations; (d) follows from Claim 2 below; (e) holds since
H (Y2n |Gn ) ≤

n
X

H (Y2 [t]|Gn ) ≤ n(1 − q 2 ).

(26)

t=1

Dividing both sides by n and letting n → ∞, we get
R1 + β (R2 + R0 ) ≤ β(1 − q 2 ).

(27)

R2 + β (R1 + R0 ) ≤ β(1 − q 2 ).

(28)

Similarly, we can obtain

Claim 2. For the two-user Binary Fading X-Channel with private and common messages under delayed CSIT
assumption as described in Section II, we have
H (Y1n |W0 , W2 , Gn ) − β {H (Y2n |W2 , Gn ) − I (W0 ; Y2n |W2 , Gn )} ≤ 0.

(29)

Proof. We first note that
H (Y2n |W0 , W2 , Gn ) = H (Y2n |W2 , Gn ) − I (W0 ; Y2n |W2 , Gn ) .

(30)

Thus, proving (29) is equivalent to proving
H (Y1n |W0 , W2 , Gn ) − βH (Y2n |W0 , W2 , Gn ) ≤ 0.

(31)

11

We have
H (Y2n |W0 , W2 , Gn )
=

n
X

(a)

=

H Y2 [t]|Y2t−1 , W0 , W2 , Gn

t=1
n
X



H Y2 [t]|Y2t−1 , W0 , W2 , Gt



t=1
n

(b) X
pH X1 [t]|Y2t−1 , W0 , W2 , G2 [t] = 1, G1 [t], Gt−1
=
t=1
(c)

=

n
X

t=1
n
(d) X

≥

pH X1 [t]|Y2t−1 , W0 , W2 , Gt



pH X1 [t]|Y1t−1 , Y2t−1 , W0 , W2 , Gt



t=1
n
(e) X
=

(f )

=

t=1
n
X
t=1


p
H Y1 [t], Y2 [t]|Y1t−1 , Y2t−1 , W0 , W2 , Gt
2
1−q

1
H Y1 [t], Y2 [t]|Y1t−1 , Y2t−1 , W0 , W2 , Gt
β

n

(g) X 1
H Y1 [t], Y2 [t]|Y1t−1 , Y2t−1 , W0 , W2 , Gn
=
β
t=1

1
= H (Y1n , Y2n |W0 , W2 , Gn )
β
(h) 1
≥ H (Y1n |W0 , W2 , Gn ) ,
β

(32)

where (a) follows from the fact that all signals at time t are independent of future channel realizations; (b) holds
since Pr (G2 [t] = 1) = p; (c) is true since transmit signal X1 [t] is independent of the channel realization at time t;
(d) holds since conditioning reduces entropy; (e) holds since Pr (G1 [t] = G2 [t] = 0) = 1 − q 2 ; (f ) follows from

the definition of β ; (g) is true since all signals at time t are independent of future channel realizations; (h) follows
from the chain rule and the non-negativity of the entropy function for discrete random variables.
This completes the converse proof of Theorem 1, and in the following section we present the achievability proof.
V. ACHIEVABILITY P ROOF OF T HEOREM 1
X-Channels can be thought of as a generalization of several known problems such as interference channels,
broadcast channels, multiple-access channels, and multicast channels. In the previous section, we developed a
set of new outer-bounds for this problem. In this section, we show that a careful combination of the capacityachieving strategies for other known known problems will achieve the capacity region of the X-Channel. However,
in Section V-C we show that if we treat the X-Channel as a number of disjoint sub-problems, we will not achieve
the capacity and in some regimes, we need to interleave the capacity-achieving strategies of different sub-problems
and execute them simultaneously.

12

To describe the transmission strategy, we first present two examples. The first example describes a symmetric
scenario associated with Fig. 2(b) and the second example describes a scenario in which transmitters achieve unequal
rates. After the examples, we present the general scheme.

W1

Tx1

12 [

t]

G22[t]

Tx2

^2
^ 1,W
W

G

[t]
G 21

W2

Rx1

G11[t]

Rx2

^2
^ 1,W
W

½
¼
¼

½

(a)

W1

Tx1

[t]
G 21

W2

Tx2

Rx1

G11[t]

^1
W

½

G

12 [

¼

t]

G22[t]

Rx2

(0.45,0.45)

^2
W

¼

½

(b)

W1

Tx1

[t]
G 21

W2

Tx2

Rx1

G11[t]

^2
W

½

G

G22[t]

12 [

¼

t]

Rx2

(0.45,0.45)

^1
W

¼

½

(c)
Fig. 5. (a) The two-user multicast channel and its capacity region, the capacity can be achieved without using the delayed CSI; (b) The
two-user binary fading interference channel and its capacity region; (c) The two-user binary fading interference channel with swapped IDs
and its capacity region.

13

A. Example 1: Symmetric Sum-Rate of Fig. 2(b)
Suppose for p = 0.5, we wish to achieve the sum-capacity of CSUM (1/4) = 0.85 with
R01 = R02 = 1/8,
R11 = R12 = R21 = R22 = 0.15,

(33)

as shown in Fig. 2(b).
For this particular example, we treat the X-Channel as three separate problems listed below at different times,
and we show that this strategy achieves the capacity.
•

For the first third of the communication block, we treat the X-Channel as a two-user multicast channel as
depicted in Fig. 5(a) in which each transmitter has a message for both receivers. For the two-user multicast
channel with fading parameter 1/2, the capacity region matches that of the multiple-access channel formed at
each receiver [10] and depicted in Fig. 5(a) as well.

•

For the second third of the communication block, we treat the X-Channel as a two-user interference channel
in which Txj wishes to communicated with Rxj , see Fig. 5(b). The capacity region of this problem is given
in [10] and depicted in Fig. 5(b).

•

During the final third of the communication block, we treat the X-Channel as a two-user interference channel
with swapped IDs in which Txj wishes to communicated with Rxj̄ , see Fig. 5(c). In the homogeneous setting
of this work, the capacity region of this interference channel with swapped IDs matches that of the previous
case and is depicted in Fig. 5(c).

Achievable Rates: We note that as the communication block length, n, goes to infinity, so do the communication
block lengths for each sub-problem. Thus, during the first third of the communication block, we can achieve
symmetric common rates arbitrary close to (3/8, 3/8). Normalizing to the total communication block, we achieve
(R01 , R02 ) = (1/8, 1/8) which matches the requirements of (33). From [10] we know that for the two-user binary

fading interference channel with delayed CSIT and p = 1/2, we can achieve symmetric rates of (0.45, 0.45). Normalizing to the total communication block, we achieve (R11 , R22 ) = (0.15, 0.15) which matches the requirements
of (33). Finally, during the final third of the communication block we treat the problem as a two-user interference
channel with swapped IDs in which we can achieve symmetric rates of (0.45, 0.45). Normalizing to the total
communication block, we achieve (R21 , R12 ) = (0.15, 0.15) which again matches the requirements of (33). Thus,
with splitting up the X-Channel into a combination of three known sub-problems, we can achieve the capacity
region described in Theorem 1.

B. Example 2: Unequal Rates
In the previous subsection we focused on a symmetric setting. Here, we discuss a scenario in which transmitters
have different types of messages with different rates for each receiver. More precisely, we consider the region in

14

Tx1
W0

]
G 11[t
G21 [t

Rx1

^0
W

]

Rx2

^0
W

(a)

Tx2
W1,W2

]
G 12[t
G22 [t

Rx1

^1
W

½
(0.3,0.3)

0.3

]

Rx2

^2
W
0.3

½

(b)
Fig. 6. (a) The two-user broadcast channel with a single common message; (b) The two-user broadcast channel with delayed CSIT and
private messages, and its capacity region.

Fig. 2(c) for p = 0.5, and
R01 = 1/2,
R02 = 0,
R11 = R21 = 0,
R12 = R22 = 0.15,

(34)

In this case, we can think of the X-Channel in this case as two sub-problems that coexist at the same time as
described below.
•

The Binary Fading Broadcast Channel from Tx1 as in Fig. 6(a) in which a single message is intended for both
receivers. For this problem, the capacity can be achieved using a point-to-point erasure code of rate 1/2.

•

The Binary Fading Broadcast Channel from Tx2 as in Fig. 6(b) with delayed CSIT in which the transmitter has
a private message for each receiver. For this problem, the capacity region is given in [11], [12] and depicted
Fig. 6(b). As described below, in order to be able to decode the messages in the presence of the broadcast
channel from Tx1 , we first encode W12 and W22 using point-to-point erasure codes of rate 1/2, and treat the
resulting codes as the input messages to the broadcast channel of Fig. 6(b).

Achievable Rates: At each receiver the received signal from Tx2 is corrupted (erased) half of times by the signal

15

from Tx1 . As a result, when we implement the capacity-achieving strategy of [11], [12], we only deliver half of
the bits intended for each receiver. However, since we first encode W12 and W22 using point-to-point erasure codes
of rate 1/2, obtaining half of the bits is sufficient for reliable decoding of W12 and W22 . Thus, we achieve
(R12 , R22 ) =

1
(0.3, 0.3) = (0.15, 0.15) ,
2

(35)

which again matches the requirements of (34). At the end of the communication block, receivers decode W12 and
W22 , and remove the contribution of Tx2 from their received signals. After removing the contribution of X2n , the

problem is identical to the broadcast channel from Tx1 as in Fig. 6(a) for which we can achieve a common rate
R02 of 1/2.

C. Transmission Strategy
The two examples we have provided so far demonstrate the key ideas behind the transmission strategy and
dividing the problem into a number of known sub-problems. Suppose we would like to achieve
0 ≤ R0 ≤ (1 − q 2 ),


β (1 − q 2 ) − R0
R1 = R2 =
.
1+β

(36)

An important difference between the X-Channel and the interference channel is the fact that in the latter scenario,
the individual rates are limited by the capacity of a point-to-point channel, i,e, p. As a result, for the interference
channel we have [10]:
(

2β 1 − q 2
sup (R1 + R2 ) = min 2p,
1+β

)
.

However, in the X-Channel no such limitation exists, and we have


2β 1 − q 2 − R0
sup (R1 + R2 ) =
.
1+β

(37)

(38)

The difference is depicted in Fig. 8 for R0 = 0. This means that if we naively try to use the capacity-achieving
strategies of the sub-problems independently, we cannot achieve the capacity region of the X-Channel. The key
idea to over come this challenge is to take an approach similar to the one we presented in Section V-B and run
different strategies simultaneously as described below.
The strategy that achieves the rates in (36) is similar to what we presented in Section V-A. Define
γ=

R0
.
1 − q2

(39)

First suppose

2β 1 − q 2
≤ 2p.
1+β
Then the transmission strategy is as follows.

(40)

16

W1

Tx1

G

W2

Rx1

G11[t]

R1+R2=(1-q2)

p

G

[t]
21

12 [

t]

G22[t]

Tx2

^2
^ 1,W
W

Rx2

^2
^ 1,W
W
p

(a)

W1

Tx1

G

W2

Rx1

G11[t]
[t]
21

p

G

12 [

t]

G22[t]

Tx2

^1
W

Rx2

^2
W
p

(b)

W1

Tx1

G

W2

Tx2

Rx1

G11[t]
[t]
21

^2
W

p

G

G22[t]

12 [

t]

Rx2

^1
W
p

(c)
Fig. 7. (a) The two-user multicast channel and its capacity region, the capacity can be achieved without using the delayed CSI; (b) The
two-user binary fading interference channel and its capacity region; (c) The two-user binary fading interference channel with swapped IDs
and its capacity region.

•

For the first γ fraction of the communication block, we treat the X-Channel as a two-user multicast channel
as depicted in Fig. 7(a) in which each transmitter has a message for both receivers. For the two-user multicast
channel with fading parameter p, the capacity region matches that of the multiple-access channel formed at
each receiver [10] and depicted in Fig. 7(a) as well.

•

During a fraction (1 − γ)/2 of the communication block, we treat the X-Channel as a two-user interference

Sum-Capacity

17

Sum-Capacity of X-Ch. with no Common Message
Sum-Capacity of the Interference Channel

1
X-Ch. outperforms IC
0.8
0.6
0.4
0.2
0
0

0.1

0.2

0.3 (3-√5)/2

0.5

0.6

0.7

0.8

0.9

1

p

Fig. 8. The sum-capacity of the X-Channel vs. that of the Interference Channel. To have a fair comparison, in the X-Channel we set R0 = 0.

channel in which Txj wishes to communicated with Rxj , see Fig. 7(b). An instance of the capacity region of
this problem is given in [10] and depicted in Fig. 7(b).
•

During a fraction (1 − γ)/2 of the communication block, we treat the X-Channel as a two-user interference
channel with swapped IDs in which Txj wishes to communicated with Rxj̄ , see Fig. 7(c). In the homogeneous
setting of this work, the capacity region of this interference channel with swapped IDs matches that of the
previous case and an instance of it is depicted in Fig. 7(c).


Achievable Rates: With this strategy γ fraction of the times, we achieve a common rate, R0 , of 1 − q 2 , while
(1 − γ) fraction of the times, we achieve individual rates

!
β 1 − q2 β 1 − q2
,
.
1+β
1+β

The overall achievable rate matches CSUM (R0 ) in this case. Now, consider the case in which

2β 1 − q 2
> 2p.
1+β

(41)

(42)

We need to modify the strategy slightly. The transmission strategy for the interference channel consists of two
phases. During Phase 1, uncoded bits intended for different receivers are transmitted. During Phases 2, using the
delayed CSIT, the previously transmitted bits are combined and repackaged to create bits of common interest.
These bits are then transmitted using the capacity-achieving strategy of the multicast problem. In the modified
strategy for the X-Channel, Phase 1 consists of two sub-phases. In the first sub-phase, both transmitters send out
bits intended for Rx1 while in the second sub-phases, bits intended for Rx2 are communicated. This way we take
full advantage of the entire signal space at each receiver and the individual rates are no longer limited by the
capacity of a point-to-point channel. The second phase is identical to the Interference Channel.

18

W1

Tx1

R1+R2=(1-q2)
G11 [t

]

t]
G 21[

W2

Rx1

^2
^ 1,W
W

p

Tx2

p

Fig. 9. The multiple-access channel formed at Rx1 and its capacity region.

Achieving unequal rates for different users follows the same logic with careful application of sub-problems as
described in Section V-B. Another example is corner point
(R0 , R1 , R2 ) = (0, 3/4, 0)

(43)

of Fig. 2(a). This corner point corresponds to the Multiple-Access Channel formed at Rx1 as depicted in Fig. 9.
In this section, we presented the transmission strategy for CSUM (R0 ) where 0 ≤ R0 ≤ (1−q 2 ). We also discussed
and highlighted the strategy for other corner points of the capacity region.
VI. C ONCLUSION
We established the capacity region of finite-field fading X-Channels with common messages and delayed CSIT.
We presented a new set of outer-bounds for this problem that relied on an extremal entropy inequality developed
specifically for this problem. We then showed how the outer-bounds can be achieved by treating the X-Channel as
a combination of a number of well-known problems such the interference channel and the multicast channel.
An important future work is to study Gaussian X-Channels with delayed CSIT. One approach could be to extend
our results to the multi-layer finite-field fading setting similar to [14] and then, derive the capacity region of the
Gaussian X-Channels to within a constant number of bits.
R EFERENCES
[1] R. Ahlswede, “The capacity region of a channel with two senders and two receivers,” The Annals of Probability, pp. 805–814, 1974.
[2] H. Sato, “Two-user communication channels,” IEEE Transactions on Information Theory, vol. 23, no. 3, pp. 295–304, 1977.
[3] T. S. Han and K. Kobayashi, “A new achievable rate region for the interference channel,” IEEE Transactions on Information Theory,
vol. 27, pp. 49–60, Jan. 1981.
[4] R. H. Etkin, D. N. Tse, and H. Wang, “Gaussian interference channel capacity to within one bit,” IEEE Transactions on Information
Theory, vol. 54, no. 12, pp. 5534–5562, 2008.
[5] M. A. Maddah-Ali, A. S. Motahari, and A. K. Khandani, “Communication over MIMO X channels: Interference alignment,
decomposition, and performance analysis,” IEEE Transactions on Information Theory, vol. 54, no. 8, pp. 3457–3470, 2008.
[6] S. A. Jafar and S. Shamai, “Degrees of freedom region of the MIMO X channel,” IEEE Transactions on Information Theory, vol. 54,
no. 1, pp. 151–170, 2008.

19

[7] M. J. Abdoli, A. Ghasemi, and A. K. Khandani, “On the degrees of freedom of K-user SISO interference and X channels with delayed
CSIT,” IEEE transactions on Information Theory, vol. 59, no. 10, pp. 6542–6561, 2013.
[8] A. Ghasemi, A. S. Motahari, and A. K. Khandani, “On the degrees of freedom of X channel with delayed CSIT,” in Information
Theory Proceedings (ISIT), 2011 IEEE International Symposium on, pp. 767–770, IEEE, 2011.
[9] S. Lashgari, A. S. Avestimehr, and C. Suh, “Linear degrees of freedom of the X-channel with delayed CSIT,” IEEE Transactions on
Information Theory, vol. 60, no. 4, pp. 2180–2189, 2014.
[10] A. Vahid, M. A. Maddah-Ali, and A. S. Avestimehr, “Capacity results for binary fading interference channels with delayed CSIT,”
IEEE Transactions on Information Theory, vol. 60, no. 10, pp. 6093–6130, 2014.
[11] K. Jolfaei, S. Martin, and J. Mattfeldt, “A new efficient selective repeat protocol for point-to-multipoint communication,” in IEEE
International Conference on Communications (ICC’93), vol. 2, pp. 1113–1117, IEEE, 1993.
[12] L. Georgiadis and L. Tassiulas, “Broadcast erasure channel with feedback-capacity and algorithms,” in Workshop on Network Coding,
Theory, and Applications (NetCod’09), pp. 54–61, IEEE, 2009.
[13] C.-C. Wang, “On the capacity of 1-to-k broadcast packet erasure channels with channel output feedback,” IEEE Transactions on
Information Theory, vol. 58, no. 2, pp. 931–956, 2012.
[14] N. David and R. D. Yates, “Fading broadcast channels with state information at the receivers,” IEEE Transactions on Information
Theory, vol. 58, no. 6, pp. 3453–3471, 2012.

