Proof For Prefix Codes
Suppose that . Let be the full -ary tree of depth . Every word of length over an -ary alphabet corresponds to a node in this tree at depth . The th word in the prefix code corresponds to a node ; let be the set of all leaf nodes in the subtree of rooted at . Clearly
Since the code is a prefix code,
- .
Thus, given that the total number of nodes at depth is ,
from which the result follows.
Conversely, given any ordered sequence of natural numbers,
satisfying the Kraft inequality, one can construct a prefix code with codeword lengths equal to by pruning subtrees from a full -ary tree of depth . First choose any node from the full tree at depth and remove all of its descendents. This removes fraction of the nodes from the full tree from being considered for the rest of the remaining codewords. The next iteration removes fraction of the full tree for total of . After iterations,
fraction of the full tree nodes are removed from consideration for any remaining codewords. But, by the assumption, this sum is less than 1 for all . Thus prefix code with lengths can be constructed for all source symbols.
Read more about this topic: Kraft's Inequality
Famous quotes containing the words proof and/or codes:
“The proof of a poet is that his country absorbs him as affectionately as he has absorbed it.”
—Walt Whitman (1819–1892)
“... until both employers’ and workers’ groups assume responsibility for chastising their own recalcitrant children, they can vainly bay the moon about “ignorant” and “unfair” public criticism. Moreover, their failure to impose voluntarily upon their own groups codes of decency and honor will result in more and more necessity for government control.”
—Mary Barnett Gilson (1877–?)