Unary Coding Explained: How It Compares to Binary
This article provides a concise guide to unary coding, explaining its fundamental mechanics and mathematical structure. It breaks down how numbers are encoded using this tally-based method and provides a direct storage efficiency comparison against the standard positional binary number system, highlighting where unary fails for large data and where it excels in specialized compression algorithms.
How Unary Coding Works
Unary coding is a base-1 numeral system and a prefix code that represents a non-negative integer \(n\) by a sequence of \(n\) identical bits terminated by a single opposite bit. It functions like a digital tally mark system.
In standard implementation: * An integer \(n\) is written as \(n\) ones followed by a single zero (or alternatively, \(n\) zeros followed by a single one). * The terminating bit acts as a delimiter, making unary code self-delimiting. A decoder knows a number has ended the moment it reads the terminating bit, eliminating the need for fixed bit-widths or explicit separators.
Examples of Unary Encoding
| Integer (\(n\)) | Unary Code (Ones terminated by 0) | Total Bits |
|---|---|---|
| 0 | 0 |
1 bit |
| 1 | 10 |
2 bits |
| 2 | 110 |
3 bits |
| 3 | 1110 |
4 bits |
| 4 | 11110 |
5 bits |
| 10 | 11111111110 |
11 bits |
Mathematically, encoding any integer \(n \ge 0\) in unary requires exactly \(n + 1\) bits.
Storage Efficiency: Unary vs. Standard Binary
The standard binary number system is a base-2 positional notation system. The efficiency disparity between unary and binary comes down to linear vs. logarithmic growth.
Bit-Length Comparison
- Standard Binary: The number of bits required to store an integer \(n > 0\) is \(\lfloor \log_2(n) \rfloor + 1\). Its space complexity scales logarithmically: \(O(\log n)\).
- Unary Coding: The number of bits required to store an integer \(n\) is \(n + 1\). Its space complexity scales linearly: \(O(n)\).
Scalability Comparison
| Integer (\(n\)) | Standard Binary | Binary Bit Count | Unary Code Bit Count |
|---|---|---|---|
| 0 | 0 |
1 bit | 1 bit |
| 1 | 1 |
1 bit | 2 bits |
| 7 | 111 |
3 bits | 8 bits |
| 64 | 1000000 |
7 bits | 65 bits |
| 1,000 | 1111101000 |
10 bits | 1,001 bits |
| 1,000,000 | 11110100001001000000 |
20 bits | 1,000,001 bits |
For small values (\(0\) and \(1\)), unary coding is competitive or equivalent in size to binary. However, as values grow, unary coding quickly becomes exponentially worse in terms of storage efficiency. Storing a value of one million in binary takes less than 3 bytes of data, whereas in unary it takes approximately 122 kilobytes.
Where Unary Coding Is Used
Despite its extreme inefficiency for general data storage, unary coding is widely used in data compression when combined with entropy-based models.
- Geometric Distributions: Unary coding is mathematically optimal (equivalent to Huffman coding) when the probability of encountering an integer \(n\) follows a geometric distribution of \(P(n) = 2^{-(n+1)}\). If smaller numbers occur overwhelmingly more often than large numbers, unary coding produces minimal overhead.
- Hybrid Entropy Coders: Unary coding is a core
building block in variable-length codes such as:
- Golomb Coding: Divides numbers into a quotient (encoded in unary) and a remainder (encoded in truncated binary).
- Rice Coding: A power-of-two subset of Golomb coding used in lossless audio formats like FLAC.
- Exponential-Golomb Coding: Used extensively in modern video codecs, including H.264/MPEG-4 AVC and H.265/HEVC, to encode syntax elements and motion vectors.