 #jsDisabledContent { display:none; } My Account | Register | Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

# Shannon–Fano–Elias coding

Article Id: WHEBN0031785457
Reproduction Date:

 Title: Shannon–Fano–Elias coding Author: World Heritage Encyclopedia Language: English Subject: 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.

## 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.

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.

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.