Ferkans — Interactive Telecom Tutor

The Simplest Relay Strategy

The most natural thing a relay can do is decode the source's message and then re-encode it, effectively creating a two-hop communication path. This is decode-and-forward (DF), and it is the relay analogue of "store-and-forward" in packet networks. The key challenge is that the relay must decode and help the destination simultaneously — it cannot simply wait until it has decoded the entire message before forwarding. This leads to the elegant technique of block-Markov encoding, where the relay in block $b$ helps with the message from block $b-1$ while the source starts transmitting the message for block $b$ .

Definition:
Block-Markov Encoding

In block-Markov encoding, the total communication is divided into $B$ blocks of $n$ channel uses each. The source sends a fresh message $W_b$ in each block $b \in \{1, \ldots, B\}$ . The key idea is layered cooperation:

In block $b$ , the source transmits a codeword that encodes both the new message $W_b$ and cooperative information about the previous message $W_{b-1}$ .
The relay, having decoded $W_{b-1}$ at the end of block $b-1$ , transmits a cooperative codeword in block $b$ that helps the destination decode $W_{b-1}$ .

The total rate is $R = \frac{B}{B+1} \cdot \frac{nR'}{n}$ , where $R'$ is the per-block rate. As $B \to \infty$ , the rate loss factor $B/(B+1) \to 1$ .

,

Block-Markov Encoding

A multi-block coding technique where the encoding in each block depends on the message of the current block and the message of the previous block, enabling cooperation between source and relay across consecutive blocks.

Related: Backward Decoding

Theorem: Decode-and-Forward Achievable Rate

For the discrete memoryless relay channel $p(y, y_r | x, x_r)$ , the following rate is achievable using decode-and-forward with block-Markov encoding: $R_{\text{DF}} = \max_{p(x, x_r)} \min\bigl\{I(X; Y_r \mid X_r),\; I(X, X_r; Y)\bigr\}.$

The first term is the rate at which the relay can decode the source message, and the second term is the rate at which the source-relay pair can communicate to the destination.

Decode-and-forward faces two bottlenecks: (1) the relay must be able to decode the source message, which requires $R \leq I(X; Y_r \mid X_r)$ , and (2) the source and relay together must be able to deliver the message to the destination, which requires $R \leq I(X, X_r; Y)$ . The achievable rate is the minimum of these two constraints, optimized over the joint input distribution.

The point is that decode-and-forward converts the relay channel into a cascade of a point-to-point channel (source to relay) and a MAC-like channel (source + relay to destination). The price is that the relay must fully decode — if the source-relay link is weak, DF suffers.

Proof

Codebook generation

Fix a distribution $p(x, x_r)$ . For each block $b \in \{1, \ldots, B\}$ :

Generate $2^{nR}$ independent codewords $x_r^n(w_{b-1})$ , $w_{b-1} \in [1:2^{nR}]$ , each i.i.d. $\sim \prod_{i=1}^n p_{X_r}(x_{r,i})$ .
For each $w_{b-1}$ , generate $2^{nR}$ conditionally independent codewords $x^n(w_b | w_{b-1})$ , each i.i.d. $\sim \prod_{i=1}^n p_{X|X_r}(x_i | x_{r,i}(w_{b-1}))$ .

Encoding

In block $b$ :

The source sends $x^n(w_b | w_{b-1})$ .
The relay, having decoded $w_{b-1}$ at the end of block $b-1$ , sends $x_r^n(w_{b-1})$ .

The source and relay transmit correlated codewords because they share knowledge of $w_{b-1}$ . This correlation is what enables coherent cooperation.

Relay decoding

At the end of block $b$ , the relay knows $w_{b-1}$ (from the previous block) and looks for the unique $\hat{w}_b$ such that $(x^n(\hat{w}_b | w_{b-1}), x_r^n(w_{b-1}), y_r^n(b))$ is jointly typical. By the joint typicality lemma, this succeeds with high probability if $R < I(X; Y_r \mid X_r)$ .

Backward decoding at destination

The destination decodes in reverse order: starting from block $B$ and working back to block $1$ . In block $b$ , knowing $w_b$ (decoded from block $b+1$ ), the destination looks for $\hat{w}_{b-1}$ such that $(x^n(w_b | \hat{w}_{b-1}), x_r^n(\hat{w}_{b-1}), y^n(b))$ is jointly typical. This succeeds if $R < I(X, X_r; Y)$ .

Why backward decoding? The destination needs to know the relay's codeword $x_r^n(w_{b-1})$ to decode block $b$ , but $w_{b-1}$ is the message being decoded! Backward decoding resolves this circularity: we start at the last block (where a known dummy message is sent) and work backwards.

Rate analysis

Both constraints must hold: $R < I(X; Y_r \mid X_r)$ (relay decoding) and $R < I(X, X_r; Y)$ (destination decoding). The rate loss from using $B+1$ blocks to send $B$ messages vanishes as $B \to \infty$ . Optimizing over $p(x, x_r)$ yields the DF achievable rate.

,

Block-Markov Encoding and Backward Decoding

Step-by-step animation of block-Markov encoding: the source sends fresh messages while the relay cooperates on previous-block messages. Shows the backward decoding chain from block

B

to block

1

.

Backward Decoding

A decoding strategy where the destination decodes messages in reverse chronological order, starting from the last block. This resolves the circular dependency in block-Markov encoding where decoding a block requires knowledge of the previous message.

Related: Block-Markov Encoding

Theorem: Capacity of the Degraded Relay Channel

For the degraded relay channel where $X \to (Y_r, X_r) \to Y$ , the capacity is: $C = \max_{p(x, x_r)} \min\bigl\{I(X; Y_r \mid X_r),\; I(X, X_r; Y)\bigr\}.$

Decode-and-forward achieves the cut-set bound, and hence the capacity, for the degraded relay channel.

In the degraded relay channel, the relay has a "better view" of the source than the destination. Since the relay can decode the source message, it loses nothing by doing so. The only question is whether the relay-destination link can support the required rate — and this is exactly what the broadcast cut captures.

Proof

Achievability

The DF rate from Theorem TDecode-and-Forward Achievable Rate is achievable.

Converse

The cut-set bound (Theorem TCut-Set Bound for the Relay Channel) gives $C \leq \max_{p(x,x_r)} \min\{I(X,X_r;Y), I(X;Y,Y_r|X_r)\}$ . For the degraded channel, as shown in Example ECut-Set Bound for the Degraded Relay Channel, $I(X;Y,Y_r|X_r) = I(X;Y_r|X_r)$ , so the cut-set bound becomes $\max_{p(x,x_r)} \min\{I(X,X_r;Y), I(X;Y_r|X_r)\}$ , which matches the DF achievable rate.

,

Example: DF Rate for a Binary Relay Channel

Consider a relay channel with binary alphabets $\mathcal{X} = \mathcal{X}_r = \mathcal{Y} = \mathcal{Y}_r = \{0, 1\}$ . The source-to-relay link is a BSC with crossover probability $p_1 = 0.05$ and the relay-to-destination link (with source cooperation) has effective capacity $I(X, X_r; Y) = 0.8$ bits. Compute the DF achievable rate.

Solution

Source-to-relay link rate

The relay decoding constraint is $R \leq I(X; Y_r | X_r)$ . For a BSC with crossover probability $p_1 = 0.05$ : $I(X; Y_r | X_r) = 1 - h(p_1) = 1 - h(0.05) \approx 1 - 0.286 = 0.714 \text{ bits}.$

Cooperative link rate

The destination decoding constraint is $R \leq I(X, X_r; Y) = 0.8$ bits.

DF achievable rate

The DF rate is the minimum: $R_{\text{DF}} = \min\{0.714, 0.8\} = 0.714 \text{ bits per channel use}.$ The bottleneck is the source-to-relay link. The relay's ability to help is limited by how well it can decode the source message.

Preview: Relay Coding Strategies

Strategy	Relay Operation	Best When	Limitation
Decode-and-Forward	Fully decodes source message, re-encodes	Source-relay link is strong (degraded channel)	Bottlenecked by weakest hop
Compress-and-Forward	Compresses observation via Wyner-Ziv	Relay is noisy but relay-destination link is strong	Requires good relay-destination link
Compute-and-Forward	Decodes linear combination over lattice	Multiple sources, structured codes needed	Requires lattice alignment

Historical Note: Block-Markov Encoding: A Proof Technique Becomes a System Architecture

1979-present

Block-Markov encoding was introduced by Cover and El Gamal in 1979 as a proof technique for the relay channel. The idea of dividing communication into blocks and having the relay cooperate across consecutive blocks was initially viewed as a mathematical device. But this technique has had extraordinary staying power: it reappears in the MAC with feedback (Cover and Leung, 1981), the broadcast channel with common messages, and cooperative communication protocols.

In modern wireless systems, block-Markov encoding maps naturally to frame-based communication: the relay processes each frame and helps with the next frame. The "one block delay" of block-Markov encoding corresponds to the processing latency of a practical relay — a remarkably tight connection between theory and practice.

Common Mistake: DF Is Not Always the Best Strategy

Mistake:

Assuming decode-and-forward is always the best relay strategy because it is "the most natural" or "extracts the most information."

Correction:

DF requires the relay to fully decode the source message, which limits the rate to $I(X; Y_r | X_r)$ — the capacity of the source-to-relay link. When this link is weak (noisy relay), DF performs poorly because the bottleneck is the first hop. In such cases, compress-and-forward (Section 22.4) is superior: the relay does not need to decode; it only compresses its observation, which can help the destination even when the relay's observation is noisy.

Quick Check

In block-Markov encoding for decode-and-forward, why does the source transmit a codeword that depends on both the current message $W_b$ and the previous message $W_{b-1}$ ?

To provide error correction across blocks

So the source and relay can transmit correlated (coherent) codewords, since both know $W_{b-1}$

Because the source does not trust the relay to decode correctly

To increase the codebook size

Correction:

So the source and relay can transmit correlated (coherent) codewords, since both know

W_{b-1}

Correct. Both the source and relay know $W_{b-1}$ — the source because it chose it, the relay because it decoded it in the previous block. By conditioning the source's codeword on $W_{b-1}$ , the source and relay can coordinate their transmissions, achieving coherent cooperation that increases $I(X, X_r; Y)$ .

⚠️Engineering Note

Decode-and-Forward in 5G NR Relay Architectures

In 3GPP standards, DF corresponds to a "Type I" relay (also called a "Layer 3" relay), which fully decodes, re-encodes, and retransmits the data. The relay appears as a separate cell to the destination UE. The main practical challenges are:

Latency: the relay introduces at least one frame of decoding delay.
Error propagation: if the relay decodes incorrectly, it forwards errors.
Half-duplex constraint: practical relays cannot transmit and receive simultaneously, reducing the effective rate by the listen/transmit duty cycle.

Despite these limitations, DF relays are widely deployed for coverage extension in 5G NR, especially in mmWave bands where the direct link is often blocked.

Practical Constraints

•
Relay decoding delay adds latency (at least one subframe)
•
Half-duplex operation typically halves the spectral efficiency
•
Error propagation if relay decodes incorrectly

Decode-and-Forward with Block-Markov Encoding

Complexity: Encoding:

O(n)

per block. Relay decoding:

O(2^{nR} \cdot n)

per block (joint typicality search). Backward decoding:

O(2^{nR} \cdot n)

per block. Total:

O(B \cdot 2^{nR} \cdot n)

.

Input: Messages

W_1, \ldots, W_B

; codebooks

\{x^n(w_b | w_{b-1})\}

,

\{x_r^n(w)\}

Output: Decoded messages

\hat{W}_1, \ldots, \hat{W}_B

// Encoding (source + relay)

Set

W_0 = 1

(known initialization)

for block

b = 1

to

B+1

do

Source transmits

x^n(W_b | W_{b-1})

Relay transmits

x_r^n(\hat{W}_{b-1})

// decoded from previous block

Relay decodes: find

\hat{W}_b

s.t.

(x^n(\hat{W}_b | \hat{W}_{b-1}), x_r^n(\hat{W}_{b-1}), y_r^n) \in \mathcal{T}_\epsilon^{(n)}

end for

// Backward decoding (destination)

Set

\hat{W}_{B+1} = 1

(known termination)