1

A New Coding Paradigm
for the Primitive Relay Channel

arXiv:1801.03153v1 [] 9 Jan 2018

Marco Mondelli, S. Hamed Hassani, and Rüdiger Urbanke

Abstract—We present a coding paradigm that provides a new
achievable rate for the primitive relay channel by combining
compress-and-forward and decode-and-forward with a chaining
construction.
In the primitive relay channel model, the source broadcasts
a message to the relay and to the destination; and the relay
facilitates this communication by sending an additional message
to the destination through a separate channel. Two well-known
coding approaches for this setting are decode-and-forward and
compress-and-forward: in the former, the relay decodes the
message and sends some of the information to the destination;
in the latter, the relay does not attempt to decode, but it sends a
compressed description of the received sequence to the destination
via Wyner-Ziv coding.
In our scheme, we transmit over pairs of blocks and we use
compress-and-forward for the first block and decode-and-forward
for the second. In particular, in the first block, the relay does not
attempt to decode and it sends only a part of the compressed
description of the received sequence; in the second block, the
relay decodes the message and sends this information plus the
remaining part of the compressed sequence relative to the first
block. As a result, we strictly outperform both compress-andforward and decode-and-forward. Furthermore, this paradigm
can be implemented with a low-complexity polar coding scheme
that has the typical attractive features of polar codes, i.e., quasilinear encoding/decoding complexity and super-polynomial decay
of the error probability. Throughout the paper we consider as
a running example the special case of the erasure relay channel
and we compare the rates achievable by our proposed scheme
with the existing upper and lower bounds.

I. I NTRODUCTION
The relay channel was introduced by van der Meulen [1]
and it represents the simplest network model: a source wants
to communicate with a destination with the help of a relay. As
schematized in Figure 1, the source sends XS to the relay and
to the destination, the relay receives YSR and sends XR to the
destination, and the destination receives YD from the source
and from the relay. Hence, the relay channel has a broadcast
component that goes from the source to the relay and to the
destination, and a multiple access component that goes from
the source and from the relay to the destination.
In their seminal work [2], Cover and El Gamal introduced two basic achievability lower bounds, namely, decodeand-forward and compress-and-forward, and a general upper
M. Mondelli is with the Department of Electrical Engineering, Stanford
University, USA (e-mail: mondelli@stanford.edu).
S. H. Hassani is with the Department of Electrical and Systems Engineering,
University of Pennsylvania, USA (e-mail: hassani@seas.upenn.edu).
R. Urbanke is with the School of Computer and Communication Sciences,
EPFL, CH-1015 Lausanne, Switzerland (e-mail: ruediger.urbanke@epfl.ch).

Relay
YSR
Source

XS

XR

pYSR ,YD |XR ,XS

YD

Destination

Figure 1: General relay channel.

Relay

XR

YSR
Source

XS

pYSR ,YSD |XS

pYRD |XR
YSD

YRD

Destination

Figure 2: Primitive relay channel: relay channel with orthogonal receiver components.

bound, namely, the cut-set bound. Since then, many other lower
bounds have been discovered, namely, amplify-and-forward,
quantize-map-and-forward, compute-and-forward, noisy network coding, hybrid coding, etc [3]–[7]. Furthermore, in most
of the cases where the capacity is known, the converse is
given by the cut-set bound [2], [8]–[10]. However, the cut-set
bound has been shown not be tight for some specific examples
of relay channels [11], [12]. New upper bounds tighter than
the cut-set bound were recently developed in [13]–[16]. For a
literature review on the relay channel, the interested reader is
referred to [17, Chapter 16] and [18, Chapter 9].
Recent works have been aimed at providing practical
schemes using the paradigm of polar coding, introduced by
Arıkan in the seminal paper [19]. In particular, polar coding
schemes for decode-and-forward are proposed in [20]–[23]
for degraded relay channels, where XS → (XR , YSR ) → YD
forms a Markov chain. Furthermore, a polar coding scheme for
compress-and-forward is presented in [22] for relay channels
with orthogonal receiver components. Eventually, polar coding
schemes for decode-and-forward and compress-and-forward
are described in [24] for general relay channels.
Soft decode-and-forward relaying strategies using LDPC
codes are developed and analyzed in [25].
In this paper, we focus on relay channels with orthogonal
receiver components, also known as primitive relay channels.
As schematized in Figure 2, the destination receives separately
YSD from the source and YRD from the relay. In other words, the

2

Relay
YSR
BEC(εSR )

Source

XS

channel. In Section V, we provide some concluding remarks.

XR
pYRD |XR

BEC(εSD )

YSD

II.
YRD

Destination

Figure 3: Erasure relay channel: primitive relay channel in
which the link from source to relay is a BEC(εSR ) and the link
from source to destination is a BEC(εSD ).

multiple access component that for the general relay channel
goes from the source and from the relay to the destination
is substituted by two parallel channels. Consequently, without
loss of generality, we can assume that the link between relay
and destination is a noiseless channel of capacity CRD . Indeed,
the relay can always use an optimal point-to-point scheme to
communicate with the destination. We also assume that the
relay is full-duplex, in the sense that it can listen and transmit
simultaneously. Despite this simplification, the capacity of
the primitive relay channel is not known in general. For a
review on coding techniques for the primitive relay channel,
the interested reader is referred to [26].
Our main contribution consists in presenting a new coding
scheme that, by combining compress-and-forward and decodeand-forward, strictly improves on both these lower bounds. To
do so, we code over pairs of blocks and employ a chaining
construction: in the first block, we perform a variant of
compress-and-forward in which the relay is not required to
send the whole compressed sequence to the destination; in
the second block, we perform decode-and-forward and the
relay sends to the destination the new information bits plus the
remaining part of the compressed sequence from the previous
block. The idea of chaining was originally introduced in [27]
to construct universal codes and in [28] to achieve strong
security guarantees on degraded wiretap channels. Since then,
it has been exploited in several non-standard scenarios (e.g.,
broadcast channels [29], [30], asymmetric channels [31], [32],
wiretap channels [33]). Our coding paradigm can be implemented with codes that are suitable for compress-and-forward
and decode-and-forward. As such, polar codes represent an
appealing choice [24]: their encoding/decoding complexity√ is
Θ(n log n) and their error probability scales roughly as 2− n ,
where n is the block length.
The reminder of this paper is organized as follows. In
Section II, we review the existing upper bounds (cut-set and its
improvements) and lower bounds (direct transmission, decodeand-forward, and compress-and-forward) for the primitive relay channel and we specialize them to the case of the erasure
relay channel. In Section III, we state our new lower bound
and we show how to achieve it. In Section IV, we compare the
rates achievable by our new strategy with the existing upper
and lower bounds for the special case of the erasure relay

E XISTING U PPER AND L OWER B OUNDS

We assume that all channels are binary memoryless and
symmetric (BMS). We denote by h2 (x) = −x log2 x − (1 −
x) log2 (1 − x) the binary entropy function and by XR , YSR , and
YSD the alphabets associated to XR , YSR , and YSD , respectively.
We define a ◦ b = a + b(1 − a) for any a, b ∈ R.
Throughout the paper, we will use as a running example
the special case of the erasure relay channel. As schematized
in Figure 3, in the erasure relay channel the links between
source and destination and between source and relay are binary
erasure channels (BECs) with erasure probabilities εSD and εSR ,
respectively.
A. Cut-Set Upper Bound
For the general relay channel, the cut-set upper bound on
the achievable rate R is given by [17, Theorem 16.1]
R ≤ max min{I(XS , XR ; YD ); I(XS ; YSR , YD |XR )}.
pXS ,XR

(1)

For the case of the primitive relay channel, the cut-set bound
specializes to [26, Proposition 1]
R ≤ max min{I(XS ; YSD ) + CRD ; I(XS ; YSR , YSD )}.
pXS

(2)

For the special case of the erasure relay channel, the cut-set
bound can be rewritten as
R ≤ min{1 − εSD + CRD ; 1 − εSR εSD }.

(3)

B. Improvements on Cut-Set Upper Bound
For the case of the primitive relay channel, an upper
bound demonstrating an explicit gap to the cut-set bound was
presented in [13]. Furthermore, two new upper bounds that
are generally tighter than cut-set are proposed in [14] for
the symmetric primitive relay channel, in which YSR and YSD
are conditionally identically distributed given XS . The results
of [14] are extended to the non-symmetric case and to the
Gaussian case in [15] and [16], respectively.
Let us now state the result in [15, Theorem 3.1], which
provides an extension of the first bound of [14]. If a rate R
is achievable, then there exists some pXS (xS ) and a ≥ 0 such
that

R ≤ I(XS ; YSR , YSD ),







R ≤ I(XS ; YSD ) + CRD − a,




!
r
(4)
a
ln
2


R ≤ I(XS ; YSD , ỸSR ) + h2


2


r



a ln 2


log2 (|YSR | − 1) − a,
+
2
for any random variable ỸSR with the same conditional distribution as YSR given XS . The evaluation of the term I(XS ; YSD , ỸSR )

3

that gives the tightest bound is simple in the following special
cases:
1) Symmetric (YSR and YSD conditionally identically distributed given XS ): I(XS ; YSD , ỸSR ) = I(XS ; YSD ).
2) Degraded (YSD stochastically degraded version of YSR ):
I(XS ; YSD , ỸSR ) = I(XS ; YSR ).
3) Reversely degraded (YSR stochastically degraded version
of YSD ): I(XS ; YSD , ỸSR ) = I(XS ; YSD ).
For the special case of the erasure relay channel, the bound
can be re-written as
(

C. Direct Transmission Lower Bound
In the direct transmission, the source communicates with
the destination by using an optimal point-to-point code. The
relay transmission is fixed at the most favorable symbol for
the channel from the source to the destination.
For the general relay channel, direct transmission allows to
achieve the following rate [17, Section 16.3]:
RDT = max I(XS ; YD |XR = xR ).
pXS ,xR

For the case of the primitive relay channel, the direct
transmission lower bound specializes to

R ≤ max min 1 − εSR εSD , 1 − εSD + CRD − a,

RDT = max I(XS ; YSD ).

a≥0

1 − min{εSR , εSD } + h2

r

a ln 2
2

!

+

r

) (5)
a ln 2
−a .
2

In order to present the second bound of [14], we need some
preliminary definitions. Given a channel transition probability
p(ω|x), for any p(x) and d ≥ 0, we define ∆(p(x), d) as
∆(p(x),d) = max H(p̃(ω|x)|p(x))

p̃(ω|x)
 (6)
+ D(p̃(ω|x)||p(ω|x)|p(x)) − H(p(ω|x)|p(x)) ,

subject to the condition

1 X
|p(x)p̃(ω|x) − p(x)p(ω|x)| ≤ d,
2

(7)

(x,ω)

where D(p̃(ω|x)||p(ω|x)|p(x)) is the conditional relative entropy defined as
D(p̃(ω|x)||p(ω|x)|p(x)) =

X

(x,ω)

p(x)p̃(ω|x) log 2

p̃(ω|x)
,
p(ω|x)

(8)
H(p̃(ω|x)|p(x)) is the conditional entropy defined with respect
to the joint distribution p(x)p̃(ω|x), i.e.,
X
p(x)p̃(ω|x) log2 p̃(ω|x),
(9)
H(p̃(ω|x)|p(x)) = −
(x,ω)

and H(p(ω|x)|p(x)) is the conditional entropy similarly defined with respect to p(x)p(ω|x). At this point, we can state
the result in [14, Theorem 4.2]. If a rate R is achievable, then
there exists some pXS (xS ) and a ∈ [0, min{CRD , H(YSR | XS )}]
such that

R ≤ I(XS ; YSR , YSD ),


 R ≤ I(XS ; YSD ) + CRD − a,
!
r
(10)
a ln 2


.
 R ≤ I(XS ; YSD ) + ∆ pXS (xS ),
2
As pointed out at the end of Section IV.C of [14], for the
special case of the symmetric erasure relay channel, we have
that ∆(pXS (xS ), d) = ∞ for all pXS (xS ) and d > 0. Thus, (10)
reduces to the cut-set bound (3).

(11)

pXS

(12)

Note that the direct transmission lower bound (12) meets
the cut-set upper bound (2) and it equals the capacity of
the primitive relay channel when either of the following two
conditions holds:
1) the primitive relay channel is reversely degraded, which
implies that I(XS ; YSD ) = I(XS ; YSR , YSD );
2) CRD = 0.
For the special case of the erasure relay channel, the direct
transmission lower bound can be rewritten as
RDT = 1 − εSD .

(13)

The direct transmission lower bound (13) meets the cut-set
upper bound (3) and it equals the capacity of the erasure relay
channel when either 1 − εSD = 1 − εSR εSD or CRD = 0.
D. Decode-and-Forward Lower Bound
In decode-and-forward, the relay completely decodes the
received sequence and cooperates with the source to communicate the message to the destination.
For the general relay channel, decode-and-forward allows
to achieve the following rate [17, Theorem 16.2]:
RDF = max min{I(XS , XR ; YD ), I(XS ; YSR |XR )}.
pXS ,XR

(14)

For the case of the primitive relay channel, the decode-andforward lower bound specializes to [26, Proposition 2]
R = max min{I(XS ; YSD ) + CRD ; I(XS ; YSR )}.
pXS

(15)

Note that the decode-and-forward lower bound (15) meets
the cut-set upper bound (2) and it equals the capacity of
the primitive relay channel when either of the following two
conditions holds:
1) the primitive relay channel is degraded, which implies
that I(XS ; YSR ) = I(XS ; YSR , YSD );
2) I(XS ; YSR ) ≥ I(XS ; YSD ) + CRD .
For the special case of the erasure relay channel, the decodeand-forward lower bound can be rewritten as
R = min{1 − εSD + CRD ; 1 − εSR }.

(16)

The decode-and-forward lower bound (16) meets the cut-set
upper bound (3) and it equals the capacity of the erasure relay
channel when either 1 − εSR = 1 − εSR εSD or 1 − εSD + CRD ≤
1 − εSR .

4

E. Compress-and-Forward Lower Bound
In compress-and-forward, the relay does not attempt to
decode the received sequence, but it sends a (possibly compressed) description of it, denoted by ŶSR , to the destination.
Since this description is correlated with the sequence received
by the destination from the source, Wyner-Ziv coding is used
to reduce the rate needed to communicate it to the destination.
For the general relay channel, compress-and-forward allows
to achieve the following rate [17, Theorem 16.4]:
RCF =

max min{I(XS , XR ; YD ) − I(YSR ; ŶSR |XS , XR , YD ),

pXS pXR pŶ

I(XS ; ŶSR , YD |XR )},
(17)
where the cardinality of the alphabet associated to ŶSR can be
bounded as |ŶSR | ≤ |XR | · |YSR | + 1. This expression can be
equivalently rewritten as [17, Remark 16.3]
max

pXS pXR pŶ

I(XS ; ŶSR , YSD ) = H(XS ) − H(XS |ŶSR , YSD )
= H(XS )(1 − (ε̂R ◦ εSR ) · εSD ).

(21)

Clearly, I(XS ; ŶSR , YSD ) is maximized by setting pXS to the
uniform distribution. Furthermore,
H(ŶSR |YSR , YSD ) = H(ŶSR |YSR ) = (1 − εSR )h2 (ε̂R ),
H(ŶSR |YSD ) = h2 (εSR ◦ ε̂R ) + εSD (1 − εSR ◦ ε̂R ).

(22)

As a result, the rate (19) can be rewritten as

SR |XR ,YSR

RCF =

probability 1; if YSR ∈ {0, 1}, then ŶSR =? with probability ε̂R
and ŶSR = YSR with probability 1 − ε̂R . Consequently,

{I(XS ; ŶSR , YD |XR ) :

SR |XR ,YSR

(18)

I(YSR ; ŶSR |XR , YD ) ≤ I(XR ; YD )}.
The bound is in general not convex, therefore it can be
improved via time sharing.
For the case of the primitive relay channel, the compressand-forward lower bound specializes to [26, Proposition 3]
RCF = max {I(XS ; ŶSR , YSD ) : I(YSR ; ŶSR |YSD ) ≤ CRD }, (19)
pXS pŶ

SR |YSR

0≤ε̂R ≤1

h2 (εSR ◦ ε̂R ) + εSD (1 − εSR ◦ ε̂R ) − (1 − εSR )h2 (ε̂R ) ≤ CRD }.
(23)
III. M AIN R ESULT
We are now ready to state our new lower bound for the
primitive relay channel.
Theorem 1. Consider the transmission over a primitive relay
channel, where the source sends XS to the relay and the destination, the relay receives YSR from the source, the destination
receives YSD from the source, and relay and destination are
connected via a noiseless link with capacity CRD . Furthermore,
denote by ŶSR the compressed description of YSR transmitted by
the relay. Then, the following rate is achievable:
RDF−CF =

with |ŶSR | ≤ |YSR | + 1.
Note that the compress-and-forward lower bound (19) meets
the cut-set upper bound (2) and it equals the capacity of
the primitive relay channel when H(YSR |YSD ) ≤ CRD . Indeed,
in this case, we can pick ŶSR = YSR , namely, the relay
performs Slepian-Wolf source coding. Therefore, RCF =
I(XS ; YSR , YSD ), which is one of the two terms in the cut-set
bound.
On the contrary, if H(YSR |YSD ) > CRD , then we degrade
YSR into ŶSR , namely, the relay performs a step of lossy
source coding. The relay transmits this lossy description to the
destination that can decode it successfully since ŶSR requires
less bits than YSR . However, after that the destination has
recovered ŶSR , there is a penalty loss: we can achieve rates
up to I(XS ; ŶSR , YSD ), instead of up to I(XS ; YSR , YSD ).
For the case of the erasure relay channel, we have that
H(YSR |YSD ) = h2 (εSR ) + εSD (1 − εSR ).

RCF = max {1 − (ε̂R ◦ εSR ) · εSD :

(20)

Hence, if CRD ≥ h2 (εSR ) + εSD (1 − εSR ), then the compressand-forward lower bound meets the cut-set upper bound and
it equals the capacity of the erasure relay channel.
On the contrary, if CRD < h2 (εSR ) + εSD (1 − εSR ), it is
not easy to find the best choice of ŶSR even for this simple
scenario. Following [25], let us assume that ŶSR is the output
of an erasure-erasure channel (EEC) with erasure probability
ε̂R and input YSR . This means that if YSR =?, then ŶSR =? with


CRD − max{0, I(XS ; YSR ) − I(XS ; YSD )} I(XS ; ŶSR , YSD )

I(YSR ; ŶSR | YSD ) − max{0, I(XS ; YSR ) − I(XS ; YSD )}

max{I(XS ; YSR ), I(XS ; YSD )} I(YSR ; ŶSR | YSD ) − CRD
,
+
I(YSR ; ŶSR | YSD ) − max{0, I(XS ; YSR ) − I(XS ; YSD )}
(24)

for any joint distribution pXS pŶSR |YSR such that
I(XS ; YSR ) < I(XS ; YSD ) + CRD ,
I(YSR ; ŶSR |YSD ) ≥ CRD ,

(25)
(26)

and where |ŶSR | ≤ |YSR | + 1. Furthermore, the rate (24) can
be achieved by a polar coding scheme with encoding/decoding
β
complexity Θ(n log n) and error probability O(2−n ) for any
β ∈ (0, 1/2), where n is the block length.
Remark 2. If (25) does not hold, then decode-and-forward
achieves the cut-set bound and it is optimal. Furthermore, if
(26) does not hold, then our scheme reduces to compress-andforward and the achievable rate is given by (19).
The special case of the erasure relay channel is handled by
the corollary below.
Corollary 3. Consider the transmission over the erasure relay
channel, where YSD is obtained from XS via a BEC(εSD ), YSR
is obtained from XS via a BEC(εSR ), ŶSR is obtained from YSR
via an EEC(ε̂R ), and the relay is connected to the destination

5

(CRD − max{0, εSD − εSR })(1 − (ε̂R ◦ εSR ) · εSD )
h2 (εSR ◦ ε̂R ) + εSD (1 − εSR ◦ ε̂R ) − (1 − εSR )h2 (ε̂R ) − max{0, εSD − εSR }
max{1 − εSR , 1 − εSD }(h2 (εSR ◦ ε̂R ) + εSD (1 − εSR ◦ ε̂R ) − (1 − εSR )h2 (ε̂R ) − CRD )
.
+
h2 (εSR ◦ ε̂R ) + εSD (1 − εSR ◦ ε̂R ) − (1 − εSR )h2 (ε̂R ) − max{0, εSD − εSR }

RDF−CF =

via a noiseless link with capacity CRD . Then, the rate (27) is
achievable for any ε̂R ∈ [0, 1] such that
1 − εSR < 1 − εSD + CRD ,
(28)
h2 (εSR ◦ ε̂R ) + εSD (1 − εSR ◦ ε̂R ) − (1 − εSR )h2 (ε̂R ) ≥ CRD .
(29)
Furthermore, the rate (27) can be achieved by a polar coding
scheme with encoding/decoding complexity Θ(n log n) and
β
error probability O(2−n ) for any β ∈ (0, 1/2), where n is
the block length.
The proof of Corollary 3 easily follows from the application
of Theorem 1 and of formulas (21)-(22).
We can now proceed with the proof of our main result.
Proof of Theorem 1: We start by presenting the main idea
of our scheme. We split the transmission into two blocks. In
the first block, we perform a variant of compress-and-forward:
the relay does not decode the received sequence, but it sends
a compressed description of it to the destination. However,
differently from standard compress-and-forward, we require
that (26) holds. Hence, we cannot transmit all the compressed
description ŶSR during the first block. In the second block, we
perform decode-and-forward: the relay completely decodes the
received sequence. Furthermore, we choose the length of the
second block so that the relay can transmit the part of ŶSR that
was not sent in the previous block plus the new information
needed to decode the second block.
Let us now describe this scheme more in detail and provide
the achievability proof of the rate (24). First, we deal with the
case I(XS ; YSR ) ≥ I(XS ; YSD ).
Consider the transmission of the first block. Denote by n1
and R1 the block length and the rate of the message transmitted
by the source, and let R1 approach from below I(XS ; ŶSR , YSD ).
The relay receives YSR and constructs the compressed description ŶSR . Recall that the destination receives the side
information YSD from the source. Hence, by using Wyner-Ziv
coding, the destination needs from the relay a number of bits
approaching from above I(YSR ; ŶSR | YSD )·n1 , in order to decode
the message sent by the source. As I(YSR ; ŶSR |YSD ) ≥ CRD , the
relay transmits right away a number of these bits approaching
from below CRD ·n1 . The number of remaining bits approaches
from above (I(YSR ; ŶSR |YSD ) − CRD ) · n1 and it is stored by the
relay. The destination stores the message received from the
relay and the observation YSD obtained from the source.
Consider the transmission of the second block and define
I(YSR ; ŶSR |YSD ) − CRD
.
α=
(30)
CRD − I(XS ; YSR ) − I(XS ; YSD )
Denote by n2 and R2 the block length and the rate of the
message transmitted by the source. Let n2 = n1 · α and let

(27)

R2 approach from below I(XS ; YSR ). The relay receives YSR
and successfully decodes the message. Again, the destination
receives the side information YSD from the source. Hence, it
needs from the relay a number of bits approaching from above
(I(XS ; YSR )−I(XS ; YSD ))·n1 ·α, in order to decode the message
sent by the source. The relay transmits to the destination these
(I(XS ; YSR ) − I(XS ; YSD )) · n1 · α information bits plus the
(I(YSR ; ŶSR |YSD ) − CRD ) · n1 bits remaining from the previous
block. This transmission is reliable as (30) implies that

I(XS ; YSR ) − I(XS ; YSD ) · n1 · α

(31)
+ I(YSR ; ŶSR |YSD ) − CRD · n1 = CRD · n2 .

At this point, the destination can reconstruct the second block
by using the side information received from the source and
the extra (I(XS ; YSR ) − I(XS ; YSD )) · n1 · α bits received from
the relay. Furthermore, it can also reconstruct the first block by
using the side information previously received from the source
and the extra I(YSR ; ŶSR | YSD ) · n1 bits received from the relay
(partly in the first and partly in the second block).
The overall block length is n = n1 + n2 = (1 + α)n1 and
the achievable rate is
R=

R1 + αR2
,
1+α

(32)

which approaches from below

CRD − (I(XS ; YSR ) − I(XS ; YSD )) I(XS ; ŶSR , YSD )

I(YSR ; ŶSR |YSD ) − I(XS ; YSR ) − I(XS ; YSD )

I(YSR ; ŶSR |YSD ) − CRD I(XS ; YSR )
+
,
I(YSR ; ŶSR |YSD ) − I(XS ; YSR ) − I(XS ; YSD )

(33)

Note that the expression (33) coincides with (24) when
I(XS ; YSR ) ≥ I(XS ; YSD ).
The case I(XS ; YSR ) < I(XS ; YSD ) is handled in a similar
way. As concerns the transmission of the first block, nothing
changes. Denote by n′1 and R1′ the block length and the rate
of the message transmitted by the source, and let R1′ approach
from below I(XS ; ŶSR , YSD ). The relay receives YSR and constructs the compressed description ŶSR . By using Wyner-Ziv
coding, the destination needs from the relay a number of bits
approaching from above I(YSR ; ŶSR | YSD )·n′1 , in order to decode
the message sent by the source. As I(YSR ; ŶSR |YSD ) ≥ CRD , the
relay transmits right away a number of these bits approaching
from below CRD ·n′1 . The number of remaining bits approaches
from above (I(YSR ; ŶSR |YSD ) − CRD ) · n′1 and it is stored by the
relay. The destination stores the message received from the
relay and the observation YSD obtained from the source.

6

As concerns the transmission of the second block, define
α′ =

I(YSR ; ŶSR |YSD ) − CRD
,
CRD

(34)

and denote by n′2 and R2′ the block length and the rate of
the message transmitted by the source. Let n′2 = n′1 · α′ and
let R2′ approach from below I(XS ; YSD ). The relay discards
the received message and transmits to the destination the
(I(YSR ; ŶSR |YSD ) − CRD ) · n′1 bits remaining from the previous
block. This transmission is reliable as (34) implies that

I(YSR ; ŶSR |YSD ) − CRD · n′1 = CRD · n′2 .
(35)

At this point, the destination can reconstruct the second block
by using the message received from the source. Furthermore,
it can also reconstruct the first block by using the side
information previously received from the source and the extra
I(YSR ; ŶSR | YSD ) · n1 bits received from the relay (partly in the
first and partly in the second block).
The overall block length is n′ = n′1 + n′2 = (1 + α′ )n′1 and
the achievable rate is
R′ + α′ R2′
R′ = 1
,
(36)
1 + α′
which approaches from below

CRD · I(XS ; ŶSR , YSD ) + I(YSR ; ŶSR |YSD ) − CRD I(XS ; YSD )
.
I(YSR ; ŶSR |YSD )
(37)
Note that the expression (37) coincides with (24) when
I(XS ; YSR ) < I(XS ; YSD ).
Clearly, the coding scheme described so far can be implemented with codes that are suitable for compress-and-forward
and for decode-and-forward. Hence, we can employ the polar
coding schemes for compress-and-forward and for decode-andforward presented in [24]. However, polar codes require block
lengths n1 and n2 (or n′1 and n′2 ) that are powers of two,
which puts a constraint on the possible values for α = n2 /n1
(or α′ = n′2 /n′1 ). To remove this constraint and achieve the
rate (24) for any α, it suffices to use the punctured polar codes
described in [34, Theorem 1].

IV. N UMERICAL R ESULTS
Let us consider the special case of the erasure relay channel.
In Figure 4, we compare the achievable rate (27) of our scheme
with the existing upper and lower bounds, i.e., the cut-set upper
bound (3) (which coincides with the improved bound (5)), the
decode-and-forward lower bound (16) and the compress-andforward lower bound (23). We consider two pairs of choices
for εSD and εSR : (εSD , εSR ) = (0.85, 0.5) for the plot on the
left, and (εSD , εSR ) = (0.4, 0.2) for the plot on the right. We
plot the various bounds as functions of CRD . Note that our
scheme outperforms both decode-and-forward and compressand-forward for an interval of values of CRD in both settings.
In [25], for εSD = 0.85, εSR = 0.5 and CRD = 0.99125,
the proposed soft decode-and-forward strategy based on LDPC
codes achieves a rate of 0.507, while both decode-and-forward

and compress-and-forward achieve a rate of 0.5. Our new
coding strategy is reliable for rates up to 0.545, hence it
outperforms all existing lower bounds. As a reference, note
that in this setting the cut-set bound is 0.575.
V. C ONCLUDING R EMARKS
We have proposed a new coding paradigm for the primitive relay channel that combines compress-and-forward and
decode-and-forward by means a chaining construction. The
achievable rates obtained by our scheme surpass the stateof-the-art coding approaches (compress-and-forward, decodeand-forward, and the soft decode-and-forward strategy of [25]).
Furthermore, our paradigm can be implemented with a lowcomplexity polar coding scheme that has the typical attractive
features of polar codes, i.e., quasi-linear encoding/decoding
complexity and super-polynomial decay of the error probability.
ACKNOWLEDGMENT
M. Mondelli was supported by an Early Postdoc.Mobility
fellowship from the Swiss NSF. R. Urbanke was supported by
grant No. 200021_156672/1 of the Swiss NSF.
R EFERENCES
[1]
[2]
[3]
[4]

[5]

[6]

[7]

[8]
[9]
[10]
[11]
[12]

[13]

[14]

E. C. van der Meulen, “Three-terminal communication channels,” Adv.
Appl. Prob., vol. 3, pp. 120–154, 1971.
T. Cover and A. E. Gamal, “Capacity theorems for the relay channel,”
IEEE Trans. Inform. Theory, vol. 25, pp. 572–584, 1979.
B. Schein and R. Gallager, “The Gaussian parallel relay network,” in
Proc. of the IEEE Int. Symposium on Inform. Theory, June 2000, p. 22.
A. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, “Wireless network
information flow: A deterministic approach,” IEEE Trans. Inform.
Theory, vol. 57, no. 4, pp. 1872–1905, Apr. 2011.
B. Nazer and M. Gastpar, “Compute-and-forward: Harnessing interference through structured codes,” IEEE Trans. Inform. Theory, vol. 57,
no. 10, pp. 6463–6486, Oct. 2011.
S. H. Lim, Y.-H. Kim, A. E. Gamal, and S.-Y. Chung, “Noisy network
coding,” IEEE Trans. Inform. Theory, vol. 57, no. 5, pp. 3132–3152,
May 2011.
P. Minero, S. H. Lim, and Y.-H. Kim, “A unified approach to hybrid
coding,” IEEE Trans. Inform. Theory, vol. 61, no. 4, pp. 1509–1523,
Apr. 2015.
S. Zahedi, “On reliable communication over relay channels,” Ph.D.
dissertation, Stanford University, Stanford, CA, 2005.
A. E. Gamal and M. Aref, “The capacity of the semideterministic relay
channel,” IEEE Trans. Inform. Theory, vol. 28, no. 3, p. 536, May 1982.
Y.-H. Kim, “Capacity of a class of deterministic relay channels,” IEEE
Trans. Inform. Theory, vol. 54, no. 3, pp. 1328–1329, Mar. 2008.
Z. Zhang, “Partial converse for a relay channel,” IEEE Trans. Inform.
Theory, vol. 34, no. 5, pp. 1106–1110, Sept. 1988.
M. Aleksic, P. Razaghi, and W. Yu, “Capacity of a class of modulosum relay channels,” IEEE Trans. Inform. Theory, vol. 55, no. 3, pp.
921–930, Mar. 2009.
F. Xue, “A new upper bound on the capacity of a primitive relay channel
based on channel simulation,” IEEE Trans. Inform. Theory, vol. 60,
no. 8, pp. 4786–4798, Aug. 2014.
X. Wu, A. Özgür, and L.-L. Xie, “Improving on the cut-set bound via
geometric analysis of typical sets,” IEEE Trans. Inform. Theory, vol. 63,
no. 4, pp. 2254–2277, Apr. 2017.

7

(a) εSD = 0.85 and εSR = 0.5

(b) εSD = 0.4 and εSR = 0.2

Figure 4: Comparison between the achievable rate provided by our strategy and the existing upper and lower bounds. We use
“CF" and “DF" as abbreviations for “compress-and-forward” and “decode-and-forward”, respectively.

[15]

X. Wu and A. Özgür, “Improving on the cut-set bound for general
primitive relay channels,” in Proc. of the IEEE Int. Symposium on
Inform. Theory, Barcelona, Spain, Jul. 2016, pp. 1675–1679.

[29]

[16]

——, “Cut-set bound is loose for gaussian relay networks,” in Proc. of
the Allerton Conf. on Commun., Control, and Computing, Monticello,
IL, USA, Oct. 2015, pp. 1135–1142.

[30]

[17]

A. E. Gamal and Y.-H. Kim, Network Information Theory. Cambridge
University Press, 2011.

[31]

[18]

G. Kramer, “Topics in multi-user information theory,” Found. Trends
Commun. Inf. Theory, vol. 4, no. 4-5, pp. 265–444, Apr. 2007.
E. Arıkan, “Channel polarization: A method for constructing capacityachieving codes for symmetric binary-input memoryless channels,”
IEEE Trans. Inform. Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009.
M. Andersson, V. Rathi, R. Thobaben, J. Kliewer, and M. Skoglund,
“Nested polar codes for wiretap and relay channels,” IEEE Commun.
Lett., vol. 14, no. 8, pp. 752–754, Aug. 2010.

[19]

[20]

[21]
[22]

[23]

[24]
[25]

[26]

[27]
[28]

M. Karzand, “Polar codes for degraded relay channels,” in Proc. Intern.
Zurich Seminar on Comm., Feb. 2012, pp. 59–62.
R. Blasco-Serrano, R. Thobaben, M. Andersson, V. Rathi, and
M. Skoglund, “Polar codes for cooperative relaying,” IEEE Trans.
Commun., vol. 60, no. 11, pp. 3263–3273, Nov. 2012.
D. Karas, K. Pappi, and G. Karagiannidis, “Smart decode-and-forward
relaying with polar codes,” IEEE Wireless Comm. Letters, vol. 3, no. 1,
pp. 62–65, Feb. 2014.
L. Wang, “Polar coding for relay channels,” in Proc. of the IEEE Int.
Symposium on Inform. Theory, Hong Kong, June 2015, pp. 1532–1536.
A. Bennatan, S. Shamai, and A. R. Calderbank, “Soft-decoding-based
strategies for relay and interference channels: Analysis and achievable
rates using LDPC codes,” IEEE Trans. Inform. Theory, vol. 60, no. 4,
pp. 1977–2009, Apr. 2014.
Y.-H. Kim, “Coding techniques for primitive relay channels,” in Proc. of
the Allerton Conf. on Commun., Control, and Computing, Monticello,
IL, USA, Sept. 2007, pp. 26–28.
S. H. Hassani and R. Urbanke, “Universal polar codes,” Dec. 2013,
[Online]. Available: http://arxiv.org/abs/1307.7223.
E. Şaşoğlu and A. Vardy, “A new polar coding scheme for strong
security on wiretap channels,” in Proc. of the IEEE Int. Symposium
on Inform. Theory, Istanbul, Turkey, July 2013, pp. 1117–1121.

[32]

[33]

[34]

M. Mondelli, S. H. Hassani, I. Sason, and R. Urbanke, “Achieving
Marton’s region for broadcast channels using polar codes,” IEEE Trans.
Inform. Theory, vol. 61, no. 2, pp. 783–800, Feb. 2015.
R. A. Chou and M. R. Bloch, “Polar coding for the broadcast channel
with confidential messages: A random binning analogy,” IEEE Trans.
Inform. Theory, vol. 62, no. 5, pp. 2410–2429, May 2016.
M. Mondelli, S. H. Hassani, and R. Urbanke, “How to
achieve the capacity of asymmetric channels,” accepted in
IEEE Trans. Inform. Theory, Jan. 2018. [Online]. Available:
http://arxiv.org/abs/1406.7373.
E. E. Gad, Y. Li, J. Kliewer, M. Langberg, A. Jiang, and J. Bruck,
“Asymmetric error correction and flash-memory rewriting using polar
codes,” IEEE Trans. Inform. Theory, vol. 62, no. 7, pp. 4024–4038, July
2016.
Y.-P. Wei and S. Ulukus, “Polar coding for the general wiretap channel
with extensions to multiuser scenarios,” IEEE J. Select. Areas Commun.,
vol. 34, no. 2, pp. 278–291, Feb. 2016.
S.-N. Hong, D. Hui, and I. Marić, “Capacity-achieving rate-compatible
polar codes,” IEEE Trans. Inform. Theory, vol. 63, no. 12, pp. 7620–
7632, Dec. 2017.

