66818

Kraft inequality

Ifintcgcrs n_x.....n_M satisfy:

u

1

.-i

then. a prefix condition codę of alphabet length D exists. with these integers as codeword lengths._

A convenient graphical representation of a codę is a tree built of branches connecting nodes, wiih sequences assigned to nodes, codewords (sequences satisfying the prefix condition) assigned to terminal nodes (leafs). Each branch connects two nodes located at different levels, starli ng from the lcvcl zero down to the lcvel n = max n,.

Sequences assigned to nodes at the first level are alphabet letters. Sequences of the length n_t, assigned to nodes at the /'-th level, have prefixes assigned to nodes at the (i-l)-th level. supplemcntcd with one alphabet lcttcr