Algorithm for binary prefix code
In information theory, Shannon–Fano–Elias coding is a precursor to arithmetic coding, in which probabilities are used to determine codewords.[1] It is named for Claude Shannon, Robert Fano, and Peter Elias.
Algorithm description
[edit]
Given a discrete random variable X of ordered values to be encoded, let
be the probability for any x in X. Define a function
![{\displaystyle {\bar {F}}(x)=\sum _{x_{i}<x}p(x_{i})+{\frac {1}{2}}p(x)}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9lZTc0ODkzZWY5Y2M4YzZlNjFmNDViYmUxMjU4NmUwOTljM2M3YjAx&__proxy_form=0)
Algorithm:
- For each x in X,
- Let Z be the binary expansion of
.
- Choose the length of the encoding of x,
, to be the integer ![{\displaystyle \left\lceil \log _{2}{\frac {1}{p(x)}}\right\rceil +1}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy84Njc2YzE4ODE5YTU4OGMxMDQ5YzBmN2UzYWIyODU5ZTM4NzVhNWFh&__proxy_form=0)
- Choose the encoding of x,
, be the first
most significant bits after the decimal point of Z.
Let X = {A, B, C, D}, with probabilities p = {1/3, 1/4, 1/6, 1/4}.
- For A
![{\displaystyle {\bar {F}}(A)={\frac {1}{2}}p(A)={\frac {1}{2}}\cdot {\frac {1}{3}}=0.1666\ldots }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8yMWFkYmQ5YTM5NTExYTQ3YzkwZjcxZTNiMGY1ZjY0NmQ4MDkxODEx&__proxy_form=0)
- In binary, Z(A) = 0.0010101010...
![{\displaystyle L(A)=\left\lceil \log _{2}{\frac {1}{\frac {1}{3}}}\right\rceil +1=\mathbf {3} }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy85YmI2YWFhOTc5NmM5NDE4YmQxMTcxYjZjM2YxMjI0MGMyNmMyNWZm&__proxy_form=0)
- code(A) is 001
- For B
![{\displaystyle {\bar {F}}(B)=p(A)+{\frac {1}{2}}p(B)={\frac {1}{3}}+{\frac {1}{2}}\cdot {\frac {1}{4}}=0.4583333\ldots }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8wMTIwZmY4OTNmNmJhMTA1ZDc1ODEzNmJmY2RlNjdlNmRjZmY3ODg4&__proxy_form=0)
- In binary, Z(B) = 0.01110101010101...
![{\displaystyle L(B)=\left\lceil \log _{2}{\frac {1}{\frac {1}{4}}}\right\rceil +1=\mathbf {3} }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9hYThiNTY3YjBlOThkMzZmYWM4YTVhOTNkNWMxYzAyY2VlNWU1OThl&__proxy_form=0)
- code(B) is 011
- For C
![{\displaystyle {\bar {F}}(C)=p(A)+p(B)+{\frac {1}{2}}p(C)={\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{2}}\cdot {\frac {1}{6}}=0.66666\ldots }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8wZjlhMjFkZDI1NGVjMDM0Y2I5YmEwZWM3ODA1MDY4NmFkYzNjNWNj&__proxy_form=0)
- In binary, Z(C) = 0.101010101010...
![{\displaystyle L(C)=\left\lceil \log _{2}{\frac {1}{\frac {1}{6}}}\right\rceil +1=\mathbf {4} }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8yZDczNmIwZjg1ZmIyNzE5YmUyMGM4YWY2NmEwMTY3OTNhNmYxZTZi&__proxy_form=0)
- code(C) is 1010
- For D
![{\displaystyle {\bar {F}}(D)=p(A)+p(B)+p(C)+{\frac {1}{2}}p(D)={\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{6}}+{\frac {1}{2}}\cdot {\frac {1}{4}}=0.875}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy82MWYxN2ZmMjQ4NDBmNDQ3MjUzOTU0MmQ0OWEzZjUzNmQyMzcwMzFh&__proxy_form=0)
- In binary, Z(D) = 0.111
![{\displaystyle L(D)=\left\lceil \log _{2}{\frac {1}{\frac {1}{4}}}\right\rceil +1=\mathbf {3} }](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9mY2I2YTI3NGZkMGFkNjQ2MGY2ZjI2MTljZjI2MWFmOGMxMjA5ZDIx&__proxy_form=0)
- code(D) is 111
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
![{\displaystyle \operatorname {bcode} (x)\leq \operatorname {bcode} (y)<\operatorname {bcode} (x)+2^{-L(x)}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy82NDY0Y2E4MTliM2FmYjk1OGVhMjdiYjI1MzI3ZTYyZmIwZGIxODM2&__proxy_form=0)
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
![{\displaystyle 2^{-L(x)}\leq {\frac {1}{2}}p(x)}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy80YjdlZjBiMDczOTkwZjk1M2Q1ODhhYjU4OTg3NjRmOTUzM2M1ZmNk&__proxy_form=0)
And because the bits after L(y) are truncated from F(y) to form code(y), it follows that
![{\displaystyle {\bar {F}}(y)-\operatorname {bcode} (y)\leq 2^{-L(y)}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8wY2M2YzQ4MDQ3ZjJjNWY5MzQyNDA4ODk3MGQxZWYzMTlhZGJiZWI0&__proxy_form=0)
thus bcode(y) must be no less than CDF(x).
So the above graph demonstrates that the
, therefore the prefix property holds.
The average code length is
.
Thus for H(X), the entropy of the random variable X,
![{\displaystyle H(X)+1\leq LC(X)<H(X)+2}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy82ZDYyMzZiZDFjN2UwYmFiOWFhNDYxZmQzYTI5YzcyYjUwNDdmYjU1&__proxy_form=0)
Shannon Fano Elias codes from 1 to 2 extra bits per symbol from X than entropy, so the code is not used in practice.