Unary coding

Unary coding is an entropy encoding that represents a natural number, n, with n ones followed by a zero (if natural number is understood as non-negative integer) or with n − 1 ones followed by a zero (if natural number is understood as strictly positive integer). For example 5 is represented as 111110 or 11110. Some representations use n or n − 1 zeros followed by a one. The ones and zeros are interchangeable without loss of generality.

n (non-negative)	n (strictly positive)	Unary code	Alternative
0	1	0	1
1	2	10	01
2	3	110	001
3	4	1110	0001
4	5	11110	00001
5	6	111110	000001
6	7	1111110	0000001
7	8	11111110	00000001
8	9	111111110	000000001
9	10	111111110	0000000001

Unary coding is an optimally efficient encoding for the following discrete probability distribution

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

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

In symbol-by-symbol coding, it is optimal for any geometric distribution

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

for which k ≥ φ = 1.61803398879…, the golden ratio, or, more generally, for any discrete distribution for which

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

for ${\displaystyle n=1,2,3,...}$. Although it is the optimal symbol-by-symbol coding for such probability distributions, its optimality can, like that of Huffman coding, be over-stated. Arithmetic coding has better compression capability for the last two distributions mentioned above because it does not consider input symbols independently, but rather implicitly groups the inputs.

A modified unary encoding is used in UTF-8. Unary codes are also used in split-index schemes like the Golomb Rice code. Unary coding is prefix-free, and can be uniquely decoded.

See also

• Thermometer code

References

• Khalid Sayood, Data Compression, 3rd ed, Morgan Kaufmann.
• Professor K.R Rao, EE5359:Principles of Digital Video Coding.