Unary coding: Difference between revisions

Revision as of 05:34, 6 July 2006

Revision as of 00:19, 20 July 2006

Line 1:

'''Unary coding''' is an [[entropy encoding]] that represents a [[Natural number]], ''n'', with ''n-1'' ones followed by a zero. For example 5 is represented as 11110. Some representations use ''n'' ones followed by a zero. Also the use of ones & zeros are interchangeable without loss of generality.

Unary coding is easily shown to be an optimally efficient encoding for the following discrete [[probability distribution]]:

:<math>P(n) = 2^{-n}\,</math>

for <math>n=1,2,3,...</math>. It is in fact optimal for any [[geometric distribution]]

For n=1,2,3,...

:<math>P(n) = (k-1)k^{-n}\,</math>

for which <math>k \ge \varphi \approx 1.618 033 989</math>, the [[golden ratio]].

A modified unary encoding is used in [[UTF-8]].