hola

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 dela 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 estudiarotros 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ódigoaritmé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 otracota 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ímbolosde 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 Huffmanpara 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
cadados
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ética6

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
queremoscodificar, 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...