CCapacity Atlas
multiple-access-channel-with-feedback

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

Channel and question

Input
Each encoder chooses \(X_{i,t}\) from its message and common past outputs \(Y^{t-1}\).
Output
A common receiver observes \(Y_t\), which is fed back noiselessly.
Law
A memoryless law \(p(y|x_1,x_2)\).
Quantity
Feedback capacity region \(\mathcal C_{\mathrm{MAC,fb}}\), measured in rate pairs in bits per channel use.

Criterion. Vanishing average joint decoding error.

  • Messages are independent.
  • Feedback is causal, common, and noiseless.

Current status

\[\mathcal R_{\mathrm{CL}}\subseteq\mathcal C_{\mathrm{MAC,fb}}\subseteq\mathcal R_{\mathrm{DB}}\]
ResultRelationMethodYear
Inner Region\(\mathcal R_{\mathrm{CL}}\subseteq\mathcal C\)Block-Markov coding turns past messages into cooperative common information.1981
Outer Region\(\mathcal C\subseteq\mathcal R_{\mathrm{DB}}\)Feedback-created encoder dependence must satisfy a dependence-balance constraint.1989

Research frontier

Determine the capacity region of the general DM-MAC with common output feedback.

Why it remains open. Feedback creates useful correlation between independent encoders, but neither block-Markov inner bounds nor dependence-balance converses are universally tight.

What would count as progress

  • Close the gap for a new explicit finite channel.
  • Strengthen dependence balance without losing computability.
  • Relate external formal proofs to a versioned canonical feedback-code statement.

Lean formalization

Canonical statementNone

Version 1 · Lean. The Ozarow Gaussian special case is exact, but the general finite model remains an external-proof target.

Substantial proofs0 linked

No external Lean proof is registered. Proofs longer than roughly 50 lines or requiring problem-specific infrastructure should live in a dedicated repository and link back to this statement version.

References

  1. Thomas M. Cover and Cyril S. K. Leung (1981). An Achievable Rate Region for the Multiple-Access Channel with Feedback. IEEE Transactions on Information Theory. DOI 10.1109/TIT.1981.1056357.
  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

Thread key: capacityatlas:multiple-access-channel-with-feedback

Find discussionStart discussion

Related problems

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
Open \(\mathcal R_{\mathrm{Shannon,in}}\subseteq\mathcal C_{\mathrm{TWC}}\subseteq\mathcal R_{\mathrm{Shannon,out}}\)
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}}\)
Two-user Gaussian multiple-access channel with feedback

Ozarow's feedback scheme and converse determine the full two-user Gaussian MAC feedback region.

Multiple access Continuous alphabet Gaussian Additive noise Feedback Power constraint Capacity region Exact
Solved \(\bigcup_{0\le\rho\le1}\!\left\{\begin{array}{l}R_1\le\frac12\log_2(1+P_1(1-\rho^2)/N),\\R_2\le\frac12\log_2(1+P_2(1-\rho^2)/N),\\R_1+R_2\le\frac12\log_2(1+(P_1+P_2+2\rho\sqrt{P_1P_2})/N)\end{array}\right\}\)