View source for Shannon–Fano–Elias coding

{{Short description|Algorithm for binary prefix code}}
{{Refimprove|date=April 2016}}
In [[information theory]], '''Shannon–Fano–Elias coding''' is a precursor to [[arithmetic coding]], in which probabilities are used to determine codewords.<ref>
{{cite book
 | url = https://books.google.com/books?id=0QuawYmc2pIC&pg=PA127
 | title = Elements of information theory
 | author = T. M. Cover and Joy A. Thomas
 | edition = 2nd
 | publisher = John Wiley and Sons
 | year = 2006
 | pages = 127–128
 | isbn = 978-0-471-24195-9
 }}</ref> It is named for [[Claude Shannon]], [[Robert Fano]], and [[Peter Elias]].

== Algorithm description ==

Given a [[Discrete random variable#Discrete probability distribution|discrete random variable]] ''X'' of [[Total order|ordered]] values to be encoded, let <math alt="p(x)">p(x)</math> be the probability for any ''x'' in ''X''.  Define a function 
:<math>\bar F(x) = \sum_{x_i < x}p(x_i) + \frac 12 p(x)</math>

Algorithm:
:For each ''x'' in ''X'',
::Let ''Z'' be the binary expansion of <math>\bar F(x)</math>.
::Choose the length of the encoding of ''x'', <math>L(x)</math>, to be the integer <math>\left\lceil \log_2 \frac {1}{p(x)} \right\rceil + 1</math>
::Choose the encoding of ''x'', <math>code(x)</math>, be the first <math>L(x)</math> [[most significant bit]]s after the decimal point of ''Z''.

=== Example ===

Let ''X'' = {''A'', ''B'', ''C'', ''D''}, with probabilities ''p'' = {1/3, 1/4, 1/6, 1/4}.
:For ''A''
::<math>\bar F(A) = \frac 12 p(A) = \frac 12 \cdot \frac 13 = 0.1666\ldots</math>
::In binary, ''Z''(''A'') = 0.'''001'''0101010...
::<math> L(A) = \left\lceil \log_2 \frac 1 \frac 1 3 \right\rceil + 1 = \mathbf 3</math>
::code(''A'') is 001

:For ''B''
::<math>\bar F(B) = p(A) + \frac 12 p(B) = \frac 13 + \frac 12 \cdot \frac 14 = 0.4583333\ldots</math>
::In binary, ''Z''(''B'') = 0.'''011'''10101010101...
::<math> L(B) = \left\lceil \log_2 \frac 1 \frac 1 4 \right\rceil + 1 = \mathbf 3</math>
::code(''B'') is 011

:For ''C''
::<math>\bar F(C) = p(A) + p(B) + \frac 12 p(C) = \frac 13 + \frac 14 + \frac 12 \cdot \frac 16 = 0.66666\ldots</math>
::In binary, ''Z''(''C'') = 0.'''1010'''10101010...
::<math> L(C) = \left\lceil \log_2 \frac 1 \frac 1 6 \right\rceil + 1 = \mathbf 4</math>
::code(''C'') is 1010

:For ''D''
::<math>\bar F(D) = p(A) + p(B) + p(C) + \frac 12 p(D) = \frac 13 + \frac 14 + \frac 16 + \frac 12 \cdot \frac 14 = 0.875</math>
::In binary, Z(D) = 0.'''111'''
::<math>L(D) = \left\lceil \log_2 \frac 1 \frac 1 4 \right\rceil + 1 = \mathbf 3 </math>
::code(''D'') is 111

==Algorithm analysis==

===Prefix code===
Shannon–Fano–Elias coding produces a binary [[prefix code]], allowing for direct decoding.

Let bcode(''x'') be the rational number formed by adding a decimal point before a binary code.  For example, if code(''C'') = 1010 then bcode(''C'') = 0.1010.  For all ''x'', if no ''y'' exists such that 
:<math> \operatorname{bcode}(x) \le \operatorname{bcode}(y) < \operatorname{bcode}(x) + 2^{-L(x)}</math>
then all the codes form a prefix code.

By comparing ''F'' to the [[Cumulative distribution function|CDF]] of ''X'', this property may be demonstrated graphically for Shannon–Fano–Elias coding.

[[File:Shannon fano elias cdf graph.jpg|The relation of ''F'' to the CDF of ''X'']]

By definition of ''L'' it follows that 
: <math>2^{-L(x)} \le \frac 12 p(x)</math>
And because the bits after ''L''(''y'') are truncated from ''F''(''y'') to form code(''y''), it follows that
: <math>\bar F(y) - \operatorname{bcode}(y) \le 2^{-L(y)}</math>
thus bcode(''y'') must be no less than CDF(''x'').

So the above graph demonstrates that the <math>\operatorname{bcode}(y) - \operatorname{bcode}(x) > p(x) \ge 2^{-L(x)}</math>, therefore the prefix property holds.

===Code length===

The average code length is 
<math>LC(X) = \sum_{x \in X}p(x)L(x) = \sum_{x \in X}p(x) \left(\left\lceil \log_2 \frac {1}{p(x)} \right\rceil + 1\right)</math>.<br />
Thus for ''H''(''X''), the [[Entropy (information theory)|entropy]] of the random variable ''X'',
:<math>H(X) + 1 \le LC(X) < H(X) + 2</math>
Shannon Fano Elias codes from 1 to 2 extra bits per symbol from ''X'' than entropy, so the code is not used in practice.

== See also ==

* [[Shannon–Fano coding]]

==References==
{{reflist}}
{{Compression Methods}}

{{DEFAULTSORT:Shannon-Fano-Elias coding}}
[[Category:Lossless compression algorithms]]