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:

“When children feel good about themselves, it’s like a snowball rolling downhill. They are continually able to recognize and integrate new proof of their value as they grow and mature.”
—Stephanie Martson (20th century)

“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)

“The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
—Andrew Michael Ramsay (1686–1743)

“There is in general good reason to suppose that in several respects the gods could all benefit from instruction by us human beings. We humans are—more humane.”
—Friedrich Nietzsche (1844–1900)

“In the case of all other sciences, arts, skills, and crafts, everyone is convinced that a complex and laborious programme of learning and practice is necessary for competence. Yet when it comes to philosophy, there seems to be a currently prevailing prejudice to the effect that, although not everyone who has eyes and fingers, and is given leather and last, is at once in a position to make shoes, everyone nevertheless immediately understands how to philosophize.”
—Georg Wilhelm Friedrich Hegel (1770–1831)