Re: Simple question on Shannon's 1948 paper

Michael wrote:
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).

Thanks Michael.

You have made it beautifully clear.

I have (if you don't mind) one last question.

I assume N(t-t_i) = 0 if t-t_i <0.

My question is what to assume about N(0).
If t_1 is the smallest of the t_i's and I choose
t=t_1 then I would expect that N(t_1)=1.

Plugging this into the formula Shannon derived,
I get N(t_1)=N(0) +0 + 0 + ...

So I evidently need to take N(0)=1. Is this correct
and if so what is its interpretation?

Thanks again.

Inf.

.

Relevant Pages

  • Re: Simple question on Shannons 1948 paper
    ... 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. ... If this still isn't clear, please let me know which part is losing you, ...
    (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)