• Author / Uploaded
• Yhan Karlo Calcina

• Categories
• Codificación de caracteres
• Conceptos matemáticos
• Física y matemáticas
• Matemáticas
• Matemáticas Aplicadas

Citation preview

Tema 4: Codificación Aritmética Rafael Molina y Javier Mateos Depto Ciencias de la Computación e Inteligencia Artificial Universidad de Granada Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

1

Contenidos • • •

• • •

• •

Objetivos del tema Introducción Codificación de una secuencia por el código aritmético – Generación de la etiqueta – Descifrado de la etiqueta Generación del código binario para el código aritmético – Unicidad y eficiencia del código aritmético Comparación del código de Huffman y el código aritmético Aplicaciones – El estándar JBIG – Codificando imágenes no binarias Resumen Bibliografía Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

2

IV.1 Objetivos del tema En este tema vamos a estudiar otros códigos de longitud variable, los llamados códigos aritméticos. Estos códigos son especialmente útiles cuando trabajamos con alfabetos pequeños o con distribuciones de probabilidad muy sesgadas (skew). Estudiaremos los aspectos básicos de estos códigos, sus propiedades, y describiremos una implementación. Compararemos los códigos aritmético y Huffman. Una variante del código aritmético es el código usado por el estándar Joint Bi-level Experts Group (JBIG) para codificar imágenes binarias, describiremos las partes esenciales de este estándar. Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

3

IV.2 Introducción. El código de Huffman garantiza una razón de compresión R que como mucho es superior en 1 bit a la entropía. Puede probarse también que otra cota alternativa es pmax+0.086 donde pmax es la probabilidad del símbolo que ocurre con mayor probabilidad. Si el valor de pmax es pequeño, la diferencia entre la codificación Huffman y entropía es pequeña, sin embargo para distribuciones muy descompensadas (sesgadas o skew) pmax puede ser bastante grande y el algoritmo de Huffman se hace bastante ineficiente. Podemos agrupar los símbolos de forma que la distribución no sea tan descompensada, pero esto no siempre funciona como veremos ahora con un ejemplo. Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

4

Ejemplo IV.2.1 Consideremos una fuente S con el alfabeto A={a1,a2,a3} con las siguiente probabilidades Se cumple

P(a1)=0.95, P(a2)=0.02 y P(a3)=0.03 H(S)=0.335 bits/símbolo.

Un código Huffman para esta fuente es Letra

Código

a1

0

a2

10

a3

11

que tiene una longitud media de 1.05 bits/símbolo. Este valor es 3.13 veces la entropía Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

5

Podríamos agrupar símbolos de dos dos y obtener siguiente tabla probabilidades.

los en la de

Su longitud media es 1.222 bits/símbolo (para cada dos símbolos) que por símbolo significa 0.611 que en comparación con la entropía es 1.82 veces la entropía

Rafael Molina Javier Mateos

Letra a1a1

Probabilidad 0.9025

Código 0

a1a2 a1a3 a2a1 a2a2 a2a3 a3a1 a3a2 a3a3

0.0190 0.0285 0.0190 0.004 0.0006 0.0285 0.0006 0.0009

111 100 1101 110011 110001 101 110010 110000

Tema 4: Codificación Aritmética

6

La redundancia bajaría a valores razonables si usásemos 8 símbolos juntos, pero esto corresponde a 6561 valores a codificar, lo que requiere mucha memoria. Es más eficiente generar palabras de código por grupos o secuencias de símbolos conforme éstos van apareciendo. En la codificación aritmética, que ahora veremos, le asignaremos una etiqueta a la secuencia completa que queremos codificar, esta etiqueta será una fracción de la unidad. Generaremos un código aritmético para una secuencia de longitud m sin que tengamos que generar código para todas las posibles secuencias de longitud m. Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

7

IV.3 Codificación de una secuencia Para distinguir una secuencia de símbolos de otra tenemos que etiquetar cada secuencia con un identificador único. Un conjunto posible de etiquetas para representar las secuencias de símbolos es el conjunto de los números reales en el intervalo unidad [0,1). •Necesitamos una función que aplique secuencias de símbolos en el intervalo unidad. •Una función que aplica variables aleatorias (y secuencias de variables aleatorias) en el intervalo unidad es la función de distribución. Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

8

La historia del descubrimiento la codificación aritmética y la resolución del problema de la precisión finita de las representaciones en un ordenador es muy interesante. Ver el libro de Sayood (páginas 79-80). Antes de comenzar el desarrollo de la codificación aritmética veamos alguna notación. Comenzamos asignando un número a cada posible miembro del alfabeto. Es decir, si A={a1,…,am} asignamos Ai i De forma que P(ai)=P(i) y tenemos la función de distribución i

FX (i ) = ∑ P ( X = k ) k =1

donde X es la variable aleatoria correspondiente a la probabilidad de la fuente. Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

9

IV.3.1 Generación de la etiqueta Para generar la etiqueta reduciremos el tamaño del intervalo en el que estará la etiqueta conforme vayamos recibiendo más símbolos. Comenzamos dividiendo el intervalo unidad en intervalos de la forma

[

FX(0),FX(1) ), [ FX(1),FX(2) ), ...., [ FX(m-1),FX(m))

Recordemos que FX(0)=0 y FX(m)=1 Tenemos, por tanto, una partición del intervalo unidad en intervalos disjuntos. Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

10

Supongamos que la secuencia que vamos a codificar comienza por el símbolo ak, entonces la etiqueta que generaremos para la secuencia estará en el intervalo [ FX(k-1), FX(k) ). Dividimos ahora este subintervalo en las mismas proporciones que el intervalo unidad [llevamos el intervalo [0,1) al intervalo [ FX(k-1), FX(k) ) y seguimos dividiendo este intervalo manteniendo las proporciones de F en el intervalo [0,1) Ejemplo P(a1)=0.5, P(a2)=0.25, P(a3)=0.25 0

0.5

0.75

1

Observamos a1 Observamos después a2 Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

11

¿Qué tipo de transformación estamos realizando sobre el intervalo [0,1)? Para llevar el intervalo [0,1) al intervalo [FX(k-1), FX(k)). La transformación para x ε [0,1) es f(x)=(FX(k)-FX(k-1))x + FX(k-1) Si el segundo símbolo observado es aj entonces la codificación de akaj estará en el intervalo

[(FX(k)-FX(k-1))FX(j-1)+FX(k-1), (FX(k)-FX(k-1))FX(j)+ FX(k-1)) y así sucesivamente Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

12

Ejemplo 4.3.1: Supongamos que el alfabeto viene dado por A={a1,a2,a3} con probabilidades P(a1)=0.7, P(a2)=0.1, P(a3)=0.2 y por tanto con función de distribución F(1)=0.7, F(2)=0.8, F(3)=1 Supongamos que queremos codificar la secuencia a1a2a3 Para codificar a1 sabemos que la etiqueta debe estar en el intervalo [0,0.7) EN OTRAS PALABRAS, PASAMOS DEL INTERVALO [0,1) AL [0,0.7) Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

13

Recuerda F(1)=0.7, F(2)=0.8, F(3)=1 y para codificar a1 estábamos en [0,0.7)

Para codificar a1a2 sabemos que la etiqueta debe estar en [(0.7-0.0)x0.7+0, (0.7-0.0)*0.8+0) es decir en [0.49,0.56) EN OTRAS PALABRAS, PASAMOS DEL INTERVALO [0.7, 0.8) DENTRO DEL INTERVALO [0,1) AL SUBINTERVALO DE [0,0.7) DADO POR [(0.7-0.0)x0.7+0, (0.7-0.0)*0.8+0)

Por último para codificar la secuencia a1a2a3 sabemos que la etiqueta debe estar en: [(0.56-0.49)x0.8+0.49, (0.56-0.49)x1+0.49) es decir en [0.546, 0.56) EN OTRAS PALABRAS, PASAMOS DEL INTERVALO [0.8, 1) DENTRO DEL INTERVALO [0,1) AL SUBINTERVALO DE [0.49,0.56) DADO POR [(0.56-0.49)x0.8+0.49, (0.56-0.49)x1+0.49) Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

14

Como hemos visto, el intervalo I en el que reside la etiqueta de cada secuencia de un tamaño dado es disjunto con los intervalos en los que residirían las etiquetas de cualquier secuencia del mismo tamaño. Cualquier miembro del intervalo I puede, por tanto, usarse como etiqueta: podemos usar, por ejemplo, el límite inferior o el punto medio. De momento usaremos el punto medio. Buscaremos ahora una fórmula que nos permita calcular la etiqueta de una secuencia. Consideremos una fuente con alfabeto A={a1,a2,…,am}. ¿Cuál sería la etiqueta de una secuencia de un único símbolo? i −1

1 1 TX (ai ) = ∑ P ( X = k ) + P ( X = i ) = FX (i − 1) + P ( X = i ) 2 2 k =1

Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

15

Ejemplo 4.3.2: Consideremos el lanzamiento de un dado equilibrado. El alfabeto es A={1,2,…,6} P(i)=1/6

i=1, 2, …, 6

La etiqueta para el 2 sería TX(2)=P(X=1)+(1/2)P(X=2)=0.25

Resultado

Etiqueta

1

0.0833

3

0.4166

4

0.5833

6

0.9166

La del 5 cinco sería TX(5)=[P(X=1)+P(X=2)+P(X=3)+ P(X=4)]+(1/2)P(X=5)=0.75 La tabla siguiente muestra la etiqueta del resto de símbolos Rafael Molina Javier Mateos

Tema 4: Codificación Aritmética

16

Como hemos visto en el ejemplo anterior, la codificación para secuencias de tamaño uno es fácil. Para secuencias xi de mayor longitud (m) tenemos que ordenar las secuencias de longitud m y asignar a la secuencia xi la etiqueta

1 T (x i ) = ∑ P(y ) + P(x i ) 2 y