Ferkans — Interactive Telecom Tutor

When Both Parties Want to Talk

In all the channel models we have studied, communication flows in one direction: from encoder to decoder (possibly with feedback assisting the encoder). But in many practical scenarios, two users simultaneously communicate with each other over the same channel. This is the two-way channel, introduced by Shannon in 1961.

The two-way channel is surprisingly tricky: each user's transmission creates interference for the other, but each user also knows its own transmitted signal and can subtract it from the received signal. This self-interference cancellation is automatic and free — the challenge lies in the coding and interaction structure. Can multiple rounds of interaction help? Shannon showed that interaction can indeed improve communication, making this one of the earliest examples of interactive communication protocols.

Definition:
Shannon's Two-Way Channel

A two-way channel consists of:

Two users, each with a message to send to the other: user 1 has $W_1$ for user 2, user 2 has $W_2$ for user 1.
At each time $i$ : user 1 sends $X_{1,i} = f_{1,i}(W_1, Y_1^{i-1})$ and receives $Y_{1,i}$ ; user 2 sends $X_{2,i} = f_{2,i}(W_2, Y_2^{i-1})$ and receives $Y_{2,i}$ .
The channel is described by $p(y_1, y_2 | x_1, x_2)$ .

The capacity region is the set of achievable rate pairs $(R_{1}, R_{2})$ where $R_{k}$ is the rate of user $k$ 's message.

The two-way channel is inherently interactive: each user's encoding at time $i$ depends on its past observations $Y_k^{i-1}$ , which in turn depend on the other user's past transmissions. This creates a feedback-like loop where interaction can improve rates.

Two-Way Channel

A communication channel where two users simultaneously send messages to each other. Each user encodes based on its message and past observations, creating an interactive communication protocol. Introduced by Shannon in 1961.

Related: Interactive Communication

Theorem: Shannon's Inner Bound for the Two-Way Channel

For the two-way channel $p(y_1, y_2 | x_1, x_2)$ , the following rate region is achievable: $\mathcal{R}_{\text{inner}} = \bigcup_{p(x_1) p(x_2)} \left\{(R_{1}, R_{2}): \begin{array}{l} R_{1} \leq I(X_1; Y_2 | X_2) \\ R_{2} \leq I(X_2; Y_1 | X_1) \end{array}\right\}.$

This is the "independent coding" inner bound: each user encodes independently, and each user decodes by subtracting its own known transmission.

User 2 receives $Y_2$ and knows its own input $X_2$ . After conditioning on $X_2$ , the effective channel from user 1 to user 2 is $p(y_2 | x_1, x_2)$ with $X_2$ known. The rate $I(X_1; Y_2 | X_2)$ is exactly the capacity of this point-to-point channel. Similarly for the reverse direction.

The point is that with independent coding, the two-way channel decomposes into two one-way channels, each with known interference. The open question is whether interaction — adapting each user's encoding based on past observations — can do better.

Proof

Independent coding

Each user generates a random codebook $\{x_k^n(w_k)\}$ independently. User $k$ sends $x_k^n(W_k)$ without using any feedback.

Decoding with known interference

User 2 receives $Y_2^n$ and knows $X_2^n$ (its own codeword). It looks for the unique $\hat{w}_1$ such that $(x_1^n(\hat{w}_1), x_2^n(w_2), y_2^n)$ is jointly typical. This succeeds if $R_{1} < I(X_1; Y_2 | X_2)$ . Similarly for user 1.

Definition:
Interactive Communication

In interactive communication, users take turns refining their messages over multiple rounds. In each round, each user transmits a signal that depends on:

Its own message,
All past observations (from previous rounds),
(Optionally) a summary of what it has decoded so far.

Interaction allows each user to adapt its transmission based on what the other user has already sent, potentially achieving higher rates than one-shot (non-interactive) coding.

Formally, an $L$ -round interactive protocol divides the $n$ channel uses into $L$ rounds of $n/L$ uses each. In round $\ell$ , user $k$ encodes based on $(W_k, Y_k^{(\ell-1)n/L})$ .

Interactive Communication

A communication protocol where users adapt their transmissions based on past observations, refining their messages over multiple rounds. Can potentially exceed the rates achievable by non-interactive (one-shot) coding.

Related: Two-Way Channel

Theorem: Outer Bound for the Two-Way Channel

For the two-way channel, the capacity region is contained in: $\mathcal{R}_{\text{outer}} \supseteq \left\{(R_{1}, R_{2}): \begin{array}{l} R_{1} \leq I(X_1; Y_2 | X_2) \\ R_{2} \leq I(X_2; Y_1 | X_1) \end{array}\right\}$ for some joint distribution $p(x_1, x_2)$ (not necessarily product).

When the outer bound with joint distributions strictly exceeds the inner bound with product distributions, interaction can potentially help.

The outer bound allows correlated inputs $(X_1, X_2)$ , which interaction can create. The inner bound restricts to independent inputs. If the gap is nonzero, there is room for interaction to improve rates.

Proof

Standard converse

By Fano's inequality: $nR_{1} \leq I(W_1; Y_2^n) + n\epsilon_n$ . Expanding: $\leq \sum_i I(X_{1,i}; Y_{2,i} | X_{2,i}, Y_2^{i-1}) + n\epsilon_n$ . Since $X_{2,i}$ can depend on $Y_2^{i-1}$ , the effective input distribution $p(x_{1,i}, x_{2,i})$ can be a joint (non-product) distribution. This is why the outer bound allows joint distributions.

Example: The Binary Multiplying Two-Way Channel

Consider the binary multiplying two-way channel: $Y_1 = Y_2 = X_1 \cdot X_2$ (the output is the product of the two binary inputs). With independent coding, each user's rate is zero (since $Y_k$ depends on both inputs but conditioning on one input reveals nothing if that input is random). Show that interaction achieves positive rates.

Solution

Independent coding fails

With independent Bernoulli(1/2) inputs: $Y = X_1 \cdot X_2 = 1$ only when both $X_1 = X_2 = 1$ (probability 1/4). $I(X_1; Y | X_2)$ : when $X_2 = 0$ , $Y = 0$ regardless of $X_1$ , so no information. When $X_2 = 1$ , $Y = X_1$ , giving 1 bit. Average: $\frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 1 = 0.5$ bits. So Shannon's inner bound gives $R_{k} \leq 0.5$ bits.

Interactive protocol

Round 1: User 1 sends $X_1 = W_1$ (its message bit). User 2 sends $X_2 = 1$ . Both observe $Y = W_1$ . Now user 2 knows $W_1$ . Round 2: User 2 sends $X_2 = W_2$ . User 1 sends $X_1 = 1$ . Both observe $Y = W_2$ . Now user 1 knows $W_2$ . Rate: each user sends 1 bit in 2 channel uses, giving $R_{1} = R_{2} = 0.5$ bits.

Comparison

In this case, the interactive protocol achieves the same rate as the independent coding bound (0.5 bits each). The two-way channel capacity for this example is known to be $R_{1} + R_{2} \leq 1$ (achieved by time-sharing). Interaction does not help beyond time-sharing here, but for other channels it can.

Example: The Gaussian Two-Way Channel

For the Gaussian two-way channel $Y_1 = X_2 + Z_1$ , $Y_2 = X_1 + Z_2$ with $Z_k \sim \mathcal{N}(0, N)$ and power constraints $P_1, P_2$ , characterize the capacity region. Does interaction help?

Solution

Shannon's inner bound

With independent coding: $R_{1} \leq \frac{1}{2}\log(1 + P_1/N)$ , $R_{2} \leq \frac{1}{2}\log(1 + P_2/N)$ . This is a rectangle. Each user gets the full point-to-point capacity because self-interference is perfectly canceled ( $Y_2 - \text{known } X_2 = X_1 + Z_2$ ).

Outer bound

The outer bound with joint distributions: since $Y_1 = X_2 + Z_1$ does not depend on $X_1$ at all, $I(X_2; Y_1 | X_1) = I(X_2; X_2 + Z_1) = \frac{1}{2}\log(1+P_2/N)$ . This matches the inner bound!

Conclusion

For the Gaussian two-way channel with additive noise (and no coupling between directions), the capacity region is: $R_{1} \leq \frac{1}{2}\log(1+P_1/N)$ , $R_{2} \leq \frac{1}{2}\log(1+P_2/N)$ . Interaction does not help because the channel decomposes into two independent point-to-point channels. Interaction helps only when the two directions are coupled through the channel.

Historical Note: Shannon's Last Great Open Problem

1961-present

Shannon introduced the two-way channel in 1961, twenty years before the relay channel gained prominence. He established the inner and outer bounds but could not determine the exact capacity region. More than sixty years later, the capacity of the general two-way channel remains unknown — it is one of the oldest open problems in information theory.

What makes the two-way channel so hard is the interaction: the optimal encoding at each time step depends on the past observations, which depend on the other user's past encoding, which depends on their past observations, creating an infinite regress. This is fundamentally different from the one-way channel where the capacity formula involves a single-letter optimization. Whether the capacity of the two-way channel admits a single-letter characterization is itself an open question.

Historical Note: Interactive Communication in Computer Science

1979-1996

The study of interactive communication has deep connections to theoretical computer science. Yao (1979) introduced the concept of communication complexity: how many bits must two parties exchange to compute a joint function of their inputs? This is the two-way channel problem in the noiseless setting.

The noisy version — interactive communication over noisy channels — was studied by Schulman (1996), who showed that interaction can be protected against noise using tree codes. The question of whether interaction helps over noisy channels, and by how much, connects information theory to computational complexity in surprising ways.

Shannon's Two-Way Channel

Animated overview of the two-way channel: two users simultaneously transmit and receive. Shows how the Gaussian additive two-way channel decomposes into two independent point-to-point channels via self-interference cancellation.

Summary: Feedback and Interaction Effects

Channel	Does Feedback/Interaction Help?	Mechanism	Capacity Known?
Point-to-point DMC	No (capacity unchanged)	N/A	Yes (Shannon, 1956)
Point-to-point Gaussian	Capacity unchanged, but reliability improves (doubly exponential error)	Schalkwijk-Kailath iterative refinement	Yes
MAC (general)	Yes — capacity region enlarged	Input correlation via shared observations	Gaussian: Yes (Ozarow, 1984)
BC (degraded)	No	N/A	Yes
BC (non-degraded)	Yes — capacity region enlarged	Retransmission / XOR of missed information	Gaussian: partially (Shayevitz-Wigger)
Two-way channel	Interaction can help for coupled channels	Adaptive encoding based on past observations	Open in general

Two-Way Channel: Inner and Outer Bounds

Visualize the inner bound (independent coding) and outer bound for the Gaussian two-way channel with varying power asymmetry.

Parameters

User 1 Power

P_1

10

User 2 Power

P_2

10

Noise Variance

N

1

Common Mistake: The Two-Way Channel Does Not Always Decompose

Mistake:

Assuming that the two-way channel always decomposes into two independent one-way channels because each user knows its own input.

Correction:

The Gaussian additive two-way channel does decompose because $Y_1 = X_2 + Z_1$ does not depend on $X_1$ . But for general two-way channels where $p(y_1, y_2 | x_1, x_2)$ couples the two directions (e.g., $Y_1 = f(X_1, X_2, Z)$ ), the channel does not decompose. In such channels, interaction can create correlation between the inputs that improves rates beyond independent coding. The binary multiplying channel is an example where the outputs are coupled.

Quick Check

Shannon's two-way channel has been open for over 60 years. What makes the two-way channel fundamentally harder than one-way channels?

The encoding functions are more complex

The interaction creates dependencies between time steps that prevent single-letter characterization

There is no known converse technique for two-way channels

Two-way channels require quantum information theory

Correction:

The interaction creates dependencies between time steps that prevent single-letter characterization

Correct. In one-way channels, the capacity is characterized by a single-letter formula $\max_{p(x)} I(X; Y)$ — a one-dimensional optimization. In the two-way channel, the encoding at time $i$ depends on all past observations, which depend on all past encodings by both users. This creates a complex dependency structure that resists reduction to a single-letter formula.

Why This Matters: Two-Way Channels and Full-Duplex Wireless

The two-way channel is the information-theoretic model for full-duplex wireless communication, where two devices transmit and receive simultaneously on the same frequency band. Full-duplex is a major research direction in 5G and 6G, promising to double spectral efficiency compared to half-duplex (TDD/FDD).

The main practical challenge — self-interference cancellation — maps directly to the "known interference" structure of the two-way channel: each device knows its own transmitted signal and can (in principle) subtract it from the received signal. The information-theoretic results show that perfect self-interference cancellation allows both directions to achieve full point-to-point capacity simultaneously.

See Book telecom, Ch. 22 for full-duplex wireless system design.

Key Takeaway

The two-way channel models simultaneous bidirectional communication. With independent coding and known-interference cancellation, each direction achieves point-to-point capacity for channels that decouple (like Gaussian additive). For coupled channels, interaction may help, but the general capacity region remains one of the oldest open problems in information theory.

Two-Way Communication

When Both Parties Want to Talk

Definition: Shannon's Two-Way Channel

Two-Way Channel

Theorem: Shannon's Inner Bound for the Two-Way Channel

Independent coding

Decoding with known interference

Definition: Interactive Communication

Interactive Communication

Theorem: Outer Bound for the Two-Way Channel

Standard converse

Example: The Binary Multiplying Two-Way Channel

Independent coding fails

Interactive protocol

Comparison

Example: The Gaussian Two-Way Channel

Shannon's inner bound

Outer bound

Conclusion

Historical Note: Shannon's Last Great Open Problem

Historical Note: Interactive Communication in Computer Science

Shannon's Two-Way Channel

Summary: Feedback and Interaction Effects

Two-Way Channel: Inner and Outer Bounds

Parameters

Common Mistake: The Two-Way Channel Does Not Always Decompose

Quick Check

Why This Matters: Two-Way Channels and Full-Duplex Wireless

Key Takeaway

Definition:
Shannon's Two-Way Channel

Definition:
Interactive Communication