CCapacity Atlas
two-user-discrete-memoryless-mac

Two-user discrete memoryless multiple-access channel

Two independent senders communicate to one receiver through a finite memoryless channel.

Multiple access Finite alphabet Discrete memoryless Capacity region Exact Single-letter characterization

Channel and question

Input
Separate deterministic encoders map independent uniform messages to words over finite nonempty alphabets \(\mathcal X_1\) and \(\mathcal X_2\).
Output
One receiver observes a word over a finite nonempty alphabet \(\mathcal Y\) and jointly decodes both messages.
Law
The length-n transition probability is \(\prod_{i=1}^n W(y_i\mid x_{1i},x_{2i})\).
Quantity
Capacity region \(\mathcal C_{\mathrm{MAC}}\), measured in rate pairs in bits per channel use.

Criterion. Nonnegative rate pairs supported at every sufficiently large blocklength with arbitrarily small average joint decoding error and arbitrarily small rate slack.

  • Each encoder depends only on its own message; there is no feedback or message sharing.
  • Blocklengths and any deterministic time-sharing schedule are fixed as part of the code.
  • There are no input-cost constraints.

Current status

\[\bigcup_{p(q)p(x_1|q)p(x_2|q)}\!\left\{\begin{array}{l}R_1,R_2\ge0,\\R_1\le I(X_1;Y|X_2,Q),\\R_2\le I(X_2;Y|X_1,Q),\\R_1+R_2\le I(X_1,X_2;Y|Q)\end{array}\right\}\]

Q ranges over finite time-sharing alphabets. Ahlswede's Theorem 1 (page 33) gives the equivalent closed convex hull of successive-decoding corner rates. The cited proceedings were published in 1973 following the September 1971 conference; the bound dates below identify that verified publication.

Known results and bounds for Two-user discrete memoryless multiple-access channel
ResultRelationMethodYear
Inner Region\(R_1,R_2\ge0,\ R_1\le I(X_1;Y|X_2,Q),\ R_2\le I(X_2;Y|X_1,Q),\ R_1+R_2\le I(X_1,X_2;Y|Q)\)Independent random codebooks, successive decoding of corner rates, and time sharing; Ahlswede's Theorem 1, pages 33–38.1973
Outer Region\(R_1,R_2\ge0,\ R_1\le I(X_1;Y|X_2,Q),\ R_2\le I(X_2;Y|X_1,Q),\ R_1+R_2\le I(X_1,X_2;Y|Q)\)Fano's inequality and memoryless information bounds with a common time coordinate; Ahlswede's Theorem 1, pages 33–38.1973

Formal verification

Lean coverageFormally stated

The local proof uses separate random codebooks and a fixed time-sharing schedule. Three Fano bounds share one time coordinate; compactness handles boundary rates. The region allows arbitrary finite Q.

Claims

  • The complete average-error capacity region with separate deterministic encoders equals the three single-letter inequalities over arbitrary finite time sharing, including boundary rates and zero-rate axes.
    exact-capacity · exact capacity · solved · Formally proved · v1
Lean declarations (4)
Linked proofs (1)
  • exact-capacity · complete · claim v1
    TomasOrtega/CapacityAtlasMAC@ec5be554 · CapacityAtlasMAC.capacityCertificate
    Historical upstream certificate imported into this repository. Pins Atlas commit f1ffd9d31dfa462010be6a95ab79bfd2f911ca76. The upstream audit checks every external proof declaration and full canonical-proposition correspondence with rigid universes; negative controls reject a different proposition and a universe-restricted certificate.

References

  1. Rudolf Ahlswede (1973). Multi-way communication channels. Proceedings of the Second International Symposium on Information Theory (September 1971), Akadémiai Kiadó, pp. 23–52.
  2. Henry Herng-Jiunn Liao (1972). Multiple Access Channels. PhD thesis, University of Hawaii.
  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

Blackwell deterministic broadcast channel

The three-input Blackwell channel is a concrete nondegraded deterministic broadcast channel with an exact entropy capacity region.

Broadcast Finite alphabet Discrete memoryless Asymmetric Capacity region Exact Single-letter characterization
Solved \(R_1\le H(Y_1),\quad R_2\le H(Y_2),\quad R_1+R_2\le H(Y_1,Y_2)\)
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}}\)
Index coding with at most five messages

The capacity regions of all 9,846 nonisomorphic index-coding instances with at most five messages are covered by a finite classification.

Index coding Finite alphabet Multiple unicast Side information Capacity region Exact Single-letter characterization
Solved \(\mathcal C(G)=\mathcal R_{\mathrm{composite}}(G)\quad\text{for }|V(G)|\le5\)
Less-noisy two-receiver broadcast channel

A less-noisy ordering compares every finite stochastic prefix and yields the exact superposition-coding capacity region.

Broadcast Finite alphabet Discrete memoryless Capacity region Exact Single-letter characterization
Solved \(\mathcal C_{\mathrm{LN}}=\bigcup_{P_U P_{X|U}}\{R_1\le I(X;Y_1\mid U),\ R_2\le I(U;Y_2)\}\)