Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about Shannon's mathematics

  1. May 17, 2013 #1
    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. jcsd
  3. May 17, 2013 #2


    User Avatar
    Homework Helper

    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
  4. May 23, 2013 #3
    Yes, I understand what the terms mean (I think) but I don't see how the two sides of the equation are equal.
  5. May 23, 2013 #4


    User Avatar
    Homework Helper

    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."

    PS. Sorry for biting your head off.
    Last edited: May 23, 2013
  6. May 23, 2013 #5
    Right. So if we have t1=2 and t2=4, any sequence ending in two S1's will have the same length as any sequence ending in one S2. In such a case you count the S1S1 sequences twice.

    I don't believe Shannon could have made a mistake in this paper, and I don't believe it could have gone unquestioned if he had. So really I'm just trying to understand why you don't count the sequences above twice, or if you do, why it doesn't matter.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Question Shannon's mathematics Date
B Secondary Upper and Lower Bound QUESTION Mar 10, 2018
B Find the missing energy value given a set of data (Hypothetical question) Mar 3, 2018
B Simple question about compactness Feb 22, 2018
B Beginner function question Feb 17, 2018
Shannon entropy problem Feb 10, 2010