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
    I think I'm starting to get it.. Thanks :)2011-11-11