Unary coding

Unary coding is an entropy encoding that represents a Natural number, n, with n-1 ones followed by a zero. For example 5 is represented as 11110. Some representations use n ones followed by a zero. Also the use of ones & zeros are interchangeable without loss of generality.

Unary coding is easily shown to be an optimally efficient encoding for the following discrete probability distribution

${\displaystyle P(n)=2^{-n}\,}$

for ${\displaystyle n=1,2,3,...}$. It is in fact optimal for any geometric distribution

${\displaystyle P(n)=(k-1)k^{-n}\,}$

for which ${\displaystyle k\geq \varphi \approx 1.618033989}$, the golden ratio, or, more generally, any distribution for which

${\displaystyle P(n)\geq P(n+1)+P(n+2)\,}$

for ${\displaystyle n=1,2,3,...}$.

A modified unary encoding is used in UTF-8.