Unary coding

Unary coding, or the <a href="/facts/Unary_numeral_system/J37tMmyW">unary numeral system</a> and also sometimes called thermometer code, is an <a href="/facts/Entropy_encoding/44I0n8F8">entropy encoding</a> that represents a <a href="/facts/Natural_number/u65og8JE">natural number</a>, n, with a code of length n + 1 ( or n ), usually 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 <a href="/facts/Without_loss_of_generality/gVP4dmEe">without loss of generality</a>. Unary coding is both a <a href="/facts/Prefix-free_code/461neBYx">prefix-free code</a> and a <a href="/facts/Self-synchronizing_code/5SJJwxAK">self-synchronizing code</a>.

<table><tbody><tr><th>n (non-negative)</th><th>n (strictly positive)</th><th>Unary code</th><th>Alternative</th></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>1</td><td>2</td><td>10</td><td>01</td></tr><tr><td>2</td><td>3</td><td>110</td><td>001</td></tr><tr><td>3</td><td>4</td><td>1110</td><td>0001</td></tr><tr><td>4</td><td>5</td><td>11110</td><td>00001</td></tr><tr><td>5</td><td>6</td><td>111110</td><td>000001</td></tr><tr><td>6</td><td>7</td><td>1111110</td><td>0000001</td></tr><tr><td>7</td><td>8</td><td>11111110</td><td>00000001</td></tr><tr><td>8</td><td>9</td><td>111111110</td><td>000000001</td></tr><tr><td>9</td><td>10</td><td>1111111110</td><td>0000000001</td></tr></tbody></table>
Unary coding is an optimally efficient encoding for the following discrete <a href="/facts/Probability_distribution/EpsKKVRu">probability distribution</a>

P
        ⁡
        (
        n
        )
        =
        
          2
          
            −
            n
          
        
        
      
    
    {\displaystyle \operatorname {P} (n)=2^{-n}\,}

for 
 
 
 
 n
 =
 1
 ,
 2
 ,
 3
 ,
 .
 .
 .
 
 
 {\displaystyle n=1,2,3,...}
 
.
In symbol-by-symbol coding, it is optimal for any <a href="/facts/Geometric_distribution/c8wjfaoV">geometric distribution</a>

P
        ⁡
        (
        n
        )
        =
        (
        k
        −
        1
        )
        
          k
          
            −
            n
          
        
        
      
    
    {\displaystyle \operatorname {P} (n)=(k-1)k^{-n}\,}

for which k ≥ φ = 1.61803398879..., the <a href="/facts/Golden_ratio/anloSRmD">golden ratio</a>, or, more generally, for any discrete distribution for which

P
        ⁡
        (
        n
        )
        ≥
        P
        ⁡
        (
        n
        +
        1
        )
        +
        P
        ⁡
        (
        n
        +
        2
        )
        
      
    
    {\displaystyle \operatorname {P} (n)\geq \operatorname {P} (n+1)+\operatorname {P} (n+2)\,}

for 
 
 
 
 n
 =
 1
 ,
 2
 ,
 3
 ,
 .
 .
 .
 
 
 {\displaystyle n=1,2,3,...}
 
. Although it is the optimal symbol-by-symbol coding for such probability distributions, <a href="/facts/Golomb_coding/bUyW4uLN">Golomb coding</a> 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, <a href="/facts/Arithmetic_encoding/WU0H4oNu">arithmetic encoding</a> performs better for general probability distributions, as in the last case above.

Unary coding open-in-new

Unary coding