CCapacity Atlas
finite-dmc-input-cost

Finite discrete memoryless channel with input cost

A finite DMC under a feasible maximum-codeword average-cost constraint has a constrained mutual-information capacity formula.

Point-to-point Finite alphabet Discrete memoryless Capacity Exact Single-letter characterization

Channel and question

Input
Symbols in a finite alphabet \(\mathcal X\), with cost \(c(x)\ge0\).
Output
Symbols in a finite alphabet \(\mathcal Y\).
Law
A stationary memoryless transition law \(W(y\mid x)\).
Quantity
Cost-constrained capacity \(C(\Gamma)\), measured in bits per channel use.

Criterion. Arbitrary blocklength deterministic codes with maximum-codeword cost and vanishing average error.

  • Every codeword has average input cost at most \(\Gamma\).
  • At least one input symbol has cost at most \(\Gamma\).
  • Messages are uniform and average decoding error vanishes.

Current status

\[C(\Gamma)=\max_{P_X:\,\mathbb E[c(X)]\le\Gamma} I(X;Y)\]
ResultRelationMethodYear
Exact\(C(\Gamma)=\max_{P_X:\,\mathbb E[c(X)]\le\Gamma}I(X;Y)\)Cost-constrained channel coding theorem and convex optimization.2015

Lean formalization

Canonical statementStatement

Version 1 · Lean. The model fixes maximum codeword cost separately from admissible one-letter input distributions.

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. Tobias Sutter, David Sutter, Peyman Mohajerin Esfahani, and John Lygeros (2015). Efficient Approximation of Channel Capacities. IEEE Transactions on Information Theory. DOI 10.1109/TIT.2015.2401002.

Discussion

Thread key: capacityatlas:finite-dmc-input-cost

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)\)