CCapacity Atlas
noiseless-q-ary-channel

Noiseless finite-alphabet channel

A q-symbol input is reproduced exactly, providing the basic normalization for channel capacity.

Point-to-point q-ary Finite alphabet Discrete memoryless Capacity Exact

Channel and question

Input
\(X\in\{1,\ldots,q\}\)
Output
\(Y=X\)
Law
\(W(y|x)=\mathbf 1\{y=x\}\).
Quantity
Shannon capacity \(C\), measured in bits per channel use.

Criterion. Zero-error and average-error capacities coincide.

  • Channel uses are independent.
  • Rates are measured in bits.

Parameters

\(q\)
Alphabet size. Range: \(q\ge2\).

Current status

\[C=\log_2 q\]
ResultRelationMethodYear
Lower\(C\ge\log_2 q\)Transmit one q-ary symbol per use.1948
Upper\(C\le\log_2 q\)There are only q outputs per use.1948

Lean formalization

Canonical statementDefinitions

Version 1 · Lean. The identity finite channel is part of the shared API.

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

Discussion

Thread key: capacityatlas:noiseless-q-ary-channel

Find discussionStart discussion

Related problems

Binary Z-channel Z-channel

One binary symbol is transmitted perfectly while the other can flip in only one direction.

Point-to-point Binary Finite alphabet Discrete memoryless Asymmetric Capacity Exact
Solved \(C_Z(p)=\log_2\!\left(1+(1-p)p^{p/(1-p)}\right)\)
Binary erasure channel BEC

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

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Erasure Capacity Exact
Solved \(C_{\mathrm{BEC}}(\varepsilon)=1-\varepsilon\)
Binary symmetric channel BSC

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

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Capacity Exact
Solved \(C_{\mathrm{BSC}}(p)=1-h_2(p)\)
DMC with causal state information at the encoder

An iid channel state is revealed causally to the encoder but not to the decoder.

Point-to-point Finite alphabet Discrete memoryless Causal state information Side information Capacity Exact Single-letter characterization
Solved \(C_{\mathrm{causal}}=\max_{P_U,\,x=f(U,S)} I(U;Y)\)