Ferkans — Interactive Telecom Tutor

Feedback in Point-to-Point vs. Multiuser Channels

One of the cleanest results in information theory is Shannon's feedback theorem: for a point-to-point DMC, feedback does not increase capacity. The encoder can adapt to past channel outputs, but this adaptation cannot push the rate beyond $\max_{p(x)} I(X; Y)$ . The proof is elegant — a single application of the chain rule and the memoryless property.

For multiuser channels, the situation is fundamentally different. In the MAC, feedback from the receiver to both transmitters allows the transmitters to cooperate — not by sharing messages directly, but by adapting their transmissions based on what the receiver has seen. This cooperation can enlarge the capacity region. The MAC with feedback is one of the most beautiful examples of how interaction creates capabilities that no amount of individual optimization can achieve.

Definition:
The MAC with Noiseless Feedback

The two-user MAC with noiseless feedback has:

Two encoders: encoder $k$ maps $(W_k, Y^{i-1})$ to $X_{k,i}$ for $k = 1, 2$ ,
A decoder that maps $Y^n$ to $(\hat{W}_1, \hat{W}_2)$ ,
A noiseless feedback link from the receiver to both transmitters: after time $i$ , both encoders observe $Y_i$ .

The key difference from the no-feedback MAC: each encoder's input at time $i$ can depend on the entire past output sequence $Y^{i-1}$ , not just its own message. This allows the encoders to implicitly coordinate their transmissions.

,

MAC with Feedback

A multiple-access channel where the receiver's output is fed back noiselessly to all transmitters, enabling them to adapt their inputs based on past channel outputs and thereby implicitly cooperate.

Related: Cover-Leung Inner Bound

Theorem: Feedback Enlarges the MAC Capacity Region

For the two-user MAC with noiseless feedback, the capacity region $\mathcal{C}_{\text{MAC-fb}}$ can be strictly larger than the no-feedback capacity region $\mathcal{C}_{\text{MAC}}$ .

Specifically, the no-feedback MAC capacity region is: $\mathcal{C}_{\text{MAC}} = \left\{(R_{1}, R_{2}): \begin{array}{l} R_{1} \leq I(X_1; Y | X_2) \\ R_{2} \leq I(X_2; Y | X_1) \\ R_{1} + R_{2} \leq I(X_1, X_2; Y) \end{array}\right\}$ for some product distribution $p(x_1) p(x_2)$ .

With feedback, the input distributions need not be independent: the encoders can coordinate their inputs based on past outputs, effectively introducing correlation. This coordination enlarges the region.

Without feedback, the two encoders act independently — they cannot coordinate because they share no common information. With feedback, both encoders observe $Y^{i-1}$ , which becomes common randomness. Using this shared observation, the encoders can correlate their inputs, achieving rate pairs outside the no-feedback region.

The point is that feedback creates a "virtual conference" between the encoders: not by allowing them to talk to each other directly, but by giving them a shared view of the channel output.

Proof

No-feedback region is a pentagon

With independent inputs, the MAC capacity region is the convex hull of $(R_{1}, R_{2})$ satisfying the three constraints above, forming a pentagon.

Feedback enables input correlation

With feedback, at time $i$ , encoder $k$ chooses $X_{k,i} = f_{k,i}(W_k, Y^{i-1})$ . Since both encoders observe the same $Y^{i-1}$ , their inputs can be correlated even though they have different messages. This correlation is impossible without feedback.

Strict enlargement

The sum-rate constraint $R_{1} + R_{2} \leq I(X_1, X_2; Y)$ with correlated $(X_1, X_2)$ can exceed $\max_{p(x_1)p(x_2)} I(X_1, X_2; Y)$ . For specific channels (e.g., the binary erasure MAC), this strict enlargement can be demonstrated explicitly.

,

Theorem: The Cover-Leung Inner Bound

For the two-user MAC with noiseless feedback, the following rate region is achievable: $\mathcal{R}_{\text{CL}} = \bigcup_{p(u) p(x_1|u) p(x_2|u)} \left\{(R_{1}, R_{2}): \begin{array}{l} R_{1} \leq I(X_1; Y | X_2, U) \\ R_{2} \leq I(X_2; Y | X_1, U) \\ R_{1} + R_{2} \leq I(X_1, X_2; Y | U) \end{array}\right\}$ where $U$ is an auxiliary random variable that represents the common part extracted from the feedback, with $|\mathcal{U}| \leq |\mathcal{X}_1| \cdot |\mathcal{X}_2| + 2$ .

The auxiliary variable $U$ captures the common information that both encoders extract from the feedback. Given $U$ , the encoders still act "independently" (the conditional distributions $p(x_1|u)$ and $p(x_2|u)$ are independent), but $U$ allows them to coordinate their transmission strategies. This is like a team meeting where everyone agrees on a plan ( $U$ ) and then acts independently — but the plan itself is informed by the shared observations.

Proof

Block-Markov encoding with common message

Divide communication into $B$ blocks. In each block, the encoders transmit a common codeword $u^n$ (agreed upon from the feedback of the previous block) and their individual fresh codewords $x_1^n(w_1 | u)$ , $x_2^n(w_2 | u)$ .

Feedback-based common message generation

At the end of block $b$ , both encoders observe $Y^n(b)$ and use it to agree on a common index for block $b+1$ . This is possible because both observe the same sequence, so they can independently compute the same function of $Y^n$ .

Decoding

The decoder uses backward decoding (as in the relay channel): knowing the common message $U$ for block $b+1$ , it decodes $(W_1, W_2)$ for block $b$ . The rate constraints follow from joint typicality decoding with $(X_1, X_2, U, Y)$ .

,

Cover-Leung Inner Bound

An achievable rate region for the MAC with feedback that uses block-Markov encoding with a common auxiliary codeword extracted from feedback observations. Strictly enlarges the no-feedback MAC region for many channels.

Related: MAC with Feedback

Historical Note: Cover and Leung: Feedback Creates Cooperation

1981

Thomas Cover and Cosma Leung published their celebrated paper on the MAC with feedback in 1981. The result was surprising: while Shannon had shown in 1956 that feedback does not help for point-to-point channels, Cover and Leung demonstrated that the multiuser setting is qualitatively different. Feedback allows the encoders to cooperate without a direct conference link, using the channel output as a shared resource.

The Cover-Leung scheme uses the same block-Markov encoding technique that Cover and El Gamal had introduced for the relay channel just two years earlier (1979). This connection — block-Markov encoding as a universal tool for cooperation — is one of the most elegant recurring themes in network information theory.

Theorem: Capacity of the Gaussian MAC with Feedback (Ozarow)

For the two-user Gaussian MAC $Y = X_1 + X_2 + Z$ with $Z \sim \mathcal{N}(0, N)$ , power constraints $P_1, P_2$ , and noiseless feedback, the capacity region is: $\mathcal{C}_{\text{G-MAC-fb}} = \left\{(R_{1}, R_{2}): \begin{array}{l} R_{1} \leq \frac{1}{2}\log(1 + P_1(1 - \rho^2)/N) \\ R_{2} \leq \frac{1}{2}\log(1 + P_2(1 - \rho^2)/N) \\ R_{1} + R_{2} \leq \frac{1}{2}\log(1 + (P_1 + P_2 + 2\rho\sqrt{P_1 P_2})/N) \end{array}\right\}$ where $\rho \in [-1, 1]$ is the correlation coefficient between $X_1$ and $X_2$ induced by feedback.

Feedback allows the encoders to correlate their inputs: $\rho \neq 0$ . The individual rate constraints decrease with $|\rho|$ (correlation uses up some of the "fresh information" budget), but the sum-rate constraint increases with $|\rho|$ due to coherent combining gain: $(P_1 + P_2 + 2\rho\sqrt{P_1 P_2})/N > (P_1 + P_2)/N$ for $\rho > 0$ .

The point is that the feedback-induced correlation trades individual rates for sum-rate gain. The capacity region is the union over all $\rho \in [-1, 1]$ — a strict enlargement of the no-feedback region (which requires $\rho = 0$ ).

Proof

Achievability via Schalkwijk-Kailath extension

Ozarow's achievability extends the Schalkwijk-Kailath scheme to two users. In each round, both encoders transmit a linear function of the receiver's estimation error for their respective messages. The correlation $\rho$ arises because both encoders observe the same feedback signal $Y$ and use it to compute correlated updates.

Converse

The converse uses the entropy power inequality and the fact that Gaussian inputs maximize mutual information under power constraints. The key step is showing that the correlation $\rho$ between the inputs is constrained by the feedback mechanism: the inputs can only be correlated through the shared observation of $Y$ .

Example: Feedback Gain for the Symmetric Gaussian MAC

For the symmetric Gaussian MAC with $P_1 = P_2 = P = 10$ and $N = 1$ : (a) Compute the sum-rate capacity without feedback. (b) Compute the maximum sum-rate with feedback (optimize over $\rho$ ). (c) Quantify the feedback gain.

Solution

(a) Sum-rate without feedback

$R_{1} + R_{2} \leq \frac{1}{2}\log(1 + 2P/N) = \frac{1}{2}\log(21) \approx 2.18$ bits.

(b) Sum-rate with feedback

With $\rho = 1$ (maximum correlation): $R_{1} + R_{2} \leq \frac{1}{2}\log(1 + (P + P + 2P)/N) = \frac{1}{2}\log(1 + 4P) = \frac{1}{2}\log(41) \approx 2.68$ bits. But individual rates must satisfy $R_{k} \leq \frac{1}{2}\log(1 + P(1-1)/N) = 0$ at $\rho = 1$ . So $\rho = 1$ is not useful — both users have zero individual rate! Optimal $\rho^*$ satisfies: maximize sum-rate subject to $R_{k} > 0$ . At $\rho^* \approx 0.5$ : sum-rate $\approx \frac{1}{2}\log(1 + 30/1) = \frac{1}{2}\log(31) \approx 2.48$ bits.

(c) Feedback gain

Sum-rate gain: $2.48 - 2.18 = 0.30$ bits (about 14% improvement). The feedback gain for the Gaussian MAC is moderate in sum-rate but can be significant in enlarging the region — allowing rate pairs that are impossible without feedback.

Gaussian MAC Capacity Region: With and Without Feedback

Compare the MAC capacity regions with and without feedback. The feedback region is strictly larger, especially away from the sum-rate face.

Parameters

User 1 Power

P_1

10

User 2 Power

P_2

10

Noise Variance

N

1

MAC Capacity Region: Feedback Enlargement

Animated visualization of how feedback enlarges the Gaussian MAC capacity region. The no-feedback pentagon grows as feedback enables input correlation between the two encoders, achieving the full beamforming sum-rate gain.

Common Mistake: Feedback Helps Multiuser but Not Point-to-Point

Mistake:

Expecting feedback to increase the capacity of a point-to-point DMC because it "gives the encoder more information."

Correction:

Shannon proved that feedback does not increase point-to-point DMC capacity: $C_{\text{fb}} = C$ for any DMC. The proof follows because the mutual information $I(X_i; Y_i | Y^{i-1})$ is maximized by the same distribution regardless of the encoding function. The key difference in multiuser channels is that feedback creates common information between encoders that were previously independent — this has no analogue in the single-user case.

Common Mistake: Feedback Does Not Increase Capacity but Improves Reliability

Mistake:

Concluding that feedback is useless for point-to-point channels because it does not increase capacity.

Correction:

While feedback does not increase point-to-point DMC capacity, it dramatically improves reliability. The Schalkwijk-Kailath scheme for the Gaussian channel achieves doubly exponential error decay: $P_e \sim 2^{-2^{cn}}$ with feedback, versus the ordinary exponential $P_e \sim 2^{-nE(R)}$ without. Feedback also simplifies the encoder (no need for long random codebooks) and enables variable-length coding that adapts to channel conditions.

Quick Check

For the MAC with feedback, feedback allows the encoders to correlate their inputs. How is this correlation created?

The encoders directly share their messages through the feedback link

Both encoders observe the same channel output $Y^{i-1}$ and use it as common randomness to coordinate their inputs

The receiver instructs the encoders how to correlate their signals

The encoders use a pre-shared random codebook

Correction:

Both encoders observe the same channel output

Y^{i-1}

and use it as common randomness to coordinate their inputs

Correct. Both encoders receive the same feedback signal $Y^{i-1}$ . By choosing their encoding functions $X_{k,i} = f_{k,i}(W_k, Y^{i-1})$ appropriately, the encoders can create correlation between $X_1$ and $X_2$ through the shared observation $Y^{i-1}$ , without directly communicating their messages.

Definition:
Kramer-Gastpar Sum-Rate Result

Kramer and Gastpar showed that for the Gaussian MAC with feedback, the sum-rate capacity satisfies: $R_{1} + R_{2} \leq \frac{1}{2}\log\!\left(1 + \frac{(\sqrt{P_1} + \sqrt{P_2})^2}{N}\right)$ with equality achieved by a generalized Schalkwijk-Kailath scheme.

This sum-rate is strictly larger than the no-feedback sum-rate $\frac{1}{2}\log(1 + (P_1 + P_2)/N)$ when $P_1, P_2 > 0$ . The gain is the coherent combining gain from feedback-induced correlation.

The sum-rate with feedback equals the capacity of a point-to-point channel with total power $(\sqrt{P_1} + \sqrt{P_2})^2$ . Feedback effectively turns the MAC into a beamforming system where both users coherently add their signals.

🎓CommIT Contribution(2003)

Feedback and Cooperation in Wireless Networks

G. Caire, S. Shamai (Shitz) — IEEE Transactions on Information Theory

Caire and Shamai's work on the MIMO broadcast channel established that dirty-paper coding (DPC) achieves the capacity region. This result is deeply connected to feedback: DPC at the transmitter achieves the same performance as if the receivers had perfect feedback to the transmitter and could cooperate. The "duality" between DPC and feedback cooperation has been a recurring theme in CommIT's work on multiuser MIMO systems, where practical feedback mechanisms (limited CSI feedback, HARQ) approximate the theoretical gains predicted by the full-feedback capacity results.

feedbackbroadcast-channelDPCMIMOView Paper →

⚠️Engineering Note

Feedback in Practical MAC Systems

In wireless systems, limited feedback from the base station to mobile users is standard (e.g., ACK/NACK, CQI reports in LTE/5G). While this is far from the noiseless full-output feedback assumed in theory, even limited feedback provides significant gains:

Rate adaptation: users adjust their rates based on channel quality reports.
Power control: users adjust power based on interference levels.
HARQ: retransmission requests use feedback to achieve reliability gains similar to the Schalkwijk-Kailath effect.

The Cover-Leung cooperation gain (input correlation via feedback) is harder to realize in practice because it requires both users to receive the same feedback signal simultaneously and to implement coordinated encoding.

Practical Constraints

•
Feedback delay limits the correlation gain for fast-fading channels
•
Feedback quantization reduces the common information available to encoders
•
Uplink feedback from BS to users consumes downlink resources

Key Takeaway

Feedback enlarges the MAC capacity region by enabling input correlation through shared channel observations. For the Gaussian MAC, feedback achieves a sum-rate of $\frac{1}{2}\log(1 + (\sqrt{P_1}+\sqrt{P_2})^2/N)$ — the coherent combining gain that is impossible without coordination. This is a qualitative departure from the point-to-point case, where feedback does not help.

Schalkwijk-Kailath Scheme

A feedback coding scheme for the Gaussian channel that achieves doubly exponential error probability decay. The encoder iteratively refines its estimate of the message by transmitting the MMSE estimation error, enabled by feedback of the channel output.

Related: MAC with Feedback

Feedback in the MAC

Feedback in Point-to-Point vs. Multiuser Channels

Definition: The MAC with Noiseless Feedback

MAC with Feedback

Theorem: Feedback Enlarges the MAC Capacity Region

No-feedback region is a pentagon

Feedback enables input correlation

Strict enlargement

Theorem: The Cover-Leung Inner Bound

Block-Markov encoding with common message

Feedback-based common message generation

Decoding

Cover-Leung Inner Bound

Historical Note: Cover and Leung: Feedback Creates Cooperation

Theorem: Capacity of the Gaussian MAC with Feedback (Ozarow)

Achievability via Schalkwijk-Kailath extension

Converse

Example: Feedback Gain for the Symmetric Gaussian MAC

(a) Sum-rate without feedback

(b) Sum-rate with feedback

(c) Feedback gain

Gaussian MAC Capacity Region: With and Without Feedback

Parameters

MAC Capacity Region: Feedback Enlargement

Common Mistake: Feedback Helps Multiuser but Not Point-to-Point

Common Mistake: Feedback Does Not Increase Capacity but Improves Reliability

Quick Check

Definition: Kramer-Gastpar Sum-Rate Result

Feedback and Cooperation in Wireless Networks

Feedback in Practical MAC Systems

Key Takeaway

Schalkwijk-Kailath Scheme

Definition:
The MAC with Noiseless Feedback

Definition:
Kramer-Gastpar Sum-Rate Result