Unary coding
Encyclopedia
Unary coding, sometimes called thermometer code, 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.
Unary coding is an optimally efficient encoding for the following discrete probability distribution
for
.
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
. Although it is the optimal symbol-by-symbol coding for such probability distributions, Golomb coding
achieves better compression capability for the geometric distribution because it does not consider input symbols independently, but rather implicitly groups the inputs. For the same reason, arithmetic encoding performs better for general probability distributions, as in the last case above.
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.
Entropy encoding
In information theory an entropy encoding is a lossless data compression scheme that is independent of the specific characteristics of the medium....
that represents a natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
, 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
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
for
.In symbol-by-symbol coding, it is optimal for any geometric distribution
for which k ≥ φ = 1.61803398879…, the golden ratio
Golden ratio
In mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989...
, or, more generally, for any discrete distribution for which
for
. Although it is the optimal symbol-by-symbol coding for such probability distributions, Golomb codingGolomb coding
Golomb coding is a lossless data compression method using a family of data compression codes invented by Solomon W. Golomb in the 1960s. Alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb coding highly suitable for situations in which the...
achieves better compression capability for the geometric distribution because it does not consider input symbols independently, but rather implicitly groups the inputs. For the same reason, arithmetic encoding performs better for general probability distributions, as in the last case above.
A modified unary encoding is used in UTF-8
UTF-8
UTF-8 is a multibyte character encoding for Unicode. Like UTF-16 and UTF-32, UTF-8 can represent every character in the Unicode character set. Unlike them, it is backward-compatible with ASCII and avoids the complications of endianness and byte order marks...
. Unary codes are also used in split-index schemes like the Golomb Rice code. Unary coding is prefix-free, and can be uniquely decoded.