# What is the capacity of a channel which doesn't allow subsequent 1's?

A given channel doesn't allow transmission of subsequent 1's (so 101, 100 etc are valid strings, and 110, 111, 011 are invalid). Given a valid string, it is transmitted as is with probability 1 (deterministic).

How do I calculate the capacity of such a channel?

-

Hint: You are looking for the number of $n$ bit strings without successive $1$s. Let $F(n)$ be the number of strings without successive $1$'s ending in $0$. Let $G(n)$ be the number of strings without successive $1$'s ending in $1$. Then $F(1)=1, G(1)=1, F(n)=G(n-1), G(n)=F(n-1)+G(n-1)$, and the number of $n$ bit strings will be $F(n)+G(n)$ Finally you compare this with $2^n$, the number of $n$ bit strings without the restriction.
So if you send $n$ bits you can send $F(n-1)$ messages. Without the restriction you could transmit that many messages by sending $m=\log_2 F(n-1)$ bits. So your channel capacity is reduced by the factor $\frac{\log_2 F(n-1)}{n}$ – Ross Millikan Nov 11 '11 at 18:51