CCapacity Atlas
causal-state-information-channel

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

Channel and question

Input
The encoder chooses \(X_t=f_t(M,S^t)\).
Output
\(Y_t\) is generated from \(W(y_t|x_t,s_t)\).
Law
States \(S_t\) are iid and revealed to the encoder before choosing \(X_t\).
Quantity
Shannon-strategy capacity \(C_{\mathrm{causal}}\), measured in bits per channel use.

Criterion. Average-error capacity.

  • The decoder does not know the state sequence.
  • The state distribution and channel law are known.

Current status

\[C_{\mathrm{causal}}=\max_{P_U,\,x=f(U,S)} I(U;Y)\]

U indexes a distribution over state-dependent input strategies.

ResultRelationMethodYear
Lower\(C\ge\max I(U;Y)\)Random coding over deterministic state-response strategies.1958
Upper\(C\le\max I(U;Y)\)Absorb message and past states into a single auxiliary strategy variable.1958

Lean formalization

Canonical statementNone

Version 1 · Lean. State processes and causal encoder strategies need a shared operational layer.

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 (1958). Channels with Side Information at the Transmitter. IBM Journal of Research and Development.
  2. Abbas El Gamal and Young-Han Kim (2011). Network Information Theory. Cambridge University Press. DOI 10.1017/CBO9781139030687.

Discussion

Thread key: capacityatlas:causal-state-information-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 noncausal state information at the encoder Gel'fand-Pinsker channel

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
Solved \(C_{\mathrm{GP}}=\max_{P_{U|S},\,x=f(U,S)}\bigl[I(U;Y)-I(U;S)\bigr]\)