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 | 1111111110 | 0000000001 |
Unary coding is an optimally efficient encoding for the following discrete probability distribution
for n = 1,2,3,....
In symbol-by-symbol coding, it is optimal for any geometric distribution
for which k ≥ φ = 1.61803398879…, the golden ratio, or, more generally, for any discrete distribution for which
for 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
References
- Khalid Sayood, Data Compression, 3rd ed, Morgan Kaufmann.
- Professor K.R Rao, EE5359:Principles of Digital Video Coding.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
