1
$\begingroup$

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?

1 Answers 1

3

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.

  • 0
    Sub-hint: Fibonacci.2011-11-11
  • 0
    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?2011-11-11
  • 0
    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}$2011-11-11
  • 0
    I think I'm starting to get it.. Thanks :)2011-11-11