Kraft's Inequality - Proof of The General Case

Proof of The General Case

Consider the generating function in inverse of x for the code S

in which —the coefficient in front of —is the number of distinct codewords of length . Here min is the length of the shortest codeword in S, and max is the length of the longest codeword in S.

For any positive integer m consider the m-fold product Sm, which consists of all the words of the form, where are indices between 1 and n. Note that, since S was assumed to uniquely decodable, if, then . In other words, every word in comes from a unique sequence of codewords in . Because of this property, one can compute the generating function for from the generating function as

$G(x) = \left( F(x) \right)^m = \left( \sum_{i=1}^n x^{-|s_i|} \right)^m = \sum_{i_1=1}^n \sum_{i_2=1}^n \cdots \sum_{i_m=1}^n x^{-\left(|s_{i_1}| + |s_{i_2}| + \cdots + |s_{i_m}|\right)} = \sum_{i_1=1}^n \sum_{i_2=1}^n \cdots \sum_{i_m=1}^n x^{-|s_{i_1} s_{i_2}\cdots s_{i_m}|} = \sum_{\ell=m \cdot \min}^{m \cdot \max} q_\ell \, x^{-\ell} \; .$

Here, similarly as before, —the coefficient in front of in —is the number of words of length in . Clearly, cannot exceed . Hence for any positive x

$\left( F(x) \right)^m \le \sum_{\ell=m \cdot \min}^{m \cdot \max} r^\ell \, x^{-\ell} \; .$

Substituting the value x = r we have

$\left( F(r) \right)^m \le m \cdot (\max-\min)+1$

for any positive integer . The left side of the inequality grows exponentially in and the right side only linearly. The only possibility for the inequality to be valid for all is that . Looking back on the definition of we finally get the inequality.

$\sum_{i=1}^n r^{-\ell_i} = \sum_{i=1}^n r^{-|s_i|} = F(r) \le 1 \; .$

Read more about this topic: Kraft's Inequality

Famous quotes containing the words proof of the, proof of, proof, general and/or case:

“From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
—Johan Huizinga (1872–1945)

“There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
—Herman Melville (1819–1891)

“If we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)

“You have lived longer than I have and perhaps may have formed a different judgment on better grounds; but my observations do not enable me to say I think integrity the characteristic of wealth. In general I believe the decisions of the people, in a body, will be more honest and more disinterested than those of wealthy men.”
—Thomas Jefferson (1743–1826)

“I love to weigh, to settle, to gravitate toward that which most strongly and rightfully attracts me;Mnot hang by the beam of the scale and try to weigh less,—not suppose a case, but take the case that is; to travel the only path I can, and that on which no power can resist me. It affords me no satisfaction to commence to spring an arch before I have got a solid foundation.”
—Henry David Thoreau (1817–1862)