#informationtheory

The series closes by restating the codes-as-priors thesis across all twelve instances and connecting the wire-format side to the Stepanov type-algebra side.

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.

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.

Cryptographic theory assumes random oracles with infinite output. We have 256 bits. This paper explores how we bridge that gap, and what it means that we can.

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.

The problem of predicting what comes next, from compression to language models

Solomonoff induction, MDL, speed priors, and neural networks are all special cases of one Bayesian framework with four knobs.

Prefix-freeness is the property that lifts the free-monoid construction into bit space.

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.

Codecs are not ad-hoc bit formats. They are constructions on the algebraic structure of types.

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

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.