Kraft inequality

cosmos 15th October 2017 at 7:48pm
Information theory

For a set of Codewords of length l(i)l(i) (for the iith codeword), which constitute a Prefix code, the following holds.

i2l(i)1\sum_i 2^{-l(i)} \leq 1

This can be seen by drawing a Binary tree where each layer corresponds to assigning a bit to a letter in the codeword. The leaves of the tree will correspond to the codewords. The limited number of nodes and codeword choices in the tree give rise to the inequality

the Kraft inequality is a sufficient condition for the existence of a codeword set with the specified set of codeword lengths.


Could this be related to LYM inequality?