Shannon-Fano-Elias and Interval Coding

Interval Coding

Modified Cumulative Distribution Function

Given a discrete probability distribution $\{p_i\}$, we define the modified cumulative distribution function as: ${\bar{F}}_i={\sum }_{j=1}^{i-1}{p}_j+\frac{1}{2}{p}_i=F_i-\frac{1}{2}{p}_i$where $F_i={\sum }_{j=1}^i{p}_j$ is the usual cumulative distribution function.

Shannon-Fano-Elias Coding

For each outcome $a_i$,

1. Calculate the value of modified cumulative distribution function ${\bar{F}}_i$.
2. Calculate the length of the required binary string $\ell (a_i)=\lceil {\log }_2\frac{1}{p_i}\rceil +1$.
3. Convert the value to binary $[{\bar{F}}_i{]}_2$.
4. Trim the binary string to the required length $\ell (a_i)$, assign the trimmed binary string to the outcome $a_i$ as its codeword.

e.g. Suppose $X$ has outcomes $(a_1,a_2,a_3,a_4)$ and probabilities $\left(\frac{2}{9},\frac{1}{9},\frac{1}{3},\frac{1}{3}\right)$. Then we have the following table:

$x$	$p(x)$	$F(x)$	$\bar{F}(x)$	$[\bar{F}(x){]}_2$	$\ell (x)$
$a_1$	$\frac{2}{9}$	$\frac{2}{9}$	$\frac{1}{9}$	$0.\overline{000111}$	4
$a_2$	$\frac{1}{9}$	$\frac{1}{3}$	$\frac{5}{18}$	$0.01\overline{000111}$	5
$a_3$	$\frac{1}{3}$	$\frac{2}{3}$	$\frac{1}{2}$	$0.1$	3
$a_4$	$\frac{1}{3}$	$1$	$\frac{5}{6}$	$0.1\overline{10}$	3

Therefore we have the code $C=\{0001,01000,100,110\}$.

Lossless Property

Proposition

The Shannon-Fano-Elias code is lossless.

Proof Denote the Shannon-Fano-Elias code as $\lfloor {\bar{F}}_i{\rfloor }_{{\ell }_i}$ for the $i$th outcome $x_i\in X$. Then we have $F_{i-1}<\lfloor {\bar{F}}_i{\rfloor }_{{\ell }_i}<F_i$That is the codeword lies entirely in the interval between $i-1$ and $i$, and these intervals are disjoint. Therefore, the code is lossless. $\square$

Prefix Property

Proposition

Shannon-Fano-Elias code is prefix free.

Proof According to the previous argument, we know that $\lfloor {\overline{F}}_i{\rfloor }_{{\ell }_i}>F_{i-1}$. Additionally, $\lfloor {\bar{F}}_i{\rfloor }_{{\ell }_i}+\frac{1}{2^{\ell }}\le {\bar{F}}_i+\frac{1}{2^{\ell }}\le {\bar{F}}_i+\frac{p_i}{2}=F_i$Hence $\left[\lfloor {\bar{F}}_i{\rfloor }_{{\ell }_i},\lfloor {\bar{F}}_i{\rfloor }_{{\ell }_i}+\frac{1}{2^{\ell }}\right)\subset [F_{i-1},F_i)$The intervals for each codeword are thus trivially disjoint, since we know each of the $[F_{i-1}{F}_i)$ interval is disjoint, thus the code is prefix free. $\square$

Shannon-Fano-Elias Decoding

Shannon-Fano-Elias Decoding

To decode a given bitstring,

1. start with the first bit, compute the corresponding binary interval;
2. if the interval is strictly contained within that of a codeword:
3. output the corresponding outcome
4. skip over any redundant bits for this codeword
5. repeat the process with the remaining bits
6. otherwise include next bit and compute the corresponding interval.

e.g. Suppose we have $\mathcal{A}=({\text{a}}_1,{\text{a}}_2,{\text{a}}_3,{\text{a}}_4)$ with $p=\left(\frac{2}{9},\frac{1}{9},\frac{1}{3},\frac{1}{3}\right)$ and we want to decode $01000$: We could actually stop the process once we see $0100$ since $[0.25,0.3125)\subset [0.22,0.33]$.

Expected Length

Theorem

The expected length of a Shannon-Fano-Elias code $C$ on ensemble $X$ satisfies: $H(X)+1\le L(C,X)\le H(X)+2.$

Proof $L(C,X)={\sum }_{i=1}^n{p}_i\ell (a_i)={\sum }_{i=1}^n{p}_i\left(\lceil {\log }_2\frac{1}{p_i}\rceil +1\right)\le {\sum }_{i=1}^n{p}_i\left({\log }_2\frac{1}{p_i}+2\right)=H(X)+2$The lower bound is similarly obtained.