Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.