Unary coding: Difference between revisions

Revision as of 04:23, 28 February 2013

Revision as of 21:56, 30 June 2013

Line 1:

'''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 both a [[Prefix-free code]] and a [[Self-synchronizing code]].

<table border="1" cellpadding="2">

Line 31:

for <math>n=1,2,3,...</math>. 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 code in use today==

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 code|prefix-free]], and can be uniquely decoded.

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 indicates the number of bytes in the sequence, so that the length of the sequence can be determined without examining the continuation bytes.

==See also==