Shannon–Fano–Elias coding

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

F ¯ ( x ) = ∑ x i < x p ( x i ) + 1 2 p ( x )

Algorithm:

For each x in X, Let Z be the binary expansion of F ¯ ( x ) . Choose the length of the encoding of x, L ( x ) , to be the integer ⌈ log 2 ⁡ 1 p ( x ) ⌉ + 1 Choose the encoding of x, c o d e ( 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 For B For C For D

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

b c o d e ( x ) ≤ b c o d e ( y ) < b c o d e ( 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 ) ≤ 1 2 p ( x )

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

F ¯ ( y ) − b c o d e ( y ) ≤ 2 − L ( y )

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

So the above graph demonstrates that the b c o d e ( y ) − b c o d e ( x ) > p ( x ) ≥ 2 − L ( x ) , therefore the prefix property holds.

Code length

The average code length is L C ( X ) = ∑ x ϵ X p ( x ) L ( x ) = ∑ x ϵ X p ( x ) ( ⌈ log 2 ⁡ 1 p ( x ) ⌉ + 1 ) .
Thus for H(X), the Entropy of the random variable X,

H ( X ) + 1 ≤ L C ( 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.