CCapacity Atlas
discrete-memoryless-two-way-channel

Discrete memoryless two-way channel

Two terminals exchange messages while adapting each input to their own past observations.

Two-way Finite alphabet Discrete memoryless Feedback Capacity region Bounds only

Channel and question

Input
Terminal i chooses \(X_{i,t}\) from its message and past observations.
Output
Terminals receive \(Y_{1,t}\) and \(Y_{2,t}\).
Law
A memoryless law \(p(y_1,y_2|x_1,x_2)\).
Quantity
Capacity region \(\mathcal C_{\mathrm{TWC}}\), measured in rate pairs in bits per channel use.

Criterion. Vanishing average error in both directions.

  • Encoding is interactive and causal.
  • Messages are independent.

Current status

\[\mathcal R_{\mathrm{Shannon,in}}\subseteq\mathcal C_{\mathrm{TWC}}\subseteq\mathcal R_{\mathrm{Shannon,out}}\]

The bounds coincide for several symmetric or decomposable channels.

Known results and bounds for Discrete memoryless two-way channel
ResultRelationMethodYear
Inner Region\(\mathcal R_{\mathrm{in}}\subseteq\mathcal C\)Independent stationary inputs without adaptation.1961
Outer Region\(\mathcal C\subseteq\mathcal R_{\mathrm{out}}\)Allow arbitrary correlated inputs in a cut-style single-letter outer bound.1961

Open question

Determine when interaction enlarges the two-way capacity region and characterize the general region.

The terminals create input dependence dynamically through noisy observations, which is difficult to summarize by a single-letter distribution.

Research directions

  • Find a sharper dependence-aware converse.
  • Close an explicit channel where Shannon's bounds differ.

Formal verification

Lean coverageFormally stated

Concrete operational definitions and admitted research statements are present. Existing proofs are preserved. New statements require mathematical review and proof completion.

Claims

  • Shannon's fixed nonadaptive inner region and adaptive outer region.
    shannon-inner-outer · capacity bounds · solved · Formally stated · v1
  • Independently tracked shannon achievability.
    shannon-achievability · achievability · solved · Formally stated · v1
  • Independently tracked shannon converse.
    shannon-converse · converse · solved · Formally stated · v1
Lean declarations (3)

References

  1. Claude E. Shannon (1961). Two-Way Communication Channels. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability.
  2. Andries P. Hekstra and Frans M. J. Willems (1989). Dependence Balance Bounds for Single-Output Two-Way Channels. IEEE Transactions on Information Theory. DOI 10.1109/18.42175.
  3. Abbas El Gamal and Young-Han Kim (2011). Network Information Theory. Cambridge University Press. DOI 10.1017/CBO9781139030687.

Discussion

Find discussionStart discussion

Related problems

Binary skew-symmetric broadcast channel BSSC

The capacity region of this binary-input broadcast channel remains unknown.

Broadcast Finite alphabet Discrete memoryless Binary Asymmetric Capacity region Bounds only
Open \(\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C_{\mathrm{BSSC}}\subseteq\mathcal R_{\mathrm{UV}}\)
Discrete memoryless multiple-access channel with feedback

Common noiseless output feedback lets distributed encoders cooperate, but the general capacity region is unknown.

Multiple access Finite alphabet Discrete memoryless Feedback Capacity region Bounds only
Open \(\mathcal R_{\mathrm{CL}}\subseteq\mathcal C_{\mathrm{MAC,fb}}\subseteq\mathcal R_{\mathrm{DB}}\)
General two-receiver discrete memoryless broadcast channel

The capacity region for two arbitrary broadcast receivers remains unknown outside important ordered subclasses.

Broadcast Finite alphabet Discrete memoryless Capacity region Bounds only
Open \(\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C_{\mathrm{BC}}\subseteq\mathcal R_{\mathrm{UV}}\)
General two-user discrete memoryless interference channel

Two transmitter-receiver pairs interfere, and the exact capacity region is unknown in general.

Interference Finite alphabet Discrete memoryless Capacity region Bounds only
Open \(\mathcal R_{\mathrm{HK}}\subseteq\mathcal C_{\mathrm{IC}}\subseteq\mathcal R_{\mathrm{outer}}\)