Prefix Codes

A prefix code assigns bit strings so that no codeword is a prefix of another, allowing instant decoding.

The prefix property

In a prefix code (also called a prefix-free or instantaneous code), no codeword is the beginning of any other. This lets a decoder recognize each symbol as soon as its bits arrive, with no lookahead or delimiters.

Tree view

Kronos motion — number counters

A prefix code corresponds to a binary tree where symbols sit only at leaves. The path from root to a leaf, reading left as 0 and right as 1, spells that symbol's codeword. Leaf-only placement guarantees the prefix property.

Kraft inequality

Codeword lengths lᵢ form a valid prefix code exactly when the sum of 2^(−lᵢ) is at most 1. This inequality tells you when a set of desired lengths is achievable, and it ties code length to probability.

Variable length efficiency

Assigning short codewords to frequent symbols and long ones to rare symbols lowers the average length. The optimal assignment, subject to the prefix property, is what Huffman coding produces.

Contrast with fixed-length

Fixed-length codes like ASCII are trivially prefix-free but cannot exploit uneven frequencies. Prefix codes trade a fixed width for adaptivity, approaching the source entropy while remaining uniquely and instantly decodable.

python

code = {'a':'0','b':'10','c':'110','d':'111'}
def decode(bits, code):
    inv = {v:k for k,v in code.items()}
    out, buf = [], ''
    for b in bits:
        buf += b
        if buf in inv:
            out.append(inv[buf]); buf = ''
    return ''.join(out)
print(decode('010110111', code))  # a b c d