CCapacity Atlas
binary-memory-with-stuck-defects

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

Channel and question

Input
One chosen binary symbol per memory cell.
Output
The binary symbol stored in each cell.
Law
A normal cell returns its input. A defective cell returns its stuck value.
Quantity
Binary memory with encoder-known stuck-at defects capacity \(C\), measured in bits per channel use.

Criterion. Vanishing average block error, with the constraints specified in the model.

  • State probabilities are 1-delta, delta/2, delta/2 for normal, stuck-zero, stuck-one.
  • States are iid and independent of the uniform message, with 0 <= delta <= 1.
  • The encoder sees the entire state word. The decoder sees only the output word.

Current status

\[C=1-\delta\]
Known results and bounds for Binary memory with encoder-known stuck-at defects
ResultRelationMethodYear
Exact\(C=1-\delta\)Defect masking and a genie-aided converse.1983

Formal verification

Lean coverageFormally stated

Concrete operational definitions and admitted research statements are present. Existing proofs are preserved. New statements require mathematical review and proof completion.

Claims

  • Noncausal knowledge of the entire iid stuck-at pattern gives capacity 1-delta.
    operational-capacity · exact capacity · solved · Formally stated · v1
Lean declarations (1)

References

  1. Chris Heegard and Abbas A. El Gamal (1983). On the Capacity of Computer Memory with Defects. IEEE Transactions on Information Theory.

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 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)\)
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),\,U\perp S} I(U;Y)\)