Codificación entrópica

En teoría de la información, "'codificación entrópica"' es un método de codificación sin perdidas que es independiente de las características específicas del medio. Este método se basa en un conocimiento previo sobre los símbolos que surgirían en una trama binaria.

La entropía es un factor para evaluar los codificadores. Se calcula con los nombres de bits por símbolo usados. Para una fuente lo interesante es la información media que genera, esto es la entropía.

Existen tres tipos de códigos:

• RLE: Codificación por longitud de series (Run Length Encoding),
• DPCM (Differential PCM),
• VLC: Códigos de longitud variable (Variable Length Coding).

RLE: Codificación por longitud de series (Run Length Encoding)

Lectura en zig-zag

La codificación Run Length realizan una lectura en zig-zag de la matriz de símbolos. Utiliza un método de lectura en diagonal en lugar de recorrerlo por filas o columnas como sería lo habitual.

RLE realiza una búsqueda de series consecutivas de solo un símbolo dentro de una trama. Posteriormente sustituye la serie por una única instancia del símbolo y un contador con la cantidad de repeticiones.

Ejemplo

• Trama original: {A A A B B C C C D D D D B B A E E}
• Codificación RLE: {[A,3] [B,2] [C,3] [D,4] [B,2] [A,1] [E,2]}

DPCM (Differential PCM)

DPCM Codifica la diferencia entre un valor y el anterior.

Los sistemas DPCM codifican la diferencia entre un valor y el anterior. En codificación de imagen, se utiliza para codificar los coeficientes DC de la Transformada Coseno Discreta (Discrete Cosine Transform - DCT). Estas presentan el nivel de gris medio del bloque y, a menudo, el nivel medio de gris de un bloque será similar al nivel medio de gris del bloque anterior. Por lo tanto la diferencia entre dos bloques consecutivos es mínima. Si por ejemplo codificamos una imagen donde hay una gran parte de cielo, entonces enviaremos números más pequeños, ya que la diferencia con el anterior valor será casi 0. Si no utilizáramos la codificación DPCM los valores serían mucho más grandes, la cual equivale a más bits en binario.

Ejemplo de codificación DPCM de una imagen

VLC: Códigos de longitud variable (Variable Length Coding)

Se trata de un caso particular de codificación aritmética. La idea básica de los códigos de longitud variable es asignar códigos de palabras de longitudes diferentes en función de la probabilidad de los mensajes. Los mensajes menos probables se codificarán con un mayor nombre de bits que no los mensajes más probables.

Ejemplo

Se quiere codificar la secuencia: 0 1 2 3 0 0 4 5 3 2 3 0 4 2 2 2 0 2 0 4 1 2 3 3 3

Símbolo	Probabilidad	Código
0	0.24	00
1	0.08	1110
2	0.28	01
3	0.24	10
4	0.12	110
5	0.04	1111

Podemos calcular el nivel medio de bits que se utilizan para codificar esta trama con este código arbitrario calculando el número de bits utilizado para cada símbolo ponderado para la probabilidad con la que se producen los símbolos.

$N_{medio}=\sum _{n=1}^{N}\ N_{k}\cdot {}P_{k}=\sum _{i=1}^{6}\ (2\cdot 0,24)+(4\cdot 0,08)+(2\cdot 0,28)+(2\cdot 0,24)+(3\cdot 0,12)+(4\cdot 0,04)=3,04bits$

Evidentemente, el número de bits medio esta por encima de la entropía:

                                                       $H=-\sum _{n=1}^{N}\ p_{k}\cdot log_{2}p_{k}=2,35bits$

Véase también

• Codificación Run Length
• Codificación de Huffman
• Differential PCM

Enlaces externos

• Datos: Q1345239