Capacity Atlas Channel-capacity problems
Point-to-point

q-ary symmetric channel

The transmitted q-ary symbol is correct with probability 1-p and otherwise changes uniformly to one of the other symbols.

Solved Lean: not started q-SC
01 · Model

Channel specification

Input

\(X\in\{1,\ldots,q\}\)

Output

\(Y\in\{1,\ldots,q\}\)

Law

\(P(Y=X)=1-p\); conditioned on an error, each of the \(q-1\) other symbols is equally likely.

Parameters

SymbolMeaningRange
\(q\) Alphabet size. \(q\ge2\)
\(p\) Total crossover probability. \(0\le p\le(q-1)/q\)

Assumptions

  • Channel uses are independent.
  • The displayed parameter range uses the usual monotone-noise convention.
02 · Capacity

Shannon capacity

bits per channel use exact
\[C_q(p)=\log_2 q-h_2(p)-p\log_2(q-1)\]

Conditions. \(q\ge2\) and \(0\le p\le(q-1)/q\).

The uniform input distribution achieves capacity by channel symmetry.

Symbol
\(C_q(p)\)
Error criterion
Average-error capacity.
03 · Evidence

Known bounds and characterizations

TypeClaimMethodSource
lower \(C_q(p)\ge\log_2 q-h_2(p)-p\log_2(q-1)\) Uniform input and the discrete-memoryless coding theorem. 1948 [1] [2]
upper \(C_q(p)\le\log_2 q-h_2(p)-p\log_2(q-1)\) Capacity formula for weakly symmetric channels. 1948 [1] [2]
05 · Lean

Formalization status

Lean: not started

Not started

A generic finite weakly symmetric channel and its capacity theorem are planned after the finite entropy layer.

  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. Claude E. Shannon (1948). A Mathematical Theory of Communication. Bell System Technical Journal. doi:10.1002/j.1538-7305.1948.tb01338.x
  2. 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