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]\]
Known results and bounds for DMC with noncausal state information at the encoder
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

Formal verification

Lean coverageFormally stated

New statements await mathematical review and proofs.

Claims

  • The Gel'fand--Pinsker formula for iid state seen noncausally only by the encoder.
    operational-capacity · exact capacity · solved · Formally stated · v1
Lean declarations (1)

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

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 memory with encoder-known stuck-at defects

Independent stuck-at defects are known noncausally to the encoder but not the decoder.

Point-to-point Binary Finite alphabet Discrete memoryless Noncausal state information Capacity Exact
Solved \(C=1-\delta\)
Binary symmetric channel BSC

Each bit is independently flipped with probability \(p\).

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Capacity Exact
Solved \(C_{\mathrm{BSC}}(p)=1-h_2(p)\)