CCapacity Atlas
no-consecutive-ones-noiseless-channel

Noiseless binary channel with no consecutive ones

A noiseless binary channel forbids adjacent transmitted ones and has golden-ratio capacity.

Point-to-point Binary Finite alphabet Memory Capacity Exact

Channel and question

Input
Binary words that contain no adjacent pair of ones.
Output
The complete input word, received noiselessly.
Law
Y=X, with the (1,infinity) run-length constraint on input words.
Quantity
Noiseless binary channel with no consecutive ones capacity \(C\), measured in bits per channel use.

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

  • Every codeword satisfies the constraint. There is no hidden constraint imposed on a preceding bit.
  • Rates are per transmitted binary coordinate and error is averaged over uniform messages.

Current status

\[C=\log_2\frac{1+\sqrt5}{2}\]
Known results and bounds for Noiseless binary channel with no consecutive ones
ResultRelationMethodYear
Exact\(C=\log_2\frac{1+\sqrt5}{2}\)Admissible-word counting and noiseless operational coding.1948

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

  • The noiseless binary (1,infinity) constrained channel has log(phi) capacity.
    operational-capacity · exact capacity · solved · Formally stated · v2
Lean declarations (1)

References

  1. Claude E. Shannon (1948). A Mathematical Theory of Communication. Bell System Technical Journal. DOI 10.1002/j.1538-7305.1948.tb01338.x.

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