Iwasawa algebra

2013-12-10T20:30:14Z

92.201.19.30: /* Iwasawa's theorem */

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 = http://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>

== Algorithm description ==

Given a [[Discrete random variable#Discrete probability distribution|discrete random variable]] ''X'' of [[Total order|ordered]] values to be encoded, let <math>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...</math>
::In binary, Z(A) = 0.'''001'''0101010...
::L(A) = <math>\left\lceil \log_2 \frac 1 \frac 1 3 \right\rceil + 1</math> = '''3'''
::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...</math>
::In binary, Z(B) = 0.'''011'''10101010101...
::L(B) = <math>\left\lceil \log_2 \frac 1 \frac 1 4 \right\rceil + 1</math> = '''3'''
::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...</math>
::In binary, Z(C) = 0.'''1010'''10101010...
::L(C) = <math>\left\lceil \log_2 \frac 1 \frac 1 6 \right\rceil + 1</math> = '''4'''
::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'''
::L(D) = <math>\left\lceil \log_2 \frac 1 \frac 1 4 \right\rceil + 1</math> = '''3'''
::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>bcode(x) \le bcode(y) < 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|"CDF"|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) - 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>bcode(y) - 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 \epsilon X}p(x)L(x) = \sum_{x \epsilon X}p(x)(\left\lceil \log_2 \frac {1}{p(x)} \right\rceil + 1)</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.

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

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

formulasearchengine - User contributions [en]

Iwasawa algebra