Proof: Source Coding Theorem For Symbol Codes
Let denote the wordlength of each possible . Define, where C is chosen so that .
Then
where the second line follows from Gibbs' inequality and the fifth line follows from Kraft's inequality: so .
For the second inequality we may set
so that
and so
and
and so by Kraft's inequality there exists a prefix-free code having those wordlengths. Thus the minimal S satisfies
Read more about this topic: Shannon's Source Coding Theorem
Famous quotes containing the words source, theorem, symbol and/or codes:
“By recognizing a favorable opinion of yourself, and taking pleasure in it, you in a measure give yourself and your peace of mind into the keeping of another, of whose attitude you can never be certain. You have a new source of doubt and apprehension.”
—Charles Horton Cooley (18641929)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (19131960)
“The glance is natural magic. The mysterious communication established across a house between two entire strangers, moves all the springs of wonder. The communication by the glance is in the greatest part not subject to the control of the will. It is the bodily symbol of identity with nature. We look into the eyes to know if this other form is another self, and the eyes will not lie, but make a faithful confession what inhabitant is there.”
—Ralph Waldo Emerson (18031882)
“We must trust infinitely to the beneficent necessity which shines through all laws. Human nature expresses itself in them as characteristically as in statues, or songs, or railroads, and an abstract of the codes of nations would be an abstract of the common conscience.”
—Ralph Waldo Emerson (18031882)