Unary coding: Difference between revisions

Revision as of 21:56, 30 June 2013

Revision as of 01:11, 11 February 2014

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]].

{| class="wikitable"

<tr><th>! n (non-negative)<th> !! n (strictly positive)<th> !! Unary code<th> !! Alternative

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

|-

<tr><th>n (non-negative)<th>n (strictly positive)<th>Unary code<th>Alternative

| 0 || 1 || 0 || 1

<tr><td>0<td>1<td>0<td>1

|-

<tr><td>1<td>2<td>10<td>01

| 1 || 2 || 10 || 01

<tr><td>2<td>3<td>110<td>001

|-

<tr><td>3<td>4<td>1110<td>0001

| 2 || 3 || 110 || 001

<tr><td>4<td>5<td>11110<td>00001

|-

<tr><td>5<td>6<td>111110<td>000001

| 3 || 4 || 1110 || 0001

<tr><td>6<td>7<td>1111110<td>0000001

|-

<tr><td>7<td>8<td>11111110<td>00000001

| 4 || 5 || 11110 || 00001

<tr><td>8<td>9<td>111111110<td>000000001

|-

<tr><td>9<td>10<td>1111111110<td>0000000001

<tr><td>| 5<td> || 6<td> || 111110<td> || 000001

</table>

|-

<tr><td>| 6<td> || 7<td> || 1111110<td> || 0000001

|-

<tr><td>| 7<td> || 8<td> || 11111110<td> || 00000001

|-

<tr><td>| 8<td> || 9<td> || 111111110<td> || 000000001

|-

<tr><td>| 9<td> || 10<td> || 1111111110<td> || 0000000001

|}

Unary coding is an optimally efficient encoding for the following discrete [[probability distribution]]