Capacity Atlas Channel-capacity problems
Multi-user

Two-user discrete memoryless multiple-access channel

Two independent senders communicate to one receiver through a memoryless channel, yielding a polymatroidal capacity region.

Solved Lean: not started DM-MAC
01 · Model

Channel specification

Input

Independent encoder inputs \(X_1\in\mathcal X_1\) and \(X_2\in\mathcal X_2\).

Output

A common receiver observes \(Y\in\mathcal Y\).

Law

A memoryless transition law \(p(y\mid x_1,x_2)\).

Assumptions

  • The two messages are independent.
  • Time sharing is allowed.
02 · Capacity

Capacity region

rate pairs in bits per channel use region
\[\bigcup_{p(q)p(x_1\mid q)p(x_2\mid q)}\!\left\{\begin{array}{l}R_1\le I(X_1;Y\mid X_2,Q),\\R_2\le I(X_2;Y\mid X_1,Q),\\R_1+R_2\le I(X_1,X_2;Y\mid Q)\end{array}\right\}\]

The auxiliary Q represents time sharing.

Symbol
\(\mathcal C_{\mathrm{MAC}}\)
Error criterion
Vanishing average joint decoding error.
03 · Evidence

Known bounds and characterizations

TypeClaimMethodSource
inner region \(R_1\le I(X_1;Y\mid X_2,Q), R_2\le I(X_2;Y\mid X_1,Q), R_1+R_2\le I(X_1,X_2;Y\mid Q)\) Independent random codebooks and joint decoding. 1971 [1] [2]
outer region \(R_1\le I(X_1;Y\mid X_2,Q), R_2\le I(X_2;Y\mid X_1,Q), R_1+R_2\le I(X_1,X_2;Y\mid Q)\) Fano's inequality and single-letterization with a time-sharing variable. 1972 [1] [2]
04 · History

Bound timeline

  1. 1971

    Ahlswede established the multiple-access coding theorem.

    Reference
  2. 1972

    Liao independently developed the multiple-access capacity region.

    Reference
05 · Lean

Formalization status

Lean: not started

Not started

Product input distributions, rate regions, and the MAC coding theorem are not yet formalized.

  1. Definitions
  2. Statement
  3. Partial proof
  4. Complete proof

No Lean file is linked yet. A contribution should begin by reusing the shared definitions under lean/CapacityAtlas.

References

Primary sources

  1. Rudolf Ahlswede (1971). Multi-way communication channels. Second International Symposium on Information Theory.
  2. Hsiao-Hwa Liao (1972). Multiple Access Channels. PhD thesis, University of Hawaii.
  3. Thomas M. Cover and Joy A. Thomas (2006). Elements of Information Theory. Wiley, second edition. doi:10.1002/047174882X
Keep exploring

Related entries

Point-to-point Updated 2026-08-09

Binary symmetric channel

Solved Lean: definitions

Each bit is independently flipped with probability p. This is the canonical finite noisy channel.

2 bounds Open entry
Point-to-point Updated 2026-08-09

Binary erasure channel

Solved Lean: definitions

Each transmitted bit is either received correctly or replaced by a visible erasure symbol.

2 bounds Open entry