Codificacin aritmtica

Es til cuando se tienen fuentes con alfabetos pequeos.

En el cdigo Huffman si el alfabeto es grande, la probabilidad del smbolo ms probable es
pequea y la desviacin de la rata de cdigo de la entropa (redundancia) es pequea. Al
contrario si el alfabeto es pequeo en donde la redundancia del cdigo Huffman es grande.
Esto se resuelve generando un cdigo extendido pero esto a veces es imprctico porque se
generan alfabetos demasiado grandes, se requieren grandes cantidades de memoria y tiempos
y recursos exagerados en la decodificacin.
Ejemplo:
Considere una fuente que pone letras independientes e idnticamente distribuidas () desde
un alfabeto
= { , , }
Con el modelo de probabilidad
( ) = .
( ) = .
( ) = .
La entropa para esta fuente es . /. Un cdigo Huffman para esta fuente
est dado en la tabla 1
Letra cdigo

Tabla 1: Cdigo Huffman para un alfabeto de tres letras

La longitud promedio para este cdigo es . /. La diferencia entre la longitud

promedia de cdigo y la entropa, o redundancia, para este cdigo es . /,
lo que es el % de la entropa. Esto significa que para codificar esta secuencia
necesitaramos ms del doble del nmero de bits prometidos por la entropa.
Agrupando los smbolos en bloques de dos, el alfabeto extendido y el modelo de probabilidad
y el cdigo se muestran en la tabla 2.

Letra Probabilidad Cdigo

.

Tabla 2: Cdigo Huffman para un alfabeto extendido

La rata promedio para el alfabeto extendido es . /. La rata adicional

sobre la entropa es an cerca del % de la entropa. Si se contina poniendo bloques de
ms smbolos encontramos que la redundancia cae a un valor aceptable cuando hacemos
bloques de . El tamao de alfabeto correspondiente a este nivel es de ,
lo cual hace que el tamao de este cdigo sea imprctico por varias razones:

El tamao de la memoria necesario para almacenar este cdigo puede que no est
disponible.
La decodificacin de un cdigo de este tamao puede ser un proceso altamente
ineficiente y consumidor de tiempo.
Si la estadstica cambia aunque sea ligeramente puede hacer que el cdigo sea
ineficiente.
Problema: para codificar una secuencia de longitud en Huffman se requieren
palabras de cdigo para todas las posibles secuencias de longitud .

En la codificacin aritmtica se asigna un identificador nico o tag a la secuencia a

codificar, el cual es una fraccin binaria a la que se le asigna posteriormente un cdigo
binario.
Se asigna un cdigo aritmtico nico a una secuencia de longitud sin que sea necesario
generar palabras de cdigo para todas las posibles secuencias de longitud .
Codificando una secuencia
Una manera de codificar con un identificador nico a cada secuencia es asignarle un nmero
en el intervalo [, ), lo cual da un conjunto infinito de identificadores.
Una funcin que toma este intervalo es la funcin distribucin acumulativa de
probabilidad de una variable aleatoria asociada con la fuente.

La variable aleatoria se toma como la asignacin de un nmero a las letras o smbolos

de la fuente
( ) =

Siendo = { , , , } el alfabeto de la fuente.

El mapeo supone que se dispone de un modelo de probabilidad de la fuente y de la
funcin densidad de probabilidad de la variable aleatoria, tal que
( = ) = ( )
Y la funcin distribucin acumulativa
() =

( = )

Ejemplo:
Considere el alfabeto de tres letras = { , , } con ( ) = . , ( ) = . ,
( ) = . .Usando el mapeo propuesto () = . , () = . , () = Esto
parte el intervalo unitario como se muestra en la ilustracin 1.

Ilustracin 1: Restringiendo el intervalo que contiene el identificador para la secuencia

{ , , }
La particin en la cual reside el identificador depende del primer smbolo de la secuencia que
est siendo codificada. Por ejemplo, si el primer smbolo es , el identificador estar en el
intervalo [. , . ]; si el primer smbolo es , el identificador estar entre[. , . ], y si

el smbolo es el identificador estar entre [. , . ]. Una vez el intervalo que contiene

el identificador ha sido determinado, el resto del intervalo unidad es descartado y el intervalo
restringido es dividido otra vez en las mismas proporciones del intervalo original. Suponga
que el primer smbolo fue . El identificador estara contenido en el sub intervalo[, . ];
Este sub intervalo es luego dividido en exactamente las mismas proporciones como el
intervalo original, dando los sub intervalos [. , . ], [. , . ], [. , . ] la
primera particin corresponde al smbolo , la segunda al smbolo y as sucesivamente.
El proceso iterativo puede visualizarse en la ilustracin 1.
La aparicin de cada nuevo smbolo de la secuencia restringe el identificador a un nuevo
subintervalo que es disjunto de cualquier otro subintervalo que pueda haber sido generado
usando este proceso, luego cualquier miembro de este subintervalo puede ser usado como
identificador. Una escogencia popular es el lmite inferior pero tambin puede ser el medio
del intervalo.
Hay un procedimiento recursivo para calcular los lmites inferior y superior del intervalo para
una secuencia de longitud .
En general, se puede mostrar que para cualquier secuencia = ( )
() = () + (() () ) ( )
() = () + (() () ) ( )
En donde se supone que () = y () = .
Observe que a travs de este proceso no necesitamos calcular explcitamente cualquier
probabilidad conjunta.
Si se usa el punto medio del intervalo para el identificador, entonces
() =

() + ()

Ejemplo: Generando un identificador

Considere una fuente que genera los smbolos con probabilidad ( ) = . , con
probabilidad ( )=0.02 y con probabilidad ( ) = . . Se define la variable
aleatoria ( ) = . Se supone que se va a codificar la secuencia .
Del modelo de probabilidad sabemos que

 () = , () = . ,
() =

() = . , () = ,

Usando las ecuaciones que permiten calcular los limites inferior y superior de manera
iterativa y suponiendo () = y () = . El primer elemento de la secuencia resulta en
la siguiente actualizacin:
() = + ( )
=
() = + ( ) ,
= ,
O sea, el identificador de la secuencia estar en el intervalo [, . ). El segundo elemento
de la secuencia es . Usando las ecuaciones de actualizacin tenemos:
() = + (. ) ()
= + (. ) .
= .
() = + (. ) ()
= + (. )
= .
Por consiguiente, el intervalo que contiene el identificador de la secuencia es
[. , . ]. El tercer elemento es , lo que resulta en las siguientes ecuaciones de
actualizacion:
() = . + (. . ) ()
= . + (. . ) .
= .
Y por lo tanto el intervalo que contiene la secuencia es [. , . ).
Continuando con el ltimo elemento, las ecuaciones de actualizacin dan lo siguiente:
() = . + (. . ) ()
= . + (. . ) .
= .
() = . + (. . ) ()
= . + (. . ) .
= .
Y el identificador para la secuencia se puede generar como

() + ()

. + .
=

= .

( ) =

Generando una secuencia binaria

Para codificar el identificador se toma la representacin binaria del nmero y se trunca a
() = (()) +
En donde () es la probabilidad de la secuencia.
Ejemplo:
Considere la fuente que genera los smbolos = { , , , } con probabilidades

( ) =

( ) =

( ) =

( ) =

Se puede generar un cdigo binario para esta fuente como se muestra en la tabla 3. La
cantidad
se obtiene usando la ecuacin (. ). La representacin binaria de
se trunca
a (/()) + para obtener el cdigo binario.
Smbolo

En Binario (
) + Cdigo
()
.
.
.

.
.
.

. .
.

. .
.

Tabla 3: Cdigo binario para un alfabeto de 4 smbolos

Descifrando un identificador
Dado el identificador obtenido en el ejemplo anterior trataremos de imitar al codificador para
obtener la secuencia representada por este identificador. El valor del identificador es
. . El intervalo que contiene este identificador es un subconjunto de todos los
intervalos contenidos en el proceso de codificacin. La estrategia de decodificacin ser
decodificar los elementos en la secuencia de tal manera que los limites inferior () ()
siempre contengan el valor del identificador para cada . arrancamos con () = () =
. Despus de decodificar el primer elemento de la secuencia , los lmites inferior y
superior llegan a ser:

() = + ( ) ( )
= ( )
() = + ( ) ( )
= ( )
En otras palabras, el intervalo que contiene el identificador es [ ( ), ( )).
Necesitamos encontrar el valor de para el cual . est en el intervalo
[ ( ), ( )). Si hacemos = , el intervalo es [, . ), Si hacemos = , el
intervalo es [. , . ), Si hacemos = , el intervalo es [. , ). Como .
esta en el intervalo [, . ) escogemos = . Repetimos este procedimiento para el
segundo elemento , usando los valores actualizados para () ()
() = + (. ) ( )
= . ( )
() = + (. ) ( )
= . ( )
Si hacemos = , el intervalo actualizado es [0, 0.64), el cual no contiene el identificador.
Luego no puede ser . Si hacemos = , el intervalo actualizado es [0.64, 0.656), el
cual tampoco contiene el identificador. Si hacemos = , el intervalo actualizado es
[0.656, 0.8), el cual s contiene el valor . del identificador. Luego el segundo
elemento en la secuencia es . Sabiendo cual es el segundo elemento de la secuencia,
podemos actualizar los valores de () y () y encontrar el elemento , el cual nos dar un
intervalo que contiene el identificador:
() = . + (. . ) ( )
= . + . ( )
() = . + (. . ) ( )
= . + . ( )
Sin embargo, las expresiones resultantes son cansonas en esta forma. Para hacer las
comparaciones ms fciles, podriamos restar el valor de () tanto de los limites como del
identificador. O sea, encontramos el valor de para el cual el intervalo [.
( ), . ( )) contiene . . = . . O, podramos
hacerlo an ms simple y dividir el valor del identificador residual de . por .
para obtener . , y encontrar el valor de para el cual . cae en el intervalo
[ ( ), ( )) . Inmediatamente vemos que el nico valor de para el cual es
posible esto es . Substituyendo para en las ecuaciones de actualizacin, podemos hallar
los nuevos valores de () () . Podemos ahora encontrar el elemento al calcular los
lmites inferior y superior as

() = . + (. . ) ( )
= . + . ( )
() = . + (. . ) ( )
= . + . ( )
Otra vez podemos restar () del identificador para conseguir . . =
. y encontrar el valor de para el cual el intervalo [. ( ),
. ( )) contiene a . . Para hacer las comparaciones ms simples,
podemos dividir el valor residual del identificador por . para conseguir . y
encontrar el valor de para el cual . est contenido en [ ( ), ( )). Podemos
ver que aquel valor es = y hemos decodificado la secuencia completa. Observe que
nosotros sabamos la longitud de la secuencia anticipadamente y, por lo tanto, sabamos
cuando parar.
El algoritmo de decodificacin:
1.
2.
3.
4.
5.

Inicialice () = () =
Para cada encuentre = ( () )/(() () )
Encuentre el valor de para el cual ( ) ( )
Actualice () ()
Contine hasta que la secuencia completa haya sido decodificada

Hay dos maneras de saber que la secuencia completa ha sido decodificada:

El decodificador puede conocer la longitud de la secuencia

Si un smbolo particular se denota como fin de transmisin.

Comparacin con el cdigo Huffman

Si se codifican los smbolos uno a la vez el cdigo Huffman se comporta mejor que la
codificacin aritmtica. Sin embargo a medida que se codifican secuencias ms largas la
codificacin aritmtica va mejorando (ver tabla 4).
Cuantas muestras tenemos que agrupar para hacer que el esquema de codificacin aritmtico
se desempee mejor que el cdigo Huffman? Podemos tener alguna idea mirando los lmites
en la rata de codificacin.
Los lmites en la longitud promedio de la codificacin aritmtica son
() () +

No toma muchos smbolos en una secuencia antes que la rata de codificacin para el cdigo
aritmtico llegue a estar cerca de la entropa. Sin embargo, recordando que para los cdigos
Huffman, si tomamos bloques de m smbolos juntos, la rata de codificacin es
() () +

Mensaje

()

()

.
.
.
.
.
.
.
.
.
.
.
.
. .
. .
.
.
. .
. .
. .
.
.
. .
. .
. .

() en binario
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

1
+1
()

Cdigo

Tabla 4: Codificacin aritmtica para secuencias de dos smbolos.

La ventaja parece estar con el cdigo Huffman, aunque la ventaja decrece con el incremento
de . Sin embargo recuerde que generar una palabra de cdigo para una secuencia de
longitud usando el cdigo Huffman requiere construir el cdigo completo para todas las
posibles secuencias de longitud . si el alfabeto original es longitud , entonces el tamao
del libro de cdigo ser . Tomando valores relativamente razonables de = =
da un tamao de diccionario de . Esto obviamente no es una opcin viable. Para el
procedimiento de codificacin Huffman, no necesitamos construir el diccionario completo.
En vez de esto simplemente obtenemos el cdigo para el identificador correspondiente a una
secuencia dada. Luego, es enteramente realizable codificar secuencias de longitud o
mucho ms. En la prctica podemos hacer largo para el codificador aritmtico y no para
el codificador Huffman. Esto significa que para la mayora de las fuentes podemos obtener
ratas ms cercanas a la entropa usando codificacin aritmtica que con codificacin
Huffman. Las excepciones son las fuentes con probabilidades potencia de dos.

Aplicaciones

El estndar ( . ) (Joint Bi-level Image

processing Group)

En este estndar se recomienda la codificacin aritmtica como parte de la codificacin de

imgenes binarias.
Este grupo se forma en para la codificacin progresiva de imgenes de dos niveles.
El estndar consta de dos algoritmos:

El algoritmo de transmisin progresiva

El algoritmo de codificacin sin prdidas.

La compresin sin prdidas:

Muchas imgenes bi_nivel tienen una gran cantidad de estructura local.
Por ejemplo en la transmisin de texto hay grandes porciones de la imagen en donde se
encuentran pxeles blancos con probabilidad de ocurrencia cerca de uno. En otras porciones
de imagen sucede lo contrario, hay grandes probabilidades de encontrar pxeles negros.
Se pueden hacer suposiciones razonables de la situacin para un determinado pxel
conociendo los valores de los pxeles vecinos al pxel que est siendo codificado. Por ejemplo
si la mayora de los pxeles vecinos son blancos hay grandes probabilidades de que este
tambin lo sea y viceversa.
Cada caso nos da una probabilidad asimtrica, lo que es ideal para la codificacin
aritmtica. Si se trata cada caso separadamente usando un codificador aritmtico diferente
para cada una de las dos situaciones, se podra obtener una mejora sobre el caso donde
usamos el mismo codificador aritmtico para todos los pxeles.
Ejemplo:
Suponga que la probabilidad de encontrar un pxel negro es . y la de encontrar un pxel
blanco es . , la entropa en este caso es () = .
Si se usa un solo codificador para codificar esta fuente se conseguir una rata de bit cercana
a . /.
Si se supone con base en la vecindad de los pxeles que podemos dividir los pxeles en dos
conjuntos, uno que comprenda el % de los pxeles y otro el % y que adems en el
primer conjunto la probabilidad de encontrar un pxel blanco es . y en el segundo la

probabilidad de encontrar un pxel negro es . . La entropa de estos conjuntos es . y

. respectivamente.
Si usamos dos codificadores aritmticos para los dos conjuntos con tablas de frecuencia
acopladas a las probabilidades, conseguiramos ratas cercanas a . cerca del % del
tiempo y cercanas a . cerca del % del tiempo. La rata promedio sera cerca de
. / la cual es casi la mitad de la rata requerida si usramos un solo
codificador aritmtico.
Si usamos solamente pxeles en la vecindad de aquellos que ya han sido transmitidos al
receptor para hacer nuestra decisin acerca de cual codificador usar, el decodificador puede
mantenerse informado acerca de cual codificador fue usado para codificar un pxel particular.
La codificacin aritmtica es particularmente atractiva para el uso de codificadores
mltiples, todos ellos usando la misma maquinaria computacional con cada codificador
usando un conjunto diferente de probabilidades.
El algoritmo hace uso de esta caracterstica de la codificacin aritmtica. En vez de
chequear para ver si la mayora de los pxeles en la vecindad son blancos o negros, el
codificador usa el patrn de pxeles en la vecindad o contexto para decidir cul
conjunto de probabilidades usar en la codificacin de un pxel particular (ver ilustracin 2).
Si la vecindad consiste de con cada pxel capaz de tomar uno de dos valores
diferentes, el nmero de patrones diferentes posibles es , el codificador usa de
codificadores, dependiendo de si una capa de baja o alta resolucin est
siendo codificada.

Ilustracin 2: Configuracin de los vecinos en el estndar

Para la capa de baja resolucin el codificador usa uno de dos diferentes vecinos
mostrados en la ilustracin 2.
El pxel X es el que va a ser codificado, mientras que los que van a ser usados como templates
(plantillas) son marcados como O o A, los cuales son previamente codificados y estn
disponibles tanto para el codificador como para el decodificador.

El pxel A puede pensarse como un miembro flotante de la vecindad. Su colocacin es

dependiente de la entrada que esta siendo codificada. Suponga que la imagen tiene lneas
verticales separadas . El pixel puede ser movido alrededor en orden a capturar
cualquier estructura que pueda existir en la imagen. Esto es especialmente til en las
imgenes halftone en las que los pixeles son usados para capturar la estructura peridica.
La ubicacin y movimiento del pixel es transmitida al decodificador como informacin
lateral.
En la siguiente ilustracin 3 los smbolos en la vecindad han sido reemplazados por y
. El cero corresponde a pxeles blancos mientras que el uno corresponde a pxeles negros.
El pixel a codificar esta encerrado en una caja sombreada.

Ilustracin 3: contextos de (a) tres lneas, (b) dos lneas

El patrn de 0s y 1s es interpretada como un numero binario el cual es usado como un ndice

para el conjunto de probabilidades. El contexto en el caso de la vecindad de tres lneas
(leyendo de izquierda a derecha y de arriba abajo) es , el cual corresponde a
un ndice de . Para la vecindad de dos lneas el contexto es o . Como
hay en este template tendremos diferentes codificadores aritmticos.
En el estndar los codificadores son una variacin del codificador aritmtico
conocido como el codificador QM.
En la descripcin del codificador aritmtico previa hemos estado actualizando el intervalo de
identificador al actualizar los extremos del intervalo u

n y l n .

De igual manera se podra haber mantenido un extremo y el tamao del Intervalo. Esta es la
aproximacin adoptada en el codificador QM, el cual conserva el extremo inferior y el

n u n l n

tamao del intervalo A

El identificador para una secuencia es la representacin binaria de l

Se puede obtener una ecuacin de actualizacin de

An

An An 1 FX xn FX xn 1
An 1 P xn

l n l n 1 An 1 FX xn 1
En vez de tratar directamente con 0s y 1s puestos por la fuente, el codificador QM los mapea
en el smbolo ms probable (MPS) y en el smbolo menos probable (LPS).
Si 0 representa un pxel negro y 1 representa un pxel blanco entonces en una imagen
mayormente negra el 0 ser el MPS y el uno el LPS.
Denotando la probabilidad de ocurrencia del LPS en el contexto C por qc y mapeando el
MPS al subintervalo mas bajo la ocurrencia de un smbolo MPS resulta en las siguientes
ecuaciones de actualizacin:

l n l n 1
An An 1 1 qc
Mientras que la ocurrencia de un LPS resultara en las siguientes ecuaciones de actualizacin:

l n l n 1 An 1 1 qc

An An 1qc
Para hacer la implementacin del codificador ms simple el comit recomend varias
desviaciones del algoritmo de codificacin estndar, evitando las multiplicaciones al asumir

An tiene un valor cercano a uno lo que simplifica las ecuaciones de actualizacin

n
tomando A =1.
que

Si

An cae por debajo de 0.75 se hace un proceso de reescalamiento hasta que el valor de

An sea mayor o igual a 0.75.

El reescalamiento es un proceso repetido de doblado lo que corresponde a desplazamientos

a la izquierda. Para conservar sincronizados los parmetros se aplica el mismo proceso de
reescalado al lmite inferior. Los bits que salen fuera del buffer que contiene el valor del
lmite inferior constituyen la salida del codificador.

Mirando las ecuaciones de actualizacin para el codificador QM podemos ver que la

rescalizacion ocurrir cada vez que ocurre un LPS. La ocurrencia de un MPS podr o no
resultar en un re escalamiento dependiendo del valor de

A n .

La probabilidad qc del LPS para el contexto C se actualiza cada vez que el reescalamiento
toma lugar y el contexto C es activo. Una lista ordenada de valores es hecha en una tabla para
qc . Cada vez que tiene lugar un reescalamiento el valor de qc es cambiado al prximo valor
ms bajo o ms alto en la tabla dependiendo de si el reescalamiento fue causado por la
ocurrencia de un LPS o de un MPS.
En una situacin no estacionaria puede suceder que el smbolo asignado al LPS ocurra mas
frecuentemente que el smbolo asignado al MPS lo cual es detectado cuando qc An qc
. En esta situacin se reversa la asignacin. Esta prueba debe realizarse cada vez que una
rescalizacion toma lugar.
El decodificador QM opera de manera similar al codificador descrito.
La transmisin progresiva
Busca poder transmitir imgenes de ms baja resolucin utilizando menos bits.
El estndar recomienda generar un pxel de ms baja resolucin por cada bloque
de 2*2 en la imagen de ms alta resolucin. El nmero de imgenes de ms baja resolucin
(llamadas capas) no se especifica en el estndar.
Un mtodo directo para generar una capa de ms baja resolucin es reemplazar cada bloque
de 2*2 con el valor promedio de los cuatro pxeles, reduciendo la resolucin por dos en las
direcciones vertical y horizontal. El problema es cuando la mitad de los pxeles es blanco y
la mitad negra.
En vez de hacer lo anterior el estndar especifica un mtodo de reduccin de resolucin
basado en tablas. La tabla es indexada por los pxeles vecinos mostrados en la ilustracin 4.

Ilustracin 4: pixeles utilizados para determinar el valor del pixel de ms bajo nivel

Los crculos representan los pxeles de la capa de ms baja resolucin y los cuadrados
representan los pxeles de la capa de ms alta resolucin.
Cada pxel contribuye un poco al ndice. La tabla se forma calculando la expresin

4e 2b d f h a c g i 3B C A
Si el valor de esta expresin es mayor a 4.5 el pxel X es tentativamente declarado 1. Las
imgenes de ms baja resolucin pueden ser usadas para codificar las imgenes de ms alta
resolucin. La especificacin hace esto usando los pxeles de ms baja resolucin como
parte del contexto para codificar las imgenes de ms alta resolucin (ver ilustracin 5).

Ilustracin 5: Contextos usados en la codificacin de las capas de ms alta resolucin

Se usan diez pxeles en cada contexto. Si se incluyen los 2 bits requeridos para indicar el
t que est siendo usado, se usaran 12 bits para indicar el contexto, lo cual indica que
habr 4096 contextos diferentes.
El desempeo de la codificacin aritmtica se puede observar en las tablas 5 y 6 obtenidas a
partir de la codificacin de las imgenes de la ilustracin 6.

Ilustracin 6: imgenes usadas para la codificacin aritmtica.

Tabla 5: Compresin lograda al usar codificacin aritmtica adaptativa de los valores de los pixeles

Tabla 6: compresin lograda al usar codificacin aritmtica adaptativa para los pixeles diferencia.