Re: Shannon's paper, and H as a lower bound on average code length.

John schrieb:
On Aug 25, 2:19 pm, Thomas Richter <t...@xxxxxxxxxxxxxxxxx> wrote:
John schrieb:

Under certauincontraints he may have done, are you within the
constraints???
He shows for a given code that *that* code has H as a lower bound. But
what (from my understanding) he hasn't done is show that there is no
other code which can do better than H on average.
Your understanding is wrong.


Would you care to elaborate? Why does the statement:

"The converse part of the theorem, that C/H cannot be exceeded, may
be
proved by nothing that the entropy of the channel input per second is
equal to that of the source, since the transmitter must be non-
singular, and also this entropy cannot exceed the channel capacity.
Hence H' <= C and the number of symbols per second = H'/H <= C/H. "

establish H as the lowest bound on all uniquely decodable codes?

For that, you need the Kraft inequality. The proof is not overly hard, and you can
do that yourself, so here is a sketch (for binary only, it doesn't matter really):

Kraft inequality tells you that for a (binary) code to be uniquely decodable, you
need to have

\sum_i 2^{-l_i} <= 1 (1)

where l_i is the length of the code of the i-th symbol. Now, the average code length
of such a code on a IID source with symbol probabilities p_i is

E(l) = \sum_i p_i l_i (2)

and you want to minimize this expression (2) under the constraint (1). Obviously, (2)
becomes even smaller if we allow non-integer l_i's such that in (1) equality holds. There
is probably no such code, but we only need a bound. Now, to solve such a problem, use
Langrage multipliers, and define a functional J with

J = \sum_i p_i l_i + \lambda (\sum_j 2^{-l_i} - 1)

which must become maximal. Derivation by x_k gives you (after a short computation) that

l_j = - log(p_j) + log(\lambda)

reaches the minimum. Inserting this again into (1) gives \lambda = 0. Comparing this with
(2) establishes for this optimal code the size entropy H as minimum.

q.e.d.

So long,
Thomas
.

Relevant Pages

  • Re: Disorderly Conduct
    ... What you perceive as my lack of understanding is ... entropy and you elect to parrot that. ... the spiritual universe), ... The original physical concepts, which are well understood by people ...
    (talk.origins)
  • Re: Disorderly Conduct
    ... What you perceive as my lack of understanding is actually ... entropy and you elect to parrot that. ... the spiritual universe), ... The original physical concepts, which are well understood by people ...
    (talk.origins)
  • Re: Is it true that when you mix two volumes of identical gas, there is no entropy change?
    ... In my understanding, entropy is number of states the system can be in. ... I did not know about the significance of knowing the number of ... molecules. ...
    (sci.chem)
  • Re: Shannons paper, and H as a lower bound on average code length.
    ... Your understanding is wrong. ... proved by nothing that the entropy of the channel input per second is ... and also this entropy cannot exceed the channel capacity. ...
    (comp.compression)