Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 37 ยท Source Coding

Codes and Prefix Codes

What a code is, why fixed-length codes waste bits, and why prefix-free codes can be decoded instantly. Build encoders and decoders, a code tree, and a unique-decodability test in Python.

A code assigns to each source symbol a string of bits called a codeword. Compression is the art of choosing codewords so that the average length is as short as possible, while still allowing the receiver to recover the message exactly. This lesson sets the rules; the next lessons show how short the average can get.

Fixed-length and variable-length codes

A fixed-length code gives every symbol the same number of bits. For an alphabet of n symbols you need ceil(log2 n) bits each. ASCII uses 7 or 8 bits for every character, whether it is a common e or a rare z.

A variable-length code gives frequent symbols short codewords and rare ones long codewords, like Morse code (E is a single dot, Q is dash-dash-dot-dash). If the probabilities are very uneven, the average length drops well below the fixed-length cost.

Python Fixed versus variable length

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.

The variable-length code averages 1.75 bits per symbol, which matches the entropy exactly (the probabilities are powers of 1/2). Compare 2 bits for the fixed code: a saving of 12.5%.

Decoding must be possible

Shorter codewords are not free. Suppose A -> 0, B -> 01, C -> 1. The bit string 01 could be B or A followed by C: it is ambiguous. We need codes that can be decoded uniquely.

Definitions, from weakest to strongest:

  • Non-singular: different symbols get different codewords.
  • Uniquely decodable: every sequence of symbols gives a different bit string, so any received string has at most one parse.
  • Prefix code (instantaneous): no codeword is a prefix of another. Each codeword can be recognized the moment its last bit arrives, with no look-ahead.

Every prefix code is uniquely decodable, and every uniquely decodable code is non-singular, but not the other way round.

Python Check the prefix property

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.

Sorting puts a codeword directly before any word that starts with it, so comparing neighbors is enough.

Decoding a prefix code

Because no codeword is a prefix of another, decoding is a simple left-to-right scan: collect bits until they form a codeword, output the symbol, restart. No back-tracking, no look-ahead.

Python Encoder and decoder

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.

Ten symbols take 18 bits instead of 20.

Code trees

A binary prefix code is a binary tree: each codeword is a path from the root (0 = go left, 1 = go right), and the symbols sit at leaves. A code is prefix-free exactly when every symbol is at a leaf, because a symbol at an internal node would be a prefix of everything below it.

flowchart TD
    R(("root")) -- "0" --> A["A = 0"]
    R -- "1" --> N1(("1"))
    N1 -- "0" --> B["B = 10"]
    N1 -- "1" --> N2(("11"))
    N2 -- "0" --> C["C = 110"]
    N2 -- "1" --> D["D = 111"]

The tree of the code A=0, B=10, C=110, D=111. Short paths go to likely symbols.

This picture explains the Kraft inequality of the next lesson: the tree has only so much room.

A uniquely decodable code that is not prefix-free

Prefix codes are not the only decodable ones. The code { "0", "01", "011", "111" } is not a prefix code (0 prefixes 01), but every string parses uniquely if you read ahead to the next 0. However, you must look ahead, so decoding is not instantaneous. We will see that restricting to prefix codes costs nothing in average length.

Python Count the parses of a bit string

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.

The ambiguous code gives two parses for 01 and 011; the prefix code never gives more than one (and sometimes zero, when the string is not a valid concatenation).

For checking unique decodability of arbitrary codes there is the Sardinas-Patterson algorithm. In practice you almost always design prefix codes directly, so you rarely need it.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a prefix code?

    Prefix-free codes can be decoded instantly: when a codeword completes, it is certainly that symbol.
  2. 2. Where do symbols sit in the tree of a prefix code?

    A symbol at an internal node would be a prefix of the codewords below it.
  3. 3. The code {0, 01, 1} is

    '01' is either the single symbol 01 or the symbols 0 then 1.
  4. 4. Four equally likely symbols are encoded with the fixed code 00, 01, 10, 11. Could a variable-length code do better on average?

    The entropy of a uniform 4-symbol source is 2 bits, and no code can average less than the entropy.

Summary

  • A code maps symbols to codewords; variable-length codes use short words for likely symbols.
  • Codes must be uniquely decodable; prefix codes are the easy, instantaneous subset.
  • A binary prefix code is a tree with all symbols at leaves; decoding is a walk from the root.
  • Average length sum p(x) len(x) is what we try to minimize; entropy is the benchmark.

Next: The Kraft Inequality