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:

“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)

“To cease to admire is a proof of deterioration.”
—Charles Horton Cooley (1864–1929)

“O, popular applause! what heart of man
Is proof against thy sweet, seducing charms?”
—William Cowper (1731–1800)

“They make a great ado nowadays about hard times; but I think that ... this general failure, both private and public, is rather occasion for rejoicing, as reminding us whom we have at the helm,—that justice is always done. If our merchants did not most of them fail, and the banks too, my faith in the old laws of the world would be staggered.”
—Henry David Thoreau (1817–1862)

“God ... created a number of possibilities in case some of his prototypes failed—that is the meaning of evolution.”
—Graham Greene (1904–1991)