codificación golomb

Método de compresión de datos sin pérdidas

La codificación Golomb es un método de compresión de datos sin pérdidas que utiliza una familia de códigos de compresión de datos inventados por Solomon W. Golomb en la década de 1960. Los alfabetos que siguen una distribución geométrica tendrán un código Golomb como código de prefijo óptimo , ^[1] lo que hace que la codificación Golomb sea muy adecuada para situaciones en las que la aparición de valores pequeños en el flujo de entrada es significativamente más probable que los valores grandes.

Codificación del arroz

La codificación Rice (inventada por Robert F. Rice) denota el uso de un subconjunto de la familia de códigos Golomb para producir un código de prefijo más simple (pero posiblemente subóptimo). Rice utilizó este conjunto de códigos en un esquema de codificación adaptativo ; La "codificación de arroz" puede referirse a ese esquema adaptativo o al uso de ese subconjunto de códigos Golomb. Mientras que un código Golomb tiene un parámetro ajustable que puede ser cualquier valor entero positivo, los códigos Rice son aquellos en los que el parámetro ajustable es una potencia de dos. Esto hace que los códigos Rice sean convenientes para su uso en una computadora, ya que la multiplicación y división por 2 se pueden implementar de manera más eficiente en aritmética binaria .

Rice se sintió motivado a proponer este subconjunto más simple debido al hecho de que las distribuciones geométricas a menudo varían con el tiempo, no se conocen con precisión o ambas cosas, por lo que seleccionar el código aparentemente óptimo podría no ser muy ventajoso.

La codificación Rice se utiliza como etapa de codificación de entropía en varios métodos de compresión de imágenes y datos de audio sin pérdidas .

Descripción general

Ejemplo de codificación Golomb para una fuente x con distribución geométrica, con parámetro p (0) = 0.2 , usando código Golomb con M = 3 . El código 00 de 2 bits se utiliza el 20% del tiempo; los códigos de 3 bits 010, 011 y 100 se utilizan más del 38% del tiempo; En una minoría de casos se necesitan 4 bits o más. Para esta fuente, entropía = 3,610 bits; para este código con esta fuente, velocidad = 3,639 bits; por lo tanto, redundancia = 0,030 bits o eficiencia = 0,992 bits por bit.

Construcción de códigos

La codificación Golomb utiliza un parámetro ajustable M para dividir un valor de entrada x en dos partes: q , el resultado de una división por M , y r , el resto. El cociente se envía en codificación unaria , seguido del resto en codificación binaria truncada . Cuando , la codificación Golomb es equivalente a la codificación unaria. ${\displaystyle M=1}$

Los códigos Golomb-Rice se pueden considerar como códigos que indican un número por la posición del contenedor ( q ) y el desplazamiento dentro del contenedor ( r ). La figura de ejemplo muestra la posición q y el desplazamiento r para la codificación del número entero x usando el parámetro M de Golomb-Rice = 3 , con probabilidades de origen siguiendo una distribución geométrica con p (0) = 0,2 .

Formalmente, las dos partes vienen dadas por la siguiente expresión, donde x es el número entero no negativo que se codifica:

${\displaystyle q=\left\lfloor {\frac {x}{M}}\right\rfloor }$

y

${\displaystyle r=x-qM}$.

Esta imagen muestra la redundancia, en bits, del código Golomb, cuando se elige M de manera óptima, para 1 − p (0) ≥ 0,45

Tanto q como r se codificarán utilizando números variables de bits: q mediante un código unario y r mediante b bits para el código Rice, o una elección entre b y b +1 bits para el código Golomb (es decir, M no es una potencia de 2). ), con . Si , entonces use b bits para codificar r ; de lo contrario, utilice b +1 bits para codificar r . Claramente, si M es una potencia de 2 y podemos codificar todos los valores de r con b bits. ${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$ ${\displaystyle r<2^{b+1}-M}$ ${\displaystyle b=\log _{2}(M)}$

El número entero x tratado por Golomb fue la longitud de ejecución de un proceso de Bernoulli , que tiene una distribución geométrica que comienza en 0. La mejor elección del parámetro M es una función del proceso de Bernoulli correspondiente, que está parametrizado por la probabilidad de éxito en un proceso dado. Juicio Bernoulli . M es la mediana de la distribución o la mediana ±1. Puede ser determinado por estas desigualdades: ${\displaystyle p=P(x=0)}$

${\displaystyle (1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M},}$

que se resuelven por

${\displaystyle M=\left\lceil -{\frac {\log(2-p)}{\log(1-p)}}\right\rceil }$.

Para el ejemplo con p (0) = 0,2 :

${\displaystyle M=\left\lceil -{\frac {\log(1.8)}{\log(0.8)}}\right\rceil =\left\lceil 2.634\right\rceil =3}$.

El código Golomb para esta distribución es equivalente al código Huffman para las mismas probabilidades, si fuera posible calcular el código Huffman para el conjunto infinito de valores fuente.

Usar con enteros con signo

El esquema de Golomb fue diseñado para codificar secuencias de números no negativos. Sin embargo, se puede ampliar fácilmente para aceptar secuencias que contengan números negativos utilizando un esquema de superposición e intercalado , en el que todos los valores se reasignan a algún número positivo de una manera única y reversible. La secuencia comienza: 0, −1, 1, −2, 2, −3, 3, −4, 4, ... El n -ésimo valor negativo (es decir, ⁠ ⁠ ${\displaystyle -n}$ ) se asigna al n ^ésimo número impar ( ⁠ ⁠ ${\displaystyle 2n-1}$ ), y el m ^-ésimo valor positivo se asigna al m -ésimo número par ( ⁠ ⁠ ${\displaystyle 2m}$ ). Esto se puede expresar matemáticamente de la siguiente manera: un valor positivo x se asigna a ( ) y un valor negativo y se asigna a ( ). Un código de este tipo puede utilizarse por motivos de simplicidad, aunque no sea óptimo. Los códigos verdaderamente óptimos para distribuciones geométricas de dos lados incluyen múltiples variantes del código Golomb, dependiendo de los parámetros de distribución, incluido éste. ^[2] ${\displaystyle x'=2|x|=2x,\ x\geq 0}$ ${\displaystyle y'=2|y|-1=-2y-1,\ y<0}$

algoritmo simple

A continuación se muestra la codificación Rice-Golomb, donde el código restante utiliza una codificación binaria truncada simple, también denominada "codificación Rice" (otras codificaciones binarias de longitud variable, como codificaciones aritméticas o de Huffman, son posibles para los códigos restantes, si la distribución estadística de los códigos de resto no son planos, y especialmente cuando no se utilizan todos los restos posibles después de la división). En este algoritmo, si el parámetro M es una potencia de 2, se vuelve equivalente a la codificación Rice más simple:

1. Fije el parámetro M a un valor entero.
2. Para N , el número a codificar, encuentre
   1. cociente = q = piso( N / M )
   2. resto = r = N módulo M
3. Generar palabra clave
   1. El formato del código: <Código de cociente><Código restante>, donde
   2. Código de cociente (en codificación unaria )
      1. Escriba una cadena de longitud q de 1 bits (alternativamente, de 0 bits)
      2. Escribe un bit 0 (respectivamente, un bit 1)
   3. Código restante (en codificación binaria truncada )
      1. Dejar ${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$
         1. Si codifica r en representación binaria usando b bits. ${\displaystyle r<2^{b+1}-M}$
         2. Si codifica el número en representación binaria usando b + 1 bits. ${\displaystyle r\geq 2^{b+1}-M}$ ${\displaystyle r+2^{b+1}-M}$

Descodificación:

1. Decodifica la representación unaria de q (cuenta el número 1 al comienzo del código)
2. Saltar el delimitador 0
3. Dejar ${\displaystyle b=\lfloor \log _{2}(M)\rfloor }$
   1. Interprete los siguientes b bits como un número binario r' . Si se mantiene, entonces el recordatorio ${\displaystyle r'<2^{b+1}-M}$ ${\displaystyle r=r'}$
   2. De lo contrario, interprete b + 1 bits como un número binario r' , el recordatorio viene dado por ${\displaystyle r=r'-2^{b+1}+M}$
4. Calcular ${\displaystyle N=q*M+r}$

Ejemplo

Establezca M = 10 . De este modo . El límite es . ${\displaystyle b=\lfloor \log _{2}(10)\rfloor =3}$ ${\displaystyle 2^{b+1}-M=16-10=6}$

Por ejemplo, con una codificación Rice-Golomb usando el parámetro M = 10 , el número decimal 42 se dividiría primero en q = 4 y r = 2, y se codificaría como qcode( q ),rcode( r ) = qcode(4 ),rcode(2) = 11110,010 (no es necesario codificar la coma de separación en el flujo de salida, porque el 0 al final del código q es suficiente para decir cuándo termina q y comienza r ; tanto el código q y rcode están autodelimitados).

Uso para codificación de longitud de ejecución

Tenga en cuenta que p y 1 – p están invertidos en esta sección en comparación con el uso en secciones anteriores.

Dado un alfabeto de dos símbolos, o un conjunto de dos eventos, P y Q , con probabilidades p y ( 1 − p ) respectivamente, donde p ≥ 1/2 , la codificación de Golomb se puede utilizar para codificar ejecuciones de cero o más P ′ s separados por Q individuales . En esta aplicación, la mejor configuración del parámetro M es el número entero más cercano a . Cuando p = 1/2, M = 1, y el código Golomb corresponde a unario ( n ≥ 0 P ′s seguido de una Q se codifica como n unos seguidos de un cero). Si se desea un código más simple, se puede asignar el parámetro b de Golomb-Rice (es decir, el parámetro Golomb ) al número entero más cercano a ; aunque no siempre es el mejor parámetro, suele ser el mejor parámetro de Rice y su rendimiento de compresión está bastante cerca del código Golomb óptimo. (El propio Rice propuso usar varios códigos para los mismos datos para determinar cuál era mejor. Un investigador posterior del JPL propuso varios métodos para optimizar o estimar el parámetro del código. ^[3] ) ${\displaystyle -{\frac {1}{\log _{2}p}}}$ ${\displaystyle M=2^{b}}$ ${\displaystyle -\log _{2}(-\log _{2}p)}$

Considere usar un código Rice con una porción binaria que tenga b bits para codificar secuencias de longitud de ejecución donde P tiene una probabilidad p . Si es la probabilidad de que un bit forme parte de una ejecución de k bits ( P s y una Q ) y es la relación de compresión de esa ejecución, entonces la relación de compresión esperada es ${\displaystyle \mathbb {P} [{\text{bit is part of }}k{\text{-run}}]}$ ${\displaystyle k-1}$ ${\displaystyle ({\text{compression ratio of }}k{\text{-run}})}$

${\displaystyle {\begin{aligned}\mathbb {E} [{\text{compression ratio}}]&=\sum _{k=1}^{\infty }({\text{compression ratio of }}k{\text{-run}})\cdot \mathbb {P} [{\text{bit is part of }}k{\text{-run}}]\\&=\sum _{k=1}^{\infty }{\frac {b+1+\lfloor 2^{-b}(k-1)\rfloor }{k}}\cdot kp^{k-1}(1-p)^{2}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \sum _{i=j2^{b}+1}^{(j+1)2^{b}}p^{i-1}\\&=(1-p)^{2}\sum _{j=0}^{\infty }(b+1+j)\cdot \left(p^{2^{b}j}-p^{2^{b}(j+1)}\right)\\&=(1-p)\cdot \left(b+\sum _{m=0}^{\infty }p^{2^{b}m}\right)\\&=(1-p)\cdot \left(b+{\left(1-p^{2^{b}}\right)}^{-1}\right)\\\end{aligned}}}$

La compresión a menudo se expresa en términos de , la proporción comprimida. Para , el enfoque de codificación de longitud de ejecución da como resultado relaciones de compresión cercanas a la entropía . Por ejemplo, utilizando el código Rice para los rendimientos ${\displaystyle 1-\mathbb {E} [{\text{compression ratio}}]}$ ${\displaystyle p\approx 1}$ ${\displaystyle b=6}$ ${\displaystyle p=0.99}$91,89% de compresión, mientras que el límite de entropía es91,92% .

Codificación adaptable de Golomb-Rice de longitud de ejecución

Cuando no se conoce una distribución de probabilidad para números enteros, no se puede determinar el parámetro óptimo para un codificador Golomb-Rice. Por lo tanto, en muchas aplicaciones se utiliza un enfoque de dos pasos: primero, se escanea el bloque de datos para estimar una función de densidad de probabilidad (PDF) para los datos. Luego, el parámetro Golomb-Rice se determina a partir de esa PDF estimada. Una variación más simple de ese enfoque es asumir que la PDF pertenece a una familia parametrizada, estimar los parámetros de la PDF a partir de los datos y luego calcular el parámetro óptimo de Golomb-Rice. Ese es el enfoque utilizado en la mayoría de las aplicaciones que se analizan a continuación.

Un enfoque alternativo para codificar eficientemente datos enteros cuyo PDF no se conoce o varía es utilizar un codificador adaptable hacia atrás. El codificador RLGR [1] logra esto usando un algoritmo muy simple que ajusta el parámetro Golomb-Rice hacia arriba o hacia abajo, dependiendo del último símbolo codificado. Un decodificador puede seguir la misma regla para rastrear la variación de los parámetros de codificación, por lo que no es necesario transmitir información adicional, solo los datos codificados. Suponiendo un PDF gaussiano generalizado, que cubre una amplia gama de estadísticas vistas en datos como errores de predicción o coeficientes de transformación en códecs multimedia, el algoritmo de codificación RLGR puede funcionar muy bien en este tipo de aplicaciones.

Aplicaciones

Relaciones de compresión del experimento del algoritmo de Rice codificado por Golomb

Numerosos códecs de señales utilizan un código Rice para los residuos de predicción . En los algoritmos predictivos, dichos residuos tienden a caer en una distribución geométrica de dos lados , siendo los residuos pequeños más frecuentes que los residuos grandes, y el código de Rice se aproxima mucho al código de Huffman para dicha distribución sin la sobrecarga de tener que transmitir la tabla de Huffman. . Una señal que no coincide con una distribución geométrica es una onda sinusoidal , porque los residuos diferenciales crean una señal sinusoidal cuyos valores no crean una distribución geométrica (los valores de residuos más altos y más bajos tienen una alta frecuencia de ocurrencia similar, solo las medianas positivas y negativas los residuos aparecen con menos frecuencia).

Varios códecs de audio sin pérdidas , como Shorten , ^[4] FLAC , ^[5] Apple Lossless y MPEG-4 ALS , utilizan un código Rice después del paso de predicción lineal (llamado "filtro FIR adaptativo" en Apple Lossless). La codificación Rice también se utiliza en el códec de imágenes sin pérdidas FELICS .

El codificador Golomb-Rice se utiliza en la etapa de codificación de entropía de códecs de imágenes sin pérdidas basados ​​​​en el algoritmo de Rice . Uno de esos experimentos produce el gráfico de relación de compresión que se muestra.

El esquema JPEG-LS utiliza Rice-Golomb para codificar los residuos de predicción.

La versión adaptativa de la codificación Golomb-Rice mencionada anteriormente, el codificador RLGR [2], se utiliza para codificar el contenido de la pantalla en máquinas virtuales en el componente RemoteFX del Protocolo de escritorio remoto de Microsoft.

Ver también

• Codificación delta de Elias
• Código de longitud variable

Referencias

1. Gallager, RG; van Voorhis, DC (1975). "Códigos fuente óptimos para alfabetos enteros distribuidos geométricamente". Transacciones IEEE sobre teoría de la información . 21 (2): 228–230. doi :10.1109/tit.1975.1055357.
2. Merhav, N.; Seroussi, G.; Weinberger, MJ (2000). "Codificación de fuentes con distribuciones geométricas bilaterales y parámetros desconocidos". Transacciones IEEE sobre teoría de la información . 46 (1): 229–236. doi :10.1109/18.817520.
3. Kiely, A. (2004). Selección del parámetro Golomb en la codificación del arroz (informe técnico). Laboratorio de Propulsión a Chorro . 42-159.
4. "hombre acortar". Archivado desde el original el 30 de enero de 2014 . Consultado el 7 de diciembre de 2008 .
5. "FLAC: descripción general del formato". xiph.org .

Lectura adicional

• Golomb, Salomón W. (1966). Codificaciones de longitud de ejecución. Transacciones IEEE sobre teoría de la información, IT--12(3):399--401
• Arroz, Robert F.; Plaunt, R. (1971). "Codificación adaptativa de longitud variable para la compresión eficiente de datos de televisión de naves espaciales". Transacciones IEEE sobre Comunicaciones . 16 (9): 889–897. doi :10.1109/TCOM.1971.1090789.
• Robert F. Rice (1979), "Algunas técnicas prácticas de codificación universal silenciosa", Jet Propulsion Laboratory, Pasadena, California, publicación del JPL 79—22, marzo de 1979.
• Witten, Ian Moffat, Alistair Bell, Timothy. "Gestión de Gigabytes: compresión e indexación de documentos e imágenes". Segunda edición. Editores Morgan Kaufmann, San Francisco CA. 1999ISBN 1-55860-570-3​ 
• David Salomón. "Compresión de datos", ISBN 0-387-95045-1 . 
• HS Malvar, Codificación adaptativa de longitud de ejecución/Golomb-Rice de fuentes gaussianas generalizadas cuantificadas con estadísticas desconocidas, Proc. Conferencia sobre compresión de datos, 2006.
• Codificación de entropía RLGR, especificación abierta Microsoft MS-RDPRFX, códec RemoteFX para protocolo de escritorio remoto.
• S. Büttcher, CLA Clarke y GV Cormack. Recuperación de información: implementación y evaluación de motores de búsqueda Archivado el 5 de octubre de 2020 en Wayback Machine . Prensa del MIT, Cambridge MA, 2010.