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, proof, general and/or case:

“The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
—Lenny Bruce (1925–1966)

“Talk shows are proof that conversation is dead.”
—Mason Cooley (b. 1927)

“We have seen over and over that white male historians in general have tended to dismiss any history they didn’t themselves write, on the grounds that it is unserious, unscholarly, a fad, too “political,” “merely” oral and thus unreliable.”
—Adrienne Rich (b. 1929)

“Socialists make the mistake of confusing individual worth with success. They believe you cannot allow people to succeed in case those who fail feel worthless.”
—Kenneth Baker (b. 1934)