Resolvedor paso a paso de ejercicios de codificación aritmética

Compresor aritmético

Los ejercicios de compresión aritmética son bastante típicos en exámenes y guías de trabajos prácticos. En un entorno de examen se resuelven a mano. Para verificar si se siguió el procedimiento correcto, este proyecto busca imitar una resolución paso a paso con papel y lápiz.

Las dependencias son mínimas, solo utilizo SymPy para trabajar con fracciones.

Los códigos a la entrada, involucrados en el algoritmo:

$$ \begin{array}{c|c|c} & \text{Codificación } \xi & \text{Decodificación } F_Z (\xi) \\ \hline \text{Representación} & z_1z_2… \text{ en base } k & y_1y_2… \text{ en base } D \\ \hline \text{Distribución} & f_Z(z_i) \text{ no uniforme } & f_Y(y_i) \text{ uniforme } \end{array} $$

Vamos a pasar por un ejemplo, si tenemos el intervalo [0,3/4,1] y la secuencia [0,0,1,1,0]:

1
2
3


>> interval0 = [0, sp.Rational(3, 4), 1]
>> code = [0, 0, 1, 1, 0]
>> arithmetic(interval0, code)

La salida es:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


---------------------------------------------
   1       3/4      9/16     9/16     9/16   |sup
   -        -        -        -        -     |
   |        |        |        |        |     |
   |        |        X        X        |     |
   |        |        |        |        |     |
  3/4      9/16    27/64   135/256  567/1024 |
   |        |        |        |        |     |
   X        X        |        |        X     |
   |        |        |        |        |     |
   -        -        -        -        -     |
   0        0        0      27/64   135/256  |inf
=============================================
   0        0        1        1        0     |code
---------------------------------------------

Pasando los extremos del último intervalo a alguna base, se puede determinar el código final a la salida.

En este caso usamos base 2, el supremo e ínfimo (usando Qalculate! ):

1
2
3
4


> 567/1023 to base 2
      567 / 1023 ≈ 0000,100011011110001101111000110111100
> 135/256 to base 2
      135 / 256 = 0000,10000111

Lo que implica que el código final es: [1, 0, 0, 0]

Para un ejemplo de decodificación:

Dada una distribución acumulada que ofrece el intervalo [0, 3/4, 1] con un entero 1/2, la decodificación en 5 pasos.

1
2
3


>> interval0 = [0, sp.Rational(3, 4), 1]
>> valor = sp.Rational(1, 2) 
>> arithmetic_value(interval0, valor, 5)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


value=1/2------------------------------------
   1       3/4      9/16     9/16   135/256  |sup
   -        -        -        -        -     |
   |        |        |        |        |     |
   |        |        X        |        |     |
   |        |        |        |        |     |
  3/4      9/16    27/64   135/256  513/1024 |
   |        |        |        |        |     |
   X        X        |        X        X     |
   |        |        |        |        |     |
   -        -        -        -        -     |
   0        0        0      27/64    27/64   |inf
=============================================
   0        0        1        0        0     |code
---------------------------------------------
Con 5 pasos se obtiene [0, 0, 1, 0, 0]

Ejercicios resueltos

En el repositorio también se encuentran ejercicios resueltos. Los PDF se producen mediante pandoc markdown, por la simple sintaxis y la posibilidad de introducir $\LaTeX$ y figuras.

Machete

Es posible armar machetes de ecuaciones con pandoc markdown. Puede parecer intimidante escribir tantas ecuaciones de $\LaTeX$ pero es posible aligerar la carga usando cosas como Mathpix Snip.