Unary coding, or the unary numeral system, is an entropy encoding that represents a natural number, , with ones followed by a zero (if the term natural number is understood as non-negative integer) or with ones followed by a zero (if the term natural number is understood as strictly positive integer). A unary number's code length would thus be with that first definition, or with that second definition. Unary code when vertical behaves like mercury in a thermometer that gets taller or shorter as n gets bigger or smaller, and so is sometimes called thermometer code. An alternative representation uses or zeros followed by a one, effectively swapping the ones and zeros, without loss of generality. For example, the first ten unary codes are: Unary code Alternativen (non-negative)n (strictly positive) 0 101 10 0112 110 00123 1110 000134 11110 0000145 111110 00000156 1111110 000000167 11111110 0000000178 111111110 00000000189 1111111110 0000000001910
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 , 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.
Unary coding is both a prefix-free code and a self-synchronizing code.
Unary code in use today Examples of unary code uses include: In Golomb Rice code, unary encoding is used to encode the quotient part of the Golomb code word. In UTF-8, unary encoding is used in the leading byte of a multi-byte sequence to indicate the number of bytes in the sequence so that the length of the sequence can be determined without examining the continuation bytes. Instantaneously trained neural networks use unary coding for efficient data representation.
Unary coding in biological networks Unary coding is used in the neural circuits responsible for birdsong production. The nucleus in the brain of the songbirds that plays a part in both the learning and the production of bird song is the HVC (high vocal center). The command signals for different notes in the birdsong emanate from different points in the HVC. This coding works as space coding which is an efficient strategy for biological circuits due to its inherent simplicity and robustness.
Standard run-length unary codes All binary data is defined by the ability to represent unary numbers in alternating run-lengths of 1s and 0s. This conforms to the standard definition of unary i.e. digits of the same number 1 or 0. All run-lengths by definition have at least one digit and thus represent strictly positive integers. RL code Next code 1 1 0 2 11 00 3 111 000 4 1111 0000 5 11111 00000 6 111111 000000 7 1111111 0000000 8 11111111 00000000 9 111111111 000000000 10 1111111111 0000000000 ... These codes are guaranteed to end validly on any length of data (when reading arbitrary data) and in the (separate) write cycle allow for the use and transmission of an extra bit (the one used for the first bit) while maintaining overall and per-integer unary code lengths of exactly .
Uniquely decodable non-prefix unary codes Following is an example of uniquely decodable unary codes that is not a prefix code and is not instantaneously decodable (need look-ahead to decode) Unary code Alternative 1 1 0 2 10 01 3 100 011 4 1000 0111 5 10000 01111 6 100000 011111 7 1000000 0111111 8 10000000 01111111 9 100000000 011111111 10 1000000000 0111111111 ... These codes also (when writing unsigned integers) allow for the use and transmission of an extra bit (the one used for the first bit). Thus they are able to transmit integers * unary bits and 1 additional bit of information within bits of data.
Symmetric unary codes The following symmetric unary codes can be read and instantaneously decoded in either direction: Unary code Alternative (non-negative) (strictly positive) 1 001 00 1112 010 10123 0110 100134 01110 1000145 011110 10000156 0111110 100000167 01111110 1000000178 011111110 10000000189 0111111110 1000000001910... These codes have a unique property wherein if one were to scan data (1s and 0s) of any probability distribution for symmetric unary codes, the average length of the scanned symmetric unary code is always around 2. This can help with timing concerns as almost every protocol has to put in checks and balances for continuous streams of low entropy data which can damage components like USB peripherals etc.
Canonical unary codes For unary values where the maximum length is known, one can use canonical unary codes that are of a somewhat numerical nature and different from character based codes. The largest length is known, numerical 0 (in bijective) or -1 (in bijective) is assigned as the boundary condition equivalent to repeating a digit the maximum number of times, then for each step reducing the number of digits by one and increasing/decreasing the result by numerical 1. Unary code BijectiveStandard BijectiveAlternativeBijectiveStandard Bijective 1 1 221101122 2 01 12411310215226 3 001 112811171102211322214 4 0001 1112161111151110222129222230 5 00001 111123211111311111022221612222262 6 000001 1111126411111163111110222221125222222126 7 0000001 11111121281111111127111111022222212532222222254 8 00000001 1111111225611111111255111111102222222150922222222510 9 000000001 11111111251211111111151111111111022222222110212222222221022 10 0000000000111111111110231111111111102311111111112222222222204622222222222046 Canonical codes (different from Canonical Huffman Code where only the code book is discussed) require less processing time to decode, canonical being a term used to imply use of any method, numerical in nature here, ie when they are processed as numbers not a string. If the number of codes required per symbol length is different to 1, i.e. there are more non-unary codes of some length required, those would be achieved by increasing/decreasing the values numerically without reducing the length. In order to obtain a set of codes of certain length, you have to start with the boundary condition usually 0....0 for the largest and last code and work upwards, increasing the value numerically till the number of codes of a certain length are exhausted, then chopping a number of bits from the right and numerically increasing the remaining number by 1 to get the first number of the next range (set of numbers belonging to a certain length) and so on from largest length to smallest length.
One can also start from the smallest length (and give it a numerical value of the largest boundary condition, like 1 in binary or 2 in bijective), and working downwards reducing the value numerically by 1 for each new code of the same length, OR (reducing value numerically by 1 AND increasing the length) (appending 2 or 22 etc or setting lower limit of new range to (binary) or (bijective) or (binary with increase of 2 bits for the next set) or (bijective with increase of 2 bits for the next set) etc. This allows you to construct codes without knowing the frequency prior. You can choose to increase the next set by 2 bits instead of 1 to fit 3 new symbols and 1 for the possibility of new symbols, or 2 new symbols and 2 for unknown symbols to contain code lengths, because if you reach the lowest boundary condition numerically, you cannot add any more symbols.
Both these methods can be used to create canonical (numerical) codes same in length to any Huffman code set (limited in length and code size) and the small to large method can be used for any Huffman or non Huffman, limited or arbitrary length codeset. The advantage being that the parser is then numerical instead of character based. Refer paper for comparing the number of 'memory accesses'.
Goldbach Biunary codes Goldbach Biunary codes (or Goldbach G0 code lookalikes) are two unary codes appended together that can represent non trivial fractions (which don't amount to 0 or 1). The length of the first unary represents the numerator and the total length of the two unary codes () represents the denominator, hence the total number of bits required to represent the entire fraction is the base itself and the total number of bits required to represent any denominator is 1. CodeValue 111/2 1011/3 0112/3 10011/4 01012/4 00113/4 100011/5 010012/5 001013/5 000114/5...
Normally the base is omitted on a per digit basis for number representation because it is assumed that all digits are in a certain base, but all numbers can be represented in variable base format where each digit is of a different base. These were used in the past as multilingual numbers or for solving sudoku puzzles where only changing the base from digit to digit could solve them. This is understood intuitively for decimal numbers between 0 and 1 which are sums of fractions, but is not commonly used or known for integers > 0. Thus representing the denominator or base (usually a subscript written beside the entire number) becomes a matter of writing the base in subscript for each digit or using Goldbach biunary codes.
N ( Integer >= 0 ) = Ax + By + Cz ; ( A,B,C >= 0 and < x,y,z ) or ( A,B,C > 0 and <= x,y,z for bijective notation )
M ( Decimal float < 1 and > 0 ) = A/x + B/y + C/z ; ( A,B,C > 0 and < x,y,z and x < y < z for non trivial fractions )
where each digit in base n reduces the search space to 1/n and the remainder is a matter of subtracting the exact fraction and continuing with the operation.
Do note that in the M (decimal float) variation of this method, all digits are fractions that add up to M, so multiplying two decimal numbers stored in this representation is a matter of running DIGIT_COUNT1 x DIGIT_COUNT2 small multiplications in parallel in any order and adding the values. Or one can choose to store the
NUMERATOR1*NUMERATOR2/DENOMINATOR2*DENOMINATOR2
format and not conducting the operation till the value is required. Or pre-compute the possible operations and do no operations at all if the maximum number of digits / precision is limited to say around 64 bits.
This allows integer math to be used for floating point numbers and arbitrary precision floats. Further since the use of random denominators to approximately represent the decimal part of a float is an involved process ( and representing them with n bits would be cumbersome), this method lends itself to small denominators, one can simply have sequences of increasing denominators, where you start:
O ( Decimal float < 1 and > 0 ) = A/x , B/x , C/y , D/z , E/z ; ( A,B,C,D,E > 0 and < x,y,z and x < y < z for non trivial fractions )
gaining some storage space but having a power operation and losing some parallelism.