Re: Simple question on Shannon's 1948 paper

I am interested in the second unnumbered equation in
Part 1 of the paper:

N(t) = N(t-t_1) + N(t-t_2) + ... N(t-t_n)

How do I see that the above equation does what it says
it does, and what are the conditions on N(t)?

A couple lines before and after define terms. I'll paraphrase:

We are interested in sequences of the symbols S1, ..., Sn. Each symbol
Si takes t_i time to transmit.

N(t) = number of sequences of duration t
= number of sequences of duration t that end in S1 + number of
sequences of duration t that end in S2 + . . . + number of sequences of
duration t that end in Sn
= number of sequences of duration t - t_1 * 1 + number of
sequences of duration t - t_2 * 1 + . . . + number of sequences of
duration t - t_n * 1
= N(t-t_1) + N(t-t_2) + ... N(t-t_n)

The third step is the doosy. Basically, we want to show that, for all
i
number of sequences of duration t that end in Si = number of sequences
of duration t - t_i * 1

Well, basically, we could write out all the sequences:
SS...SSi
where S is some symbol (any symbol), and the last symbol is Si. There
could be a bunch of these:
S1Si
S2Si
S1S2S3S4Si
whatever.

The total number is (# of sequences SS...S) * 1, i.e., the last element
of the sequence is fixed as Si.

Si takes t_i time. Let's suppose we can transmit SS...S in t-t_i time.
Then we can transmit SS...SSi in (t-t_i) + t_i = t time. In fact,
that's if and only if (details left for you).

If this still isn't clear, please let me know which part is losing you,
and I'll see if I can fill in some more detail.

Michael

.

Relevant Pages

  • Re: Simple question on Shannons 1948 paper
    ... Michael wrote: ... We are interested in sequences of the symbols S1, ..., Sn. ... N= number of sequences of duration t ... Let's suppose we can transmit SS...S in t-t_i time. ...
    (sci.stat.math)
  • Re: decode Truncated binary encoding
    ... sequences of words, because then I need to add one more word at the ... Truncated binary encoding I would need 3 bits to transmit u, ... case of a series of decreasing integers. ...
    (comp.compression)