In Shannon's landmark paper, "A Mathematical Theory of Communications" he discusses the channel capacity of "Discrete Noiseless Systems). From the paper:
Definition: The capacity C of a discrete channel is given by
}}{T})
where N(T) is the number of allowed signals of duration T. It is easily seen that in the teletype case this reduces to the previous result. It can be shown that the limit in question will exist as a finite number in most cases of interest. Suppose all sequences of the symbols S1,...,Sn are allowed and these symbols have durations t1,...,tn. What is the channel capacity? If N(t) represents the number of sequences of duration t we have
=N(t-t1)%2BN(t-t2)%2B...%2BN(t-tn))
I don't understand the final sequence. If N(t) is the "number of sequences of duration t", isn't N(t-t1) the "number of sequences in t'," where t' is the total duration minus the time it takes to transmit symbol S1?
To illustrate by example, suppose we have 3 symbols S1, S2, S3, which uniformly take 1 second to transmit, i.e., t1=t2=t3=1s
We would expect N(3 seconds) to be 3, correct? But the formula given by Shannon gives
=N(3-1)%2BN(3-1)%2B...%2BN(3-1))
We can clearly see that N(2) is expected to be 2, but the formula thus gives N(3) = 6, twice what was expected.
What am I missing here?
It is a recursion.
At time $t$ there are $N(t)$ possible signals of length $t$. There are $n$ symbols, so if the last symbol was $S_k$, then there are $N(t-t_k)$ possible signals leading up to $S_k$, which take time $t-t_k$, plus the length of $S_k$ which is $t_k$.
Now add up over all symbols and we get $N(t) = \sum_i N(t-t_i)$.