1. May 17, 2013

### ScarTissue

I'm trying to go through Shannon's paper "A Mathematical Theory of Communication" to improve my understanding of information theory.

In Part I (Discrete Noiseless Systems) Shannon states:

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) = N(t -t1)+N(t -t2)+...+N(t -tn):

The total number is equal to the sum of the numbers of sequences ending in S1, S2, . . . , Sn and these are N(t -t1), N(t -t2), . . . ,N(t -tn), respectively.

So I can't understand how this sum is actually working. For example, if t1=2s and t2=4s, then the first term in the sum is the number of all sequences ending in S1 as expected. However the second term is going to be the number of all sequences ending in either S1,S1 or S2. So this means that some of the sequences ending in S1 have been counted twice by this sum.

Am I missing something here? Or am I correct and the right hand side of the equation is going to be larger than the left?

2. May 17, 2013

### verty

To get a sequence of duration t, we append some Si to a sequence of duration t - ti. N(t) is just the number of sequences of duration t, and is the sum of those with each Si to be appended.

-- sorry, I see I answered the wrong question. The question was, is the sum correct?

Last edited: May 17, 2013
3. May 23, 2013

### ScarTissue

Yes, I understand what the terms mean (I think) but I don't see how the two sides of the equation are equal.

4. May 23, 2013

### verty

We know Claude Shannon as one of the forefathers of the digital age. Someone with this much foresight would not easily make a mistake. Whatever he wrote there we must assume was intentional.

Therefore, look again. And focus too on what is being counted. We are counting only t-length sequences, not any shorter sequences.

In reference to: "So this means that some of the sequences ending in S1 have been counted twice by this sum."