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 les 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.

Existen tres tipos de códigos: Codificación por longitud de series"(Run Length Encoding - RLE)", DPCM "(Differential PCM)" y Códigos de longitud variable "(Variable Length Coding - VLC)"

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

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 pera 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 serian mucho mas grandes, la cual equivale a más bits en binario.

Ejemplo de codificación DPCM de una imagen

VLC (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 más probables se codificaran con un mayor nombre de bits que no los mensajes menos probables.

Por 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\cdot0,24)+(4\cdot0,08)+(2\cdot0,28)+(2\cdot0,24)+(3\cdot0,12)+(4\cdot0,04)=3,04 bits$

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,35 bits$

Mirar tambien

codificación Run Length

Codificación de Huffman

DifferentialPCM

Referencias

• Este artículo fue creado a partir de la traducción del artículo Codificació entròpica de la Wikipedia en catalán, concretamente de esta versión, bajo licencia Creative Commons Atribución Compartir Igual 3.0 y GFDL.