# 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.
 Sub-hint: Fibonacci. – Did Nov 11 '11 at 18:31 OK, I do understand that for a string of length N I have Fibonacci(N-1) different symbols in the input alphabet. What I don't understand is why I need to compare these strings to the corresponding unrestricted ones. What I mean is that as far as I'm concerned, I could send Fib(N-1) fruit and vegetable types, which would be decoded into bits on the other side - who cares how many bits we had at the input? – Michael Litvin Nov 11 '11 at 18:33 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 I think I'm starting to get it.. Thanks :) – Michael Litvin Nov 11 '11 at 19:00