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. The ones and zeros are interchangeable without loss of generality.

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,...}$.

When comparing only the subset of encoders with an integer number of symbols in the output code, 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,...}$.

Note that these two distributions can be encoded more efficiently with arithmetic coding (by allocating a non-integer number of symbols per code), so unary encoding is not optimally efficient for these distributions according to Shannon's source coding theorem.

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.

References

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