Feedback in the BC

Can Feedback Help the Broadcast Channel?

We have seen that feedback enlarges the MAC capacity region by enabling encoder cooperation. What about the broadcast channel? Here a single transmitter sends different messages to different receivers. Since there is only one encoder, the "cooperation through feedback" mechanism of the MAC does not directly apply.

Yet feedback does help the BC β€” through a completely different mechanism: retransmission. When the transmitter learns what each receiver has decoded (via feedback), it can retransmit information that one receiver decoded but the other missed. This creates "free" side information: receiver 1's overheard signal becomes useful for receiver 2, and vice versa. The Shayevitz-Wigger scheme exploits this to strictly enlarge the BC capacity region.

Definition:

The Broadcast Channel with Feedback

The broadcast channel with noiseless feedback has:

  • One encoder that maps (W1,W2,Y1iβˆ’1,Y2iβˆ’1)(W_1, W_2, Y_1^{i-1}, Y_2^{i-1}) to XiX_i,
  • Two receivers: receiver kk maps YknY_k^n to W^k\hat{W}_k,
  • Noiseless feedback links from both receivers to the transmitter: after time ii, the encoder observes (Y1,i,Y2,i)(Y_{1,i}, Y_{2,i}).

The encoder knows both receivers' observations, enabling adaptive retransmission.

Broadcast Channel with Feedback

A broadcast channel where the outputs of all receivers are fed back noiselessly to the transmitter, enabling adaptive encoding based on what each receiver has observed.

Related: Retransmission Strategy

Theorem: Feedback Can Enlarge the BC Capacity Region

For certain broadcast channels, feedback from both receivers strictly enlarges the capacity region: CBC-fbβŠ‹CBC.\mathcal{C}_{\text{BC-fb}} \supsetneq \mathcal{C}_{\text{BC}}.

Unlike the MAC case (where the sum-rate always increases for the Gaussian channel), feedback helps the BC only for non-degraded channels where the receivers observe different "views" of the transmitted signal.

In a degraded BC (Y1Y_1 is a degraded version of Y2Y_2 or vice versa), the stronger receiver already decodes everything the weaker receiver needs, so feedback provides no new information. But in a non-degraded BC, the two receivers may decode different parts of the signal. Feedback lets the transmitter learn these different "pieces" and retransmit them, effectively creating a cooperative relay-like mechanism between the receivers (mediated by the transmitter).

Proof
Degraded BC: feedback does not help

For the degraded BC, the capacity region is achieved by superposition coding. Feedback cannot improve it because the weaker receiver's observation is a degraded version of the stronger receiver's β€” no new information is revealed by feedback.

Non-degraded BC: feedback helps via retransmission

Consider a BC where receiver 1 observes Y1=f1(X,Z1)Y_1 = f_1(X, Z_1) and receiver 2 observes Y2=f2(X,Z2)Y_2 = f_2(X, Z_2) with independent noise components. Receiver 1 may decode some information that receiver 2 missed, and vice versa. With feedback, the transmitter can retransmit the "missing" pieces, creating mutual side information.

,

Definition:

Retransmission Strategy for the BC with Feedback

The retransmission strategy for the BC with feedback operates in three phases:

  1. Phase 1 (Fresh transmission): transmit new information W1,W2W_1, W_2 using superposition coding. Both receivers attempt to decode.
  2. Phase 2 (Retransmission for receiver 1): the transmitter re-encodes information that receiver 2 decoded but receiver 1 missed. Receiver 1 uses this to recover the missing piece.
  3. Phase 3 (Retransmission for receiver 2): similarly, retransmit what receiver 1 decoded but receiver 2 missed.

The key insight is that retransmission is "free" from the perspective of the receiver that already has the information β€” it uses the signal as side information to decode its own message at a higher rate.

Retransmission Strategy

A feedback coding strategy for the BC where the transmitter re-encodes information based on feedback about each receiver's decoding status, creating mutual side information.

Related: Broadcast Channel with Feedback

Theorem: The Shayevitz-Wigger Scheme for the Gaussian BC with Feedback

For the Gaussian broadcast channel Y1=X+Z1Y_1 = X + Z_1, Y2=X+Z2Y_2 = X + Z_2 with Zk∼N(0,Nk)Z_k \sim \mathcal{N}(0, N_k) (N1β‰ N2N_1 \neq N_2) and noiseless feedback, the Shayevitz-Wigger scheme achieves a rate region that strictly contains the no-feedback capacity region.

The scheme uses a combination of:

  1. Schalkwijk-Kailath-type iterative refinement for each user,
  2. Dirty-paper coding to manage the known interference from retransmissions,
  3. Block-Markov encoding to coordinate fresh and retransmitted information.

The Shayevitz-Wigger scheme is best understood through the erasure BC analogy. In the binary erasure BC, receiver 1 sees some bits and erases others, and similarly for receiver 2. With feedback, the transmitter XORs a bit that receiver 1 erased (but receiver 2 received) with a bit that receiver 2 erased (but receiver 1 received). This single retransmission is useful to both receivers β€” the "XOR trick." The Gaussian version replaces XOR with linear combinations and uses DPC to handle interference.

Proof
Round 1: Fresh transmission

Transmit Gaussian codewords for both users using superposition coding. From the feedback, the transmitter learns each receiver's estimation error.

Round 2: Correlated retransmission

The transmitter sends a linear combination of the two receivers' estimation errors. Each receiver uses its own estimation error (known from its observation) to cancel its component and decode the other user's error β€” this provides side information that improves its own decoding.

Iterative refinement

Repeat: each round reduces the estimation error at both receivers, and the retransmission of correlated errors provides a multiplexing gain similar to the XOR-based scheme in the erasure BC.

Example: The Erasure BC with Feedback: The XOR Trick

Consider a binary erasure BC where user 1 sees each bit with probability 1βˆ’Ο΅11 - \epsilon_1 (erased with probability Ο΅1\epsilon_1) and user 2 sees each bit with probability 1βˆ’Ο΅21 - \epsilon_2. Without feedback, the capacity region is known. Show that with feedback, the sum-rate can be improved using the XOR trick.

Solution
No-feedback capacity region

Without feedback, the capacity region of the erasure BC is: R1≀1βˆ’Ο΅1R_{1} \leq 1 - \epsilon_1, R2≀1βˆ’Ο΅2R_{2} \leq 1 - \epsilon_2, R1+R2≀1βˆ’Ο΅1Ο΅2R_{1} + R_{2} \leq 1 - \epsilon_1 \epsilon_2 (with time-sharing). The sum-rate is 1βˆ’Ο΅1Ο΅21 - \epsilon_1 \epsilon_2.

The XOR trick

With feedback, the transmitter can identify bits that user 1 received but user 2 erased (call this set AA) and bits that user 2 received but user 1 erased (set BB). For each pair (a,b)∈AΓ—B(a, b) \in A \times B, the transmitter sends aβŠ•ba \oplus b. User 1 (who knows aa) recovers bb, and user 2 (who knows bb) recovers aa. Each XOR transmission serves both users.

Sum-rate with feedback

The fraction of bits in AA is ∼(1βˆ’Ο΅1)Ο΅2\sim (1-\epsilon_1)\epsilon_2 and in BB is ∼ϡ1(1βˆ’Ο΅2)\sim \epsilon_1(1-\epsilon_2). The XOR phase sends min⁑{∣A∣,∣B∣}\min\{|A|, |B|\} useful symbols, each serving both users. The sum-rate with feedback: R1+R2=1βˆ’Ο΅1Ο΅2+min⁑{Ο΅1(1βˆ’Ο΅2),(1βˆ’Ο΅1)Ο΅2}>1βˆ’Ο΅1Ο΅2R_{1} + R_{2} = 1 - \epsilon_1\epsilon_2 + \min\{\epsilon_1(1-\epsilon_2), (1-\epsilon_1)\epsilon_2\} > 1 - \epsilon_1\epsilon_2. Feedback strictly improves the sum-rate.

Erasure BC: Capacity Region With and Without Feedback

Compare the capacity regions of the binary erasure broadcast channel with and without feedback. The XOR trick strictly enlarges the achievable region.

Parameters
0.3
0.5

The XOR Retransmission Trick

Step-by-step animation of the XOR trick for the erasure broadcast channel with feedback. Shows how a single retransmission of bβŠ•cb \oplus c serves both receivers simultaneously, each using its own side information to decode the missing bit.

Common Mistake: Feedback Does Not Help the Degraded BC

Mistake:

Assuming that feedback always helps the broadcast channel because "more information at the encoder is always beneficial."

Correction:

For the degraded BC, feedback does not enlarge the capacity region. The capacity is already achieved by superposition coding, and the stronger receiver's output is a sufficient statistic for the weaker receiver. Feedback only helps non-degraded BC channels where the two receivers observe complementary aspects of the signal.

Historical Note: Dueck's Counterexample and the Power of BC Feedback

1981-2011

The question of whether feedback helps the BC was open for decades. Shannon's result for the point-to-point case (feedback does not help) and El Gamal's result for the degraded BC (feedback does not help) suggested that feedback might be useless for the BC in general. But Dueck (1981) constructed a clever counterexample β€” a non-degraded BC where feedback strictly enlarges the capacity region.

Dueck's example was initially viewed as a curiosity, but the subsequent work by Shayevitz and Wigger (2011) showed that feedback gains are significant even for the practically important Gaussian BC. The retransmission/XOR idea has since influenced the design of HARQ protocols in wireless systems.

Quick Check

In the erasure BC with feedback, the XOR trick sends aβŠ•ba \oplus b where aa was received by user 1 but erased by user 2, and bb was received by user 2 but erased by user 1. Why is this single transmission useful to both users?

Because XOR is a self-inverse operation: each user XORs with its known bit to recover the other

Because the erasure channel preserves XOR operations

Because both users receive the XOR transmission without erasure

Because XOR is a linear code

Correction:
Because XOR is a self-inverse operation: each user XORs with its known bit to recover the other

Correct. User 1 knows aa, so it computes aβŠ•(aβŠ•b)=ba \oplus (a \oplus b) = b. User 2 knows bb, so it computes bβŠ•(aβŠ•b)=ab \oplus (a \oplus b) = a. Each user uses its own received bit as "side information" to decode the bit meant for the other.

πŸ”§Engineering Note

From BC Feedback Theory to HARQ Protocols

The retransmission idea in BC feedback theory has a direct connection to HARQ (Hybrid ARQ) in wireless systems. In 5G NR, when a user fails to decode a packet, it sends a NACK and the base station retransmits. Modern HARQ schemes go further:

  1. HARQ combining (chase combining): the receiver combines the original and retransmitted packets for improved SNR β€” analogous to iterative refinement.
  2. Incremental redundancy: the base station sends additional parity bits, not a full retransmission β€” analogous to the Schalkwijk-Kailath refinement.
  3. Network HARQ: when multiple users experience different erasures, the base station can XOR retransmissions to serve multiple users simultaneously β€” directly inspired by the BC feedback results.

The theoretical sum-rate gain from feedback translates to practical throughput gains of 10-30% in broadcast scenarios with heterogeneous user channels.

Practical Constraints
  • β€’

    Feedback delay limits effectiveness for high-mobility users

  • β€’

    Feedback overhead (NACK/CQI reports) consumes uplink resources

  • β€’

    XOR-based network coding requires careful scheduling

Key Takeaway

Feedback can enlarge the broadcast channel capacity region for non-degraded channels, using retransmission strategies where the transmitter XORs (or linearly combines) information that one receiver decoded but the other missed. Each retransmission serves both receivers simultaneously. For degraded BCs, feedback does not help.

Feedback in the MACTwo-Way Communication