Codificación aritmética

La codificación aritmética (AC) es una forma de codificación de entropía utilizada en la compresión de datos sin pérdidas. Normalmente, una cadena de caracteres se representa utilizando un número fijo de bits por carácter, como en el código ASCII. Cuando una cadena se convierte a codificación aritmética, los caracteres de uso frecuente se almacenarán con menos bits y los caracteres que no aparecen con tanta frecuencia se almacenarán con más bits, lo que da como resultado que se utilicen menos bits en total. La codificación aritmética difiere de otras formas de codificación de entropía, como la codificación de Huffman, en que en lugar de separar la entrada en símbolos componentes y reemplazar cada uno con un código, la codificación aritmética codifica el mensaje completo en un solo número, una fracción de precisión arbitraria q, donde 0.0 ≤ q < 1.0. Representa la información actual como un rango, definido por dos números. Una familia reciente de codificadores de entropía llamados sistemas numéricos asimétricos permite implementaciones más rápidas gracias a operar directamente en un único número natural que representa la información actual.

Un ejemplo de codificación aritmética asumiendo una distribución de probabilidad fija de tres símbolos "A", "B", y "C". La probabilidad de "A" es del 50%, la probabilidad de "B" es del 33% y la probabilidad de "C" es del 17%. Además, suponemos que la profundidad de recursión se conoce en cada paso. En el primer paso codificamos "B" que está dentro del intervalo [0.5, 0.83): El número binario "0.10x" es el código más corto que representa un intervalo que está completamente dentro [0.5, 0.83). "x" significa una secuencia arbitraria de bits. Hay dos casos extremos: los más pequeños x significa cero que representa el lado izquierdo del intervalo representado. Luego el lado izquierdo del intervalo es dec(0.10) = 0.5. En el otro extremo, x significa una secuencia finita de los que tiene el límite superior dec(0.11) = 0.75. Por lo tanto, "0.10x" representa el intervalo [0.5, 0.75) que está dentro [0.5, 0.83). Ahora podemos dejar fuera la parte "0." ya que todos los intervalos comienzan con "0." y podemos ignorar el "x"parte porque no importa qué bit-sequence representa, nos quedaremos dentro [0.5, 0.75).

Detalles de implementación y ejemplos

Codificación del mensaje "WIKI" con codificación aritmética

1.	Las frecuencias de la carta se encuentran.
2.	El intervalo [0, 1) se divide en la relación de las frecuencias.
3-5.	El intervalo correspondiente se divide iterativamente para cada letra en el mensaje.
6.	Cualquier valor en el intervalo final es elegido para representar el mensaje.
2*–6*.	La partición y el valor si el mensaje era "KIWI" en su lugar.

El ejemplo anterior se visualizó como un círculo, los valores en la codificación roja "WIKI" y "KIWI" – en la imagen SVG, saltan sobre un intervalo para destacarlo y mostrar sus estadísticas

Probabilidades iguales

En el caso más simple, la probabilidad de que ocurra cada símbolo es igual. Por ejemplo, considere un conjunto de tres símbolos, A, B y C, cada uno con la misma probabilidad de ocurrir. La codificación de bloque simple requeriría 2 bits por símbolo, lo que es un desperdicio: una de las variaciones de bit nunca se usa. Es decir, los símbolos A, B y C pueden codificarse respectivamente como 00, 01 y 10, con 11 sin usar.

Una solución más eficiente es representar una secuencia de estos tres símbolos como un número racional en base 3 donde cada dígito representa un símbolo. Por ejemplo, la secuencia "ABBCAB" podría convertirse en 0.011201₃, en codificación aritmética como un valor en el intervalo [0, 1). El siguiente paso es codificar este número ternario utilizando un número binario de punto fijo de suficiente precisión para recuperarlo, como 0.0010110010₂, esto es solo 10 bits; Se ahorran 2 bits en comparación con la codificación de bloques ingenua. Esto es factible para secuencias largas porque existen algoritmos eficientes en el lugar para convertir la base de números arbitrariamente precisos.

Para decodificar el valor, sabiendo que la cadena original tenía una longitud 6, uno simplemente puede volver a convertir a la base 3, redondear a 6 dígitos y recuperar la cadena.

Definiendo un modelo

En general, los codificadores aritméticos pueden generar resultados casi óptimos para cualquier conjunto de símbolos y probabilidades. (El valor óptimo es −log₂P bits para cada símbolo de probabilidad P; consulte Teorema de codificación de fuentes.) Los algoritmos de compresión que usan codificación aritmética comienzan determinando un modelo de los datos, básicamente una predicción de qué patrones se encontrarán en los símbolos del mensaje. Cuanto más precisa sea esta predicción, más cerca de la óptima será la salida.

Ejemplo: un modelo estático simple para describir el resultado de un instrumento de monitoreo en particular a lo largo del tiempo podría ser:

• 60% de probabilidad de símbolo NEUTRAL
• 20% de probabilidad de símbolo POSITIVE
• 10% de probabilidad de símbolo NEGATIVE
• 10% de probabilidad de símbolo END-OF-DATA. (La presencia de este símbolo significa que el flujo será 'internally terminada', como es bastante común en la compresión de datos; cuando este símbolo aparece en el flujo de datos, el decodificador sabrá que todo el flujo ha sido decodificado.)

Los modelos también pueden manejar alfabetos que no sean el conjunto simple de cuatro símbolos elegido para este ejemplo. También son posibles modelos más sofisticados: el modelado de orden superior cambia su estimación de la probabilidad actual de un símbolo en función de los símbolos que lo preceden (el contexto), de modo que en un modelo para texto en inglés, por ejemplo, el porcentaje de probabilidad de "u" sería mucho mayor cuando sigue a una "Q" o una "q". Los modelos pueden incluso ser adaptables, de modo que cambien continuamente su predicción de los datos en función de lo que realmente contiene la transmisión. El decodificador debe tener el mismo modelo que el codificador.

Codificación y decodificación: descripción general

En general, cada paso del proceso de codificación, excepto el último, es el mismo; el codificador tiene básicamente solo tres datos a considerar:

• El próximo símbolo que necesita ser codificado
• El intervalo actual (en el comienzo mismo del proceso de codificación, el intervalo se establece a [0,1], pero eso cambiará)
• Las probabilidades que el modelo asigna a cada uno de los diversos símbolos que son posibles en esta etapa (como se mencionó anteriormente, modelos de orden superior o adaptables significan que estas probabilidades no son necesariamente iguales en cada paso.)

El codificador divide el intervalo actual en subintervalos, cada uno de los cuales representa una fracción del intervalo actual proporcional a la probabilidad de ese símbolo en el contexto actual. Cualquiera que sea el intervalo que corresponda al símbolo real que se va a codificar a continuación, se convierte en el intervalo utilizado en el siguiente paso.

Ejemplo: para el modelo de cuatro símbolos anterior:

• el intervalo para NEUTRAL sería [0, 0.6)
• el intervalo para POSITIVE sería [0.6, 0.8)
• el intervalo para NEGATIVE sería [0.8, 0.9)
• el intervalo para END-OF-DATA sería [0.9, 1).

Cuando se han codificado todos los símbolos, el intervalo resultante identifica sin ambigüedades la secuencia de símbolos que lo produjeron. Cualquiera que tenga el mismo intervalo final y el mismo modelo que se está utilizando puede reconstruir la secuencia de símbolos que debe haber ingresado al codificador para dar como resultado ese intervalo final.

Sin embargo, no es necesario transmitir el intervalo final; solo es necesario transmitir una fracción que se encuentre dentro de ese intervalo. En particular, solo es necesario transmitir suficientes dígitos (en cualquier base) de la fracción para que todas las fracciones que comiencen con esos dígitos caigan en el intervalo final; esto garantizará que el código resultante sea un código de prefijo.

Codificación y decodificación: ejemplo

Un diagrama que muestra decodificación de 0.538 (el punto redondo) en el modelo de ejemplo. La región se divide en subregiones proporcionales a frecuencias de símbolos, y la subregión que contiene el punto se subdivide sucesivamente de la misma manera.

Considere el proceso para decodificar un mensaje codificado con el modelo de cuatro símbolos dado. El mensaje está codificado en la fracción 0.538 (usando decimal para mayor claridad, en lugar de binario; también suponiendo que solo hay tantos dígitos como sea necesario para decodificar el mensaje).

El proceso comienza con el mismo intervalo que usa el codificador: [0,1), y usando el mismo modelo, dividiéndolo en los mismos cuatro subintervalos que debe tener el codificador. La fracción 0,538 cae en el subintervalo de NEUTRO, [0, 0,6); esto indica que el primer símbolo que leyó el codificador debe haber sido NEUTRO, por lo que este es el primer símbolo del mensaje.

A continuación, divida el intervalo [0, 0.6) en subintervalos:

• el intervalo para NEUTRAL sería [0, 0.36), 60% de [0,6].
• el intervalo para POSITIVE sería [0.36, 0.48] 20% de [0,6].
• el intervalo para NEGATIVE sería [0.48, 0.54), 10% de [0,6].
• el intervalo para END-OF-DATA sería [0.54, 0.6), 10% de [0,6].

Dado que 0.538 está dentro del intervalo [0.48, 0.54], el segundo símbolo del mensaje debe haber sido NEGATIVO.

Vuelva a dividir nuestro intervalo actual en subintervalos:

• el intervalo para NEUTRAL sería [0.48, 0.516).
• el intervalo para POSITIVE sería [0.516, 0.528).
• el intervalo para NEGATIVE sería [0.528, 0.534).
• el intervalo para END-OF-DATA sería [0.534, 0.540).

Ahora 0,538 cae dentro del intervalo del símbolo FIN DE DATOS; por lo tanto, este debe ser el siguiente símbolo. Dado que también es el símbolo de terminación interna, significa que la decodificación está completa. Si la secuencia no termina internamente, debe haber alguna otra forma de indicar dónde se detiene la secuencia. De lo contrario, el proceso de decodificación podría continuar para siempre, leyendo por error más símbolos de la fracción de los que en realidad estaban codificados en ella.

Fuentes de ineficiencia

El mensaje 0.538 en el ejemplo anterior podría haber sido codificado por las fracciones igualmente cortas 0.534, 0.535, 0.536, 0.537 o 0.539. Esto sugiere que el uso de decimal en lugar de binario introdujo alguna ineficiencia. Esto es correcto; el contenido de información de un decimal de tres dígitos es ${displaystyle 3times log _{2}(10)approx 9.966}$ bits; el mismo mensaje podría haber sido codificado en la fracción binaria 0.10001010 (equivalente a 0.5390625 decimal) a un costo de sólo 8bits. (El cero final debe especificarse en la fracción binaria, o de lo contrario el mensaje sería ambiguo sin información externa como el tamaño de flujo comprimido.)

Esta salida de 8 bits es mayor que el contenido de la información o la entropía del mensaje, que es

${displaystyle sum -log _{2}(p_{i})=-log _{2}(0.6)-log _{2}(0.1)-log _{2}(0.1)=7.381{text{ bits}}.}$

Pero se debe usar un número entero de bits en la codificación binaria, por lo que un codificador para este mensaje usaría al menos 8 bits, lo que daría como resultado un mensaje un 8,4 % más grande que el contenido de entropía. Esta ineficiencia de 1 bit como máximo da como resultado una sobrecarga relativamente menor a medida que crece el tamaño del mensaje.

Además, las probabilidades de los símbolos reclamados fueron [0,6, 0,2, 0,1, 0,1), pero las frecuencias reales en este ejemplo son [0,33, 0, 0,33, 0,33). Si se reajustan los intervalos para estas frecuencias, la entropía del mensaje sería de 4,755 bits y el mismo mensaje NEUTRO NEGATIVO FIN DE DATOS podría codificarse como intervalos [0, 1/3); [1/9, 2/9); [27/5, 27/6]); y un intervalo binario de [0.00101111011, 0.00111000111). Este también es un ejemplo de cómo los métodos de codificación estadística, como la codificación aritmética, pueden producir un mensaje de salida que es más grande que el mensaje de entrada, especialmente si el modelo de probabilidad está desactivado.

Codificación aritmética adaptativa

Una ventaja de la codificación aritmética sobre otros métodos similares de compresión de datos es la conveniencia de la adaptación. Adaptación es el cambio de las tablas de frecuencia (o probabilidad) mientras se procesan los datos. Los datos decodificados coinciden con los datos originales siempre que la tabla de frecuencias en la decodificación se reemplace de la misma manera y en el mismo paso que en la codificación. La sincronización se basa, normalmente, en una combinación de símbolos que se producen durante el proceso de codificación y decodificación.

Precisión y renormalización

Las explicaciones anteriores de la codificación aritmética contienen algunas simplificaciones. En particular, se escriben como si el codificador primero calculara las fracciones que representan los puntos finales del intervalo en su totalidad, utilizando una precisión infinita, y solo convirtiera la fracción a su forma final al final de la codificación. En lugar de intentar simular una precisión infinita, la mayoría de los codificadores aritméticos operan con un límite fijo de precisión que saben que el decodificador podrá igualar, y redondean las fracciones calculadas a sus equivalentes más cercanos con esa precisión. Un ejemplo muestra cómo funcionaría esto si el modelo requiriera que el intervalo [0,1) se dividiera en tercios, y esto se aproximara con una precisión de 8 bits. Tenga en cuenta que, dado que ahora se conoce la precisión, también se conocen los rangos binarios que podremos usar.

Un proceso llamado renormalización evita que la precisión finita se convierta en un límite en el número total de símbolos que se pueden codificar. Cada vez que el rango se reduce hasta el punto en que todos los valores del rango comparten ciertos dígitos iniciales, esos dígitos se envían a la salida. Por muchos dígitos de precisión que la computadora pueda manejar, ahora está manejando menos que eso, por lo que los dígitos existentes se desplazan a la izquierda y, a la derecha, se agregan nuevos dígitos para expandir el rango tanto como sea posible. posible. Tenga en cuenta que este resultado ocurre en dos de los tres casos de nuestro ejemplo anterior.

Codificación aritmética como cambio generalizado de raíz

Recuerde que en el caso de que los símbolos tuvieran las mismas probabilidades, la codificación aritmética podría implementarse mediante un simple cambio de base o raíz. En general, la codificación aritmética (y de rango) puede interpretarse como un cambio de raíz generalizado. Por ejemplo, podemos mirar cualquier secuencia de símbolos:

${displaystyle mathrm {DABDDB}$

como un número en una base determinada, suponiendo que los símbolos involucrados forman un conjunto ordenado y cada símbolo en el conjunto ordenado denota un número entero secuencial A = 0, B = 1, C = 2, D = 3, y así sucesivamente. Esto da como resultado las siguientes frecuencias y frecuencias acumuladas:

La frecuencia acumulada de un elemento es la suma de todas las frecuencias que preceden al elemento. En otras palabras, la frecuencia acumulada es un total acumulado de frecuencias.

En un sistema de numeración posicional, la base, o base, es numéricamente igual a una cantidad de símbolos diferentes utilizados para expresar el número. Por ejemplo, en el sistema decimal, el número de símbolos es 10, es decir, 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. La raíz se usa para expresar cualquier número entero finito en un supuesto multiplicador en forma polinómica. Por ejemplo, el número 457 es en realidad 4×10² + 5×10¹ + 7×10⁰, donde se presume la base 10 pero no se muestra explícitamente.

Al principio, convertiremos DABDDB en un número de base 6, porque 6 es la longitud de la cadena. La cadena se asigna primero a la cadena de dígitos 301331, que luego se asigna a un número entero por el polinomio:

${displaystyle 6^{5}times 3+6^{4}times 0+6^{3}times 1+6^{2}times 3+6^{1}times 3+6^{0}times 1=23671}$

El resultado 23671 tiene una longitud de 15 bits, que no se acerca mucho al límite teórico (la entropía del mensaje), que es de aproximadamente 9 bits.

Para codificar un mensaje con una longitud más cercana al límite teórico impuesto por la teoría de la información, necesitamos generalizar ligeramente la fórmula clásica para cambiar la raíz. Calcularemos los límites inferior y superior L y U y elegiremos un número entre ellos. Para el cálculo de L, multiplicamos cada término de la expresión anterior por el producto de las frecuencias de todos los símbolos anteriores:

${displaystyle {begin{aligned}L={} {6^{5}times 3)+{}\\\\fnMis (6^{4}times 0)+{}\fnMicrosoft Sans 1)times (6^{3}times 1) + {}\\\fnMicrosoft Sans 2)times (6^{2}times 3)+{}\\fn1times 2times 3)times (6^{1}times 3)+{}\fn1times 2times 3times 3)times (6^{0}times 1) {={} {} {}} {f}}} {fn}}}}}} {\\\\\\\\\\\\\\\}}}}}}}}\\\\\\\\\\\\}}}}}}}}}}}}}}}}}}}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\$

La diferencia entre este polinomio y el polinomio anterior es que cada término se multiplica por el producto de las frecuencias de todos los símbolos anteriores. Más generalmente, L se puede calcular como:

${displaystyle L=sum ¿Qué? ¿Qué?$

Donde ${displaystyle scriptstyle C_{i}$ son las frecuencias acumulativas y ${displaystyle scriptstyle f_{k}$ son las frecuencias de ocurrencias. Los índices denotan la posición del símbolo en un mensaje. En el caso especial donde todas las frecuencias ${displaystyle scriptstyle f_{k}$ son 1, esta es la fórmula de cambio de base.

El límite superior U será L más el producto de todas las frecuencias; en este caso U = L + (3 × 1 × 2 × 3 × 3 × 2) = 25002 + 108 = 25110. En general, U está dada por:

${displaystyle U=L+prod ¿Qué?$

Ahora podemos elegir cualquier número del intervalo [L, U) para representar el mensaje; una opción conveniente es el valor con el rastro de ceros más largo posible, 25100, ya que nos permite lograr la compresión al representar el resultado como 251×10². Los ceros también se pueden truncar, dando 251, si la longitud del mensaje se almacena por separado. Los mensajes más largos tenderán a tener rastros más largos de ceros.

Para decodificar el entero 25100, el cálculo del polinomio se puede invertir como se muestra en la siguiente tabla. En cada etapa se identifica el símbolo actual, luego se resta el término correspondiente del resultado.

Durante la decodificación, tomamos la palabra después de dividir por la potencia correspondiente de 6. Luego, el resultado se compara con los intervalos acumulativos y se selecciona el símbolo apropiado de la tabla de búsqueda. Cuando se identifica el símbolo, se corrige el resultado. El proceso continúa durante la duración conocida del mensaje o mientras el resultado restante sea positivo. La única diferencia en comparación con el cambio de base clásico es que puede haber un rango de valores asociados con cada símbolo. En este ejemplo, A siempre es 0, B es 1 o 2 y D es cualquiera de 3, 4, 5. Esto está exactamente de acuerdo con nuestros intervalos que están determinados por las frecuencias. Cuando todos los intervalos son iguales a 1 tenemos un caso especial del clásico cambio de base.

Límite teórico de mensaje comprimido

El límite inferior L nunca supera nⁿ, donde n es el tamaño del mensaje, y así puede ser representado en ${displaystyle log _{2}(n^{n})=nlog _{2}(n)}$ bits. Después de la computación del límite superior U y la reducción del mensaje seleccionando un número del intervalo [L,U) con el sendero más largo de ceros podemos suponer que esta longitud puede ser reducida por ${displaystyle textstyle log _{2}left(prod ¿Qué?$ bits. Puesto que cada frecuencia en un producto ocurre exactamente el mismo número de veces que el valor de esta frecuencia, podemos utilizar el tamaño del alfabeto A para el cálculo del producto

${displaystyle prod _{k=1}{n}f_{k}=prod ¿Qué?$

Aplicando log₂ para la cantidad estimada de bits en el mensaje, el mensaje final (sin contar una sobrecarga logarítmica para las tablas de longitud y frecuencia del mensaje) coincidirá con la cantidad de bits dada por la entropía, que para mensajes largos está muy cerca de lo óptimo:

${displaystyle -left[sum ¿Por qué?$

Conexiones con otros métodos de compresión

Codificación Huffman

Debido a que la codificación aritmética no comprime un dato a la vez, puede acercarse arbitrariamente a la entropía al comprimir cadenas IID. Por el contrario, el uso de la extensión de la codificación de Huffman (a cadenas) no alcanza la entropía a menos que todas las probabilidades de los símbolos alfabéticos sean potencias de dos, en cuyo caso tanto la codificación de Huffman como la aritmética alcanzan la entropía.

Cuando Huffman codifica ingenuamente cadenas binarias, no es posible la compresión, incluso si la entropía es baja (por ejemplo, ({0, 1}) tiene probabilidades {0,95, 0,05}). La codificación Huffman asigna 1 bit a cada valor, lo que da como resultado un código de la misma longitud que la entrada. Por el contrario, la codificación aritmética comprime bien los bits, acercándose a la relación de compresión óptima de

${displaystyle 1-[-0.95log _{2}(0.95)+-0.05log _{2}(0.05)]approx 71.4$

Una forma sencilla de abordar la subóptima codificación de Huffman es concatenar símbolos ('bloquear') para formar un nuevo alfabeto en el que cada nuevo símbolo representa una secuencia de símbolos originales, en este caso bits. – del alfabeto original. En el ejemplo anterior, la agrupación de secuencias de tres símbolos antes de la codificación produciría nuevos "supersímbolos" con las siguientes frecuencias:

• 000: 85,7%
• 001, 010, 100: 4,5% cada uno
• 011, 101, 110: 0.24% cada uno
• 111: 0,0125%

Con esta agrupación, la codificación Huffman promedios 1.3 bits por cada tres símbolos, o 0.433 bits por símbolo, en comparación con un bit por símbolo en la codificación original, es decir, ${displaystyle 56.7$ compresión. Permitir secuencias arbitrariamente grandes se acerca arbitrariamente a la entropía – al igual que la codificación aritmética – pero requiere códigos enormes para hacerlo, así que no es tan práctico como codificación aritmética para este propósito.

Una alternativa es la codificación de longitudes de ejecución a través de códigos Golomb-Rice basados en Huffman. Este enfoque permite una codificación/decodificación más simple y rápida que la codificación aritmética o incluso la codificación Huffman, ya que este último requiere una búsqueda de tabla. En el ejemplo {0.95, 0.05}, un código Golomb-Rice con un resto de cuatro bits logra una relación de compresión de ${displaystyle 71.1$, mucho más cerca de lo óptimo que usar bloques de tres bits. Los códigos Golomb-Rice sólo se aplican a las entradas de Bernoulli como la de este ejemplo, sin embargo, por lo que no es un sustituto para bloquear en todos los casos.

Historia y patentes

Los algoritmos básicos para la codificación aritmética fueron desarrollados de forma independiente por Jorma J. Rissanen, en IBM Research, y por Richard C. Pasco, Ph.D. estudiante de la Universidad de Stanford; ambos fueron publicados en mayo de 1976. Pasco cita un borrador previo a la publicación del artículo de Rissanen y comenta sobre la relación entre sus trabajos:

Un algoritmo de la familia fue desarrollado independientemente por Rissanen [1976]. Cambia el elemento de código al extremo más significativo del acumulador, utilizando un puntero obtenido por adición y exponente. Ahora compararemos las alternativas en las tres opciones, y veremos que es preferible cambiar el elemento de código en lugar del acumulador, y añadir elementos de código al extremo menos significativo del acumulador.

Menos de un año después de la publicación, IBM solicitó una patente estadounidense sobre el trabajo de Rissanen. El trabajo de Pasco no fue patentado.

Una variedad de técnicas específicas para la codificación aritmética han estado históricamente cubiertas por patentes de EE. UU., aunque desde entonces varios métodos bien conocidos han pasado al dominio público cuando las patentes han expirado. Las técnicas cubiertas por patentes pueden ser esenciales para implementar los algoritmos de codificación aritmética que se especifican en algunos estándares internacionales formales. Cuando este es el caso, tales patentes generalmente están disponibles para licencia bajo lo que se llama "razonable y no discriminatoria" (RAND) términos de licencia (al menos como una cuestión de política del comité de estándares). En algunos casos bien conocidos (incluidos algunos relacionados con patentes de IBM que ya expiraron), dichas licencias estaban disponibles de forma gratuita y, en otros casos, se requerían tarifas de licencia. La disponibilidad de licencias bajo términos RAND no necesariamente satisface a todos los que quieran usar la tecnología, ya que lo que puede parecer "razonable" para una empresa que prepara un producto de software comercial propietario puede parecer mucho menos razonable para un proyecto de software libre o de código abierto.

Al menos un importante programa de software de compresión, bzip2, descontinuó deliberadamente el uso de la codificación aritmética en favor de la codificación Huffman debido a la situación de patentes percibida en ese momento. Además, los codificadores y decodificadores del formato de archivo JPEG, que tiene opciones tanto para la codificación Huffman como para la codificación aritmética, generalmente solo admiten la opción de codificación Huffman, que originalmente se debió a problemas de patentes; el resultado es que casi todas las imágenes JPEG que se utilizan hoy en día utilizan la codificación Huffman, aunque las patentes de codificación aritmética de JPEG han expirado debido a la antigüedad del estándar JPEG (cuyo diseño se completó aproximadamente en 1990). JPEG XL, así como archivadores como PackJPG, Brunsli y Lepton, que pueden convertir sin pérdidas archivos codificados por Huffman a otros con codificación aritmética (o sistemas numéricos asimétricos en el caso de JPEG XL), mostrando hasta un 25 % de ahorro de tamaño.

El algoritmo de codificación aritmética del formato de compresión de imágenes JPEG se basa en las siguientes patentes citadas (ya vencidas).

• U.S. Patent 4,652,856 – (IBM) Filed 4 February 1986, granted 24 March 1987 – Kottappuram M. A. Mohiuddin, Jorma Johannes Rissanen – Código aritmético multi-alfabet libre de multi-alfabet
• U.S. Patent 4,905,297 – (IBM) Filed 18 November 1988, granted 27 February 1990 – Glen George Langdon, Joan L. Mitchell, William B. Pennebaker, Jorma Johannes Rissanen – Arithmetic coding encoder and decoder system
• U.S. Patent 4,935,882 – (IBM) Filed 20 July 1988, granted 19 June 1990 – William B. Pennebaker, Joan L. Mitchell – Adaptación de probabilidad para codificadores aritméticos
• JP Patent 1021672 – (Mitsubishi) Filed 21 January 1989, granted 10 August 1990 – Toshihiro Kimura, Shigenori Kino, Fumitaka Ono, Masayuki Yoshida – Sistema de codificación
• JP Patente 2-46275 – (Mitsubishi) Filed 26 February 1990, granted 5 November 1991 – Fumitaka Ono, Tomohiro Kimura, Masayuki Yoshida, Shigenori Kino – Método de codificación y codificación

Otras patentes (en su mayoría también vencidas) relacionadas con la codificación aritmética incluyen las siguientes.

• U.S. Patent 4,122,440 – (IBM) Archivado el 4 de marzo de 1977, otorgado el 24 de octubre de 1978 – Glen George Langdon, Jorma Johannes Rissanen – Método y medios para codificación de cadena aritmética
• U.S. Patent 4,286,256 – (IBM) Filed 28 November 1979, granted 25 August 1981 – Glen George Langdon, Jorma Johannes Rissanen – Method and means for arithmetic coding useing a reduced number of operations
• U.S. Patent 4.467.317 – (IBM) Filed 30 March 1981, granted 21 August 1984 – Glen George Langdon, Jorma Johannes Rissanen – Codificación de compresión aritmética de alta velocidad mediante actualización de valor concurrente
• U.S. Patent 4,891,643 – (IBM) Filed 15 September 1986, granted 2 January 1990 – Joan L. Mitchell, William B. Pennebaker – Arithmetic coding data compresión/de-compression by selectively employed, diverse arithmetic coding encoders and decoders
• JP Patent 11782787 – (NEC) Filed 13 May 1987, granted 18 November 1988 – Michio Shimada – Data compresing arithmetic encoding device
• JP Patent 15015487 – (KDDI) Filed 18 June 1987, granted 22 December 1988 – Shuichi Matsumoto, Masahiro Saito – System for preventing carrying propagation in arithmetic coding
• U.S. Patente 4,933,883 – (IBM) Filed 3 May 1988, granted 12 June 1990 – William B. Pennebaker, Joan L. Mitchell – Adaptación de probabilidad para codificadores aritméticos
• U.S. Patent 4,989.000 – (IBM) Filed 19 June 1989, granted 29 January 1991 – Dan S. Chevion, Ehud D. Karnin, Eugeniusz Walach – Compresión de cadenas de datos mediante codificación aritmética con estimación de subintervalo de probabilidad simplificada
• U.S. Patent 5,099,440 – (IBM) Filed 5 January 1990, granted 24 March 1992 – William B. Pennebaker, Joan L. Mitchell – Adaptación de probabilidad para codificadores aritméticos
• U.S. Patent 5,272,478 – (Ricoh) Filed 17 Agosto 1992, concedió 21 Diciembre 1993 – James D. Allen – Método y aparato para la codificación entropía

Nota: esta lista no es exhaustiva. Consulte los siguientes enlaces para obtener una lista de más patentes estadounidenses. El códec Dirac utiliza codificación aritmética y no está pendiente de patente.

Pueden existir patentes sobre codificación aritmética en otras jurisdicciones; ver patentes de software para una discusión sobre la patentabilidad del software en todo el mundo.

Benchmarks y otras características técnicas

Cada implementación programática de la codificación aritmética tiene una relación de compresión y un rendimiento diferentes. Si bien las relaciones de compresión varían solo un poco (generalmente menos del 1%), el tiempo de ejecución del código puede variar en un factor de 10. Elegir el codificador adecuado de una lista de codificadores disponibles públicamente no es una tarea sencilla porque el rendimiento y la relación de compresión también dependen de el tipo de datos, particularmente sobre el tamaño del alfabeto (número de símbolos diferentes). Uno de los dos codificadores particulares puede tener un mejor rendimiento para alfabetos pequeños, mientras que el otro puede mostrar un mejor rendimiento para alfabetos grandes. La mayoría de los codificadores tienen limitaciones en el tamaño del alfabeto y muchos de ellos están especializados en alfabetos de exactamente dos símbolos (0 y 1).