January 12, 2025
Arithmetic Coding
Arithmetic coding closes the gap between Huffman's per-symbol integer lengths and true entropy. A single number in the unit interval encodes an entire sequence; 32-bit integer arithmetic makes it practical.
Prefix-Free
Browse posts by tag
August 4, 2024
Huffman Coding
Given a finite distribution, Huffman's algorithm builds the prefix-free code with minimum expected length. It is the first entropy-optimal code in this series.
February 25, 2024
VByte / Varint
VByte trades bit-level precision for byte-alignment, and that trade wins in practice. Most production columnar databases and network protocols use VByte for integer encoding.
September 17, 2023
Rice / Golomb
Rice and Golomb codes are parametric: a single parameter k (or m) tunes the code to a specific geometric distribution. Choosing k is choosing your prior precisely.
April 23, 2023
Fibonacci Coding
Fibonacci coding uses Zeckendorf's representation to produce self-synchronizing codewords. Every codeword ends in two consecutive ones; a single bit flip corrupts at most two codewords.
November 13, 2022
Elias Delta and Omega
Elias delta and omega extend Elias gamma by recursively encoding the length prefix. Each step yields shorter codewords for large integers at a small constant cost for small ones.
June 19, 2022
Unary and Elias Gamma
Unary and Elias gamma are the two simplest universal codes. Unary encodes n in n bits; gamma in 2 log2(n)+1 bits. Each implies a different prior over the integers.
January 15, 2022
Universal Codes as Priors
Every prefix-free code is a hypothesis about the source. The codeword lengths determine an implicit probability distribution; the code is optimal when that prior matches the true source.
September 13, 2020
McMillan's Converse
Any length vector satisfying Kraft has a prefix-free code. Here is the construction.
March 22, 2020
Kraft's Inequality
Which codeword-length vectors are achievable by prefix-free codes? Kraft's inequality is the answer.