Unary coding: Difference between revisions

Revision as of 12:29, 21 February 2007

Revision as of 12:50, 21 February 2007

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. The ones and 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>\operatorname{P}(n) = 2^{-n}\,</math>

Line 9:

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

for which ''k'' &ge; &phi; = 1.61803398879&hellip;, the [[golden ratio]], or, more generally, for any discrete distribution for which

:<math>\operatorname{P}(n) \ge \operatorname{P}(n+1) + \operatorname{P}(n+2)\, </math>

Line 15:

for <math>n=1,2,3,...</math>.

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.

==References==

*Khalid Sayood, ''Data Compression'', 3rd ed, Morgan Kaufmann.

*Professor K.R Rao, EE5359:''Principles of Digital Video Coding''.

[[Category:Coding theory]]

[[Category:Data compression]]

[[Category:Lossless compression algorithms]]