Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 37 ยท Source Coding

The Kraft Inequality

The Kraft-McMillan inequality tells you exactly which codeword lengths a prefix code can have. Learn the tree-counting proof idea, then build a code from lengths in Python.

Can you build a prefix code with codeword lengths 1, 2, 2, 3? What about 1, 1, 2? You can answer without trying any codewords at all. The Kraft inequality says a binary prefix code with lengths l_1, ..., l_n exists if and only if

TEXT
sum over i of 2^(-l_i)  <=  1

This tiny inequality is the bridge between codes and probabilities. It lets us talk about code lengths as if they were -log2 of a probability, which leads straight to the source coding theorem.

The budget picture

Think of the number 1 as a budget. A codeword of length l costs 2^(-l): a 1-bit word costs 1/2, a 2-bit word 1/4, a 3-bit word 1/8. You may keep adding codewords until the budget runs out. Short words are expensive because they rule out many longer words that would start with them.

In the code tree, a codeword of length l sits at depth l and blocks the whole subtree below it. At depth L there are 2^L nodes; the codeword blocks 2^(L-l) of them, a fraction 2^(-l) of the level. Since prefix-free words block disjoint fractions, the fractions cannot add to more than 1.

Python Check Kraft sums

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Lengths 1, 2, 3, 3 sum to exactly 1 (a complete code: no room left, nothing wasted). 1, 2, 2, 3 sums to 1.125, so no prefix code has those lengths. 1, 2, 3 sums to 7/8 < 1: possible, but a bit of the tree stays unused, which means a shorter code probably exists.

From lengths to a code

The inequality is constructive. Sort the lengths ascending, then hand out codewords in order, always taking the next available binary number and padding it with zeros when the length grows. This is the idea behind canonical codes used in DEFLATE.

Python Build a prefix code from lengths

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For A:1, B:2, C:3, D:3 you get 0, 10, 110, 111, the code from the last lesson. The second call shows the construction working for any valid set.

McMillan: unique decodability changes nothing

Kraft's argument covers prefix codes. McMillan's theorem extends it: every uniquely decodable code also satisfies sum 2^(-l) <= 1. The proof raises the sum to the n-th power and counts distinct concatenations.

The consequence is important: you never lose by restricting to prefix codes. For any uniquely decodable code there is a prefix code with exactly the same lengths. So we study prefix codes only, with no loss in optimal average length.

Python A brute-force view of the McMillan argument

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If a code were uniquely decodable but had S > 1, S^n would grow exponentially, yet the number of possible bit strings of each total length is limited. That contradiction forces S <= 1.

Lengths from probabilities

Here is the link to entropy. Given probabilities p_i, choose lengths l_i = ceil(-log2 p_i) (the surprisal, rounded up). Then 2^(-l_i) <= p_i, so

TEXT
sum 2^(-l_i) <= sum p_i = 1

and Kraft guarantees a prefix code with those lengths exists. This is exactly Shannon coding, which you will build in Shannon and Shannon-Fano Codes.

Python Shannon lengths always satisfy Kraft

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Kraft sums work for any alphabet size D: replace 2 by D, so ternary codes need sum D^(-l_i) <= 1. The tree just has D branches per node.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Do binary prefix codes exist with lengths 1, 2, 2, 3?

    1/2 + 1/4 + 1/4 + 1/8 = 9/8 > 1, so no prefix code can have these lengths.
  2. 2. A code is complete if its Kraft sum equals

    Sum = 1 means the code tree is full: every internal node has all children used.
  3. 3. What does McMillan's theorem add to Kraft's?

    Any uniquely decodable code has a Kraft sum at most 1, so a prefix code with the same lengths exists.
  4. 4. Setting l_i = ceil(-log2 p_i) guarantees what?

    2^(-l_i) <= p_i, so the sum is at most 1. Optimality is a separate question (Huffman).

Summary

  • A binary prefix code with lengths l_i exists iff sum 2^(-l_i) <= 1.
  • The proof: each codeword blocks a fraction 2^(-l) of the tree, and blocked fractions cannot overlap.
  • You can build the code directly from the lengths (canonical code).
  • McMillan: uniquely decodable codes obey the same inequality, so prefix codes are enough.
  • Lengths ceil(-log2 p) always satisfy it.

Next: The Source Coding Theorem