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:

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

“A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
—Samuel Johnson (1709–1784)

“Right and proof are two crutches for everything bent and crooked that limps along.”
—Franz Grillparzer (1791–1872)

“Surely one of the peculiar habits of circumstances is the way they follow, in their eternal recurrence, a single course. If an event happens once in a life, it may be depended upon to repeat later its general design.”
—Ellen Glasgow (1873–1945)

“Instructing in cures, therapists always recommend that “each case be individualized.” If this advice is followed, one becomes persuaded that those means recommended in textbooks as the best, means perfectly appropriate for the template case, turn out to be completely unsuitable in individual cases.”
—Anton Pavlovich Chekhov (1860–1904)