Codificación de Shannon-Fano-Elias

Algoritmo para código de prefijo binario

En teoría de la información , la codificación de Shannon-Fano-Elias es un precursor de la codificación aritmética , en la que se utilizan probabilidades para determinar palabras clave. ^[1] Lleva el nombre de Claude Shannon , Robert Fano y Peter Elias .

Descripción del algoritmo

Dada una variable aleatoria discreta X de valores ordenados a codificar, sea la probabilidad de cualquier x en X . Defina una función ${\displaystyle p(x)}$

${\displaystyle {\bar {F}}(x)=\sum _{x_{i}<x}p(x_{i})+{\frac {1}{2}}p(x)}$

Algoritmo:

Para cada x en X ,

Sea Z la expansión binaria de . ${\displaystyle {\bar {F}}(x)}$

Elija la longitud de la codificación de x , , para que sea el número entero ${\displaystyle L(x)}$ ${\displaystyle \left\lceil \log _{2}{\frac {1}{p(x)}}\right\rceil +1}$

Elija la codificación de x , , sean los primeros bits más significativos después del punto decimal de Z. ${\displaystyle code(x)}$ ${\displaystyle L(x)}$

Ejemplo

Sea X = { A , B , C , D }, con probabilidades p = {1/3, 1/4, 1/6, 1/4}.

Para A

${\displaystyle {\bar {F}}(A)={\frac {1}{2}}p(A)={\frac {1}{2}}\cdot {\frac {1}{3}}=0.1666\ldots }$

En binario, Z ( A ) = 0,001 0101010 ...

${\displaystyle L(A)=\left\lceil \log _{2}{\frac {1}{\frac {1}{3}}}\right\rceil +1=\mathbf {3} }$

El código ( A ) es 001

Para 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 }$

En binario, Z ( B ) = 0,011 10101010101 ...

${\displaystyle L(B)=\left\lceil \log _{2}{\frac {1}{\frac {1}{4}}}\right\rceil +1=\mathbf {3} }$

El código ( B ) es 011

Para 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 }$

En binario, Z ( C ) = 0. 1010 10101010...

${\displaystyle L(C)=\left\lceil \log _{2}{\frac {1}{\frac {1}{6}}}\right\rceil +1=\mathbf {4} }$

El código ( C ) es 1010

Para 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}$

En binario, Z(D) = 0,111

${\displaystyle L(D)=\left\lceil \log _{2}{\frac {1}{\frac {1}{4}}}\right\rceil +1=\mathbf {3} }$

El código ( D ) es 111

Análisis de algoritmos

Código de prefijo

La codificación de Shannon-Fano-Elias produce un código de prefijo binario que permite una decodificación directa.

Sea bcode( x ) el número racional formado añadiendo un punto decimal antes de un código binario. Por ejemplo, si code( C ) = 1010 entonces bcode( C ) = 0,1010. Para todo x , si no existe y tal que

${\displaystyle \operatorname {bcode} (x)\leq \operatorname {bcode} (y)<\operatorname {bcode} (x)+2^{-L(x)}}$

Entonces todos los códigos forman un código de prefijo.

Comparando F con la CDF de X , esta propiedad se puede demostrar gráficamente para la codificación de Shannon-Fano-Elias.

Por definición de L se deduce que

${\displaystyle 2^{-L(x)}\leq {\frac {1}{2}}p(x)}$

Y como los bits después de L ( y ) se truncan de F ( y ) para formar código ( y ), se deduce que

${\displaystyle {\bar {F}}(y)-\operatorname {bcode} (y)\leq 2^{-L(y)}}$

Por lo tanto, bcode( y ) no debe ser menor que CDF( x ).

Por lo tanto, el gráfico anterior demuestra que la propiedad , por lo tanto, el prefijo se cumple. ${\displaystyle \operatorname {bcode} (y)-\operatorname {bcode} (x)>p(x)\geq 2^{-L(x)}}$

Longitud del código

La longitud media del código es . Por lo tanto, para H ( X ), la entropía de la variable aleatoria X , ${\displaystyle LC(X)=\sum _{x\in X}p(x)L(x)=\sum _{x\in X}p(x)\left(\left\lceil \log _{2}{\frac {1}{p(x)}}\right\rceil +1\right)}$

${\displaystyle H(X)+1\leq LC(X)<H(X)+2}$

Los códigos de Shannon Fano Elias utilizan de 1 a 2 bits adicionales por símbolo de X que la entropía, por lo que el código no se utiliza en la práctica.

Véase también

• Codificación de Shannon-Fano

Referencias

1. TM Cover y Joy A. Thomas (2006). Elementos de la teoría de la información (2.ª ed.). John Wiley and Sons. pp. 127–128. ISBN 978-0-471-24195-9.