CCapacity Atlas
gelfand-pinsker-channel

DMC with noncausal state information at the encoder

The entire iid state sequence is known noncausally to the encoder but not the decoder.

Point-to-point Finite alphabet Discrete memoryless Noncausal state information Side information Capacity Exact Single-letter characterization

Channel and question

Input
The encoder maps \((M,S^n)\) to \(X^n\).
Output
\(Y_t\sim W(\cdot|X_t,S_t)\).
Law
States \(S_t\) are iid and known in full to the encoder before transmission.
Quantity
Gel'fand-Pinsker capacity \(C_{\mathrm{GP}}\), measured in bits per channel use.

Criterion. Average-error capacity.

  • The decoder does not know the state sequence.
  • The state distribution is fixed and known.

Current status

\[C_{\mathrm{GP}}=\max_{P_{U|S},\,x=f(U,S)}\bigl[I(U;Y)-I(U;S)\bigr]\]
ResultRelationMethodYear
Lower\(C_{\mathrm{GP}}\ge\max[I(U;Y)-I(U;S)]\)Random binning selects a codeword jointly typical with the state.1980
Upper\(C_{\mathrm{GP}}\le\max[I(U;Y)-I(U;S)]\)Csiszár's sum identity and an auxiliary random variable.1980

Lean formalization

Canonical statementNone

Version 1 · Lean. This theorem is a natural substantial external-proof repository once state and entropy APIs exist.

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. Sergei I. Gel'fand and Mark S. Pinsker (1980). Coding for Channel with Random Parameters. Problems of Control and Information Theory.
  2. Abbas El Gamal and Young-Han Kim (2011). Network Information Theory. Cambridge University Press. DOI 10.1017/CBO9781139030687.

Discussion

Thread key: capacityatlas:gelfand-pinsker-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)\)