Codificaci N Aritm Tica

Codificación aritmética

símbolo probabilidad intervalo

En la codificación aritmética no se asigna una palabra de código a cada uno de
los símbolos del alfabeto fuente. Lo que se hace es codificar una secuencia de
entrada de símbolos del alfabeto fuente mediante un número representado en
punto flotante.
El proceso se basa en asignar a cada símbolo un intervalo entre 0 y 1, de forma
que laamplitud de cada intervalo sea igual a la probabilidad de cada símbolo. La
suma de las amplitudes de los intervalos debe ser igual a la unidad. Es necesario
establecer algún orden entre los símbolos del alfabeto fuente que será conocido
por el receptor para poder hacer una correcta decodificación.
Para codificar una determinada cadena se siguen los siguientes pasos:
- Se selecciona el primer símbolo dela secuencia de entrada y se localiza el
intervalo asociado a ese símbolo.
- A continuación se selecciona el siguiente símbolo y se localiza su intervalo.
Se multiplican los extremos de este intervalo por la longitud del intervalo
asociado al símbolo anterior (es decir, por la probabilidad del símbolo
anterior) y los resultados se suman al extremo inferior del intervalo asociado
al símboloanterior para obtener unos nuevos extremos inferior y superior.
- El paso anterior se repite hasta que todos los símbolos del mensaje hayan sido
procesados.
- Para el símbolo i-ésimo se calcula su intervalo de la siguiente forma:
inf(i)=inf(i-1)+(sup(i-1)-inf(i-1))*inf(i)
sup(i)=inf(i-1)+(sup(i-1)-inf(i-1))*sup(i)
- Por último se selecciona un valor dentro del intervalo del último símbolo de
lasecuencia. Este valor representará la secuencia que queremos enviar.

x1

0.1

[0.0,0.1]

x2

0.3

[0.1,0.4]

x3

0.4

[0.4,0.8]

x4

0.15

[0.8,0.95]

x5

0.05

[0.95,1.0]

Ejemplo de codificación
Para este ejemplo usaremos el conjunto de símbolos que se muestra en la
siguiente tabla:
símbolo probabilidad
x1

0.1

x2

0.3

x3

0.4

x4

0.15

x5

0.05

Vamos a mantener la misma ordenación con la queaparecen los símbolos en la
tabla anterior.
La asignación de intervalos a los símbolos del alfabeto fuente será la siguiente:

Supongamos que la cadena de símbolos que queremos enviar es la siguiente:
x3x5x2x1x4x5
A continuación realizamos la codificación.
Tomamos el primer símbolo de la cadena de entrada:
x3 [0.4,0.8]
amplitud del intervalo: 0.4
Ahora tomamos el siguiente símbolo de la cadena deentrada y calculamos los
nuevos límites de su intervalo asociado:
x5 [0.95,1.0]
nuevo límite inferior = 0.4+(0.95*0.4)=0.78
nuevo límite superior = 0.4+(1.0*0.4)=0.8
Resultado: x5 [0.78,0.8] amplitud del intervalo: 0.02
Se repite el paso anterior para cada uno de los símbolos restantes de la cadena
de entrada:
x2 [0.1,0.4]
nuevo límite inferior = 0.78+(0.02*0.1)=0.782
nuevo límite superior =0.78+(0.02*0.4)=0.788
Resultado: x2 [0.782,0.788] amplitud del intervalo: 0.006
x1 [0.0,0.1]
nuevo límite inferior = 0.782+(0.006*0.0)=0.782
nuevo límite superior = 0.782+(0.006*0.1)=0.7826
Resultado: x1 [0.782,0.7826] amplitud del intervalo: 0.0006
x4 [0.8,0.95]
nuevo límite inferior = 0.782+(0.0006*0.8)=0.78248
nuevo límite superior = 0.782+(0.0006*0.95)=0.78257
Resultado: x4 [0.78248,0.78257] amplitud delintervalo: 0.00009
x5 [0.95,1.0]
nuevo límite inferior = 0.78248+(0.00009*0.95)=0.7825655
nuevo límite superior = 0.78248+(0.00009*1.0)=0.78257
Resultado: x5 [0.7825655,0.78257]

Por último, elegiríamos un valor perteneciente al último intervalo que hemos
obtenido y este valor será el que transmitamos a través del canal. Cualquier valor
que elijamos perteneciente al último intervalo representaráde forma única a la
secuencia de entrada original.
Cuando se transmite un valor al receptor es necesario indicar cuantos símbolos
se han enviado para que el receptor sepa cuándo debe finalizar el proceso de
descompresión. Para indicar esto existen dos técnicas. La primera consiste en
enviar antes del valor elegido el número de símbolos que se han comprimido en
binario. De esta forma el receptor...