World Library  
Flag as Inappropriate
Email this Article

Shannon–Fano–Elias coding

Article Id: WHEBN0031785457
Reproduction Date:

Title: Shannon–Fano–Elias coding  
Author: World Heritage Encyclopedia
Language: English
Subject: Shannon–Fano coding, Context tree weighting, Warped linear predictive coding, Log area ratio, Smart Bitrate Control
Collection: Lossless Compression Algorithms
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Shannon–Fano–Elias coding

In information theory, Shannon–Fano–Elias coding is a precursor to arithmetic coding, in which probabilities are used to determine codewords.[1]

Contents

  • Algorithm description 1
    • Example 1.1
  • Algorithm analysis 2
    • Prefix code 2.1
    • Code length 2.2
  • References 3

Algorithm description

Given a discrete random variable X of ordered values to be encoded, let p(x) be the probability for any x in X. Define a function

\bar F(x) = \sum_{x_i < x}p(x_i) + \frac 12 p(x)

Algorithm:

For each x in X,
Let Z be the binary expansion of \bar F(x).
Choose the length of the encoding of x, L(x), to be the integer \left\lceil \log_2 \frac {1}{p(x)} \right\rceil + 1
Choose the encoding of x, code(x), be the first L(x) most significant bits 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
\bar F(A) = \frac 12 p(A) = \frac 12 \cdot \frac 13 = 0.1666...
In binary, Z(A) = 0.0010101010...
L(A) = \left\lceil \log_2 \frac 1 \frac 1 3 \right\rceil + 1 = 3
code(A) is 001
For B
\bar F(B) = p(A) + \frac 12 p(B) = \frac 13 + \frac 12 \cdot \frac 14 = 0.4583333...
In binary, Z(B) = 0.01110101010101...
L(B) = \left\lceil \log_2 \frac 1 \frac 1 4 \right\rceil + 1 = 3
code(B) is 011
For C
\bar F(C) = p(A) + p(B) + \frac 12 p(C) = \frac 13 + \frac 14 + \frac 12 \cdot \frac 16 = 0.66666...
In binary, Z(C) = 0.101010101010...
L(C) = \left\lceil \log_2 \frac 1 \frac 1 6 \right\rceil + 1 = 4
code(C) is 1010
For D
\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
In binary, Z(D) = 0.111
L(D) = \left\lceil \log_2 \frac 1 \frac 1 4 \right\rceil + 1 = 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

bcode(x) \le bcode(y) < bcode(x) + 2^{-L(x)}

then all the codes form a prefix code.

By comparing F to the CDF of X, this property may be demonstrated graphically for Shannon–Fano–Elias coding.

The relation of F to the CDF of X

By definition of L it follows that

2^{-L(x)} \le \frac 12 p(x)

And because the bits after L(y) are truncated from F(y) to form code(y), it follows that

\bar F(y) - bcode(y) \le 2^{-L(y)}

thus bcode(y) must be no less than CDF(x).

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

Code length

The average code length is 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).
Thus for H(X), the Entropy of the random variable X,

H(X) + 1 \le LC(X) < H(X) + 2

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

  1. ^ T. M. Cover and Joy A. Thomas (2006). Elements of information theory (2nd ed.). John Wiley and Sons. pp. 127–128.  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.