Coding-Theory

Information Theory, Inference, and Learning Algorithms

Introduction to Cryptography with Coding Theory

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.

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.

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.

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.

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.

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.

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.

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.

McMillan's Converse

Any length vector satisfying Kraft has a prefix-free code. Here is the construction.

Kraft's Inequality

Which codeword-length vectors are achievable by prefix-free codes? Kraft's inequality is the answer.