Codificación Golomb

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

La codificación Golomb es un método de compresión de datos sin pérdida 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 la de valores grandes.

Codificación de 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 adaptativa ; la "codificación Rice" puede referirse tanto a ese esquema adaptativo como 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 la 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 datos de audio y de compresión de imágenes sin pérdida .

Descripción general

Ejemplo de codificación Golomb para una fuente x con distribución geométrica, con parámetro p (0) = 0,2 , utilizando código Golomb con M = 3. El código de 2 bits 00 se utiliza el 20 % del tiempo; los códigos de 3 bits 010, 011 y 100 se utilizan más del 38 % del tiempo; se necesitan 4 bits o más en una minoría de los casos. Para esta fuente, entropía = 3,610 bits; para este código con esta fuente, tasa = 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 de Golomb-Rice pueden considerarse como códigos que indican un número por la posición del bin ( q ) y el desplazamiento dentro del bin ( r ). La figura de ejemplo muestra la posición q y el desplazamiento r para la codificación del entero x utilizando el parámetro de Golomb-Rice M = 3 , con probabilidades de origen que siguen una distribución geométrica con p (0) = 0,2 .

Formalmente, las dos partes se dan mediante la siguiente expresión, donde x es el entero no negativo que se está codificando:

${\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 M se elige de forma ó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, use 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 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 opción de parámetro M es una función del proceso de Bernoulli correspondiente, que está parametrizado por la probabilidad de éxito en un ensayo de Bernoulli dado . M es la mediana de la distribución o la mediana ±1. Puede determinarse mediante 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 mediante

${\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 de Golomb para esta distribución es equivalente al código de Huffman para las mismas probabilidades, si fuera posible calcular el código de Huffman para el conjunto infinito de valores fuente.

Usar con números enteros con signo

El esquema de Golomb fue diseñado para codificar secuencias de números no negativos. Sin embargo, se extiende fácilmente para aceptar secuencias que contienen números negativos usando un esquema de superposición e intercalación , 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 puede expresarse matemáticamente de la siguiente manera: un valor positivo x se asigna a ( ), y un valor negativo y se asigna a ( ). Tal código puede usarse para simplificar, incluso si no es óptimo. Los códigos verdaderamente óptimos para distribuciones geométricas bilaterales incluyen múltiples variantes del código de 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 de residuo utiliza una codificación binaria truncada simple, también llamada "codificación Rice" (otras codificaciones binarias de longitud variable, como las codificaciones aritméticas o de Huffman, son posibles para los códigos de residuo, si la distribución estadística de los códigos de residuo no es plana, y en particular cuando no se utilizan todos los residuos 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 = suelo( 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 de resto>, donde
   2. Código de cociente (en codificación unaria )
      1. Escribe una cadena de longitud q de 1 bit (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 el código r está en representación binaria utilizando b bits. ${\displaystyle r<2^{b+1}-M}$
         2. Si codifica el número en representación binaria utilizando b + 1 bits. ${\displaystyle r\geq 2^{b+1}-M}$ ${\displaystyle r+2^{b+1}-M}$

Descodificación:

1. Decodificar la representación unaria de q (contar el número 1 al comienzo del código)
2. Omitir 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 cumple, entonces el resto ${\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. Por lo tanto , el valor de corte 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 que utiliza el parámetro M = 10 , el número decimal 42 primero se dividiría 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 separadora en el flujo de salida, porque el 0 al final del código q es suficiente para indicar cuándo termina q y comienza r ; tanto el qcode como el rcode están autodelimitados).

Se utiliza 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 Golomb se puede utilizar para codificar ejecuciones de cero o más P ′ separadas por Q ′ individuales. En esta aplicación, la mejor configuración del parámetro M es el entero más cercano a . Cuando p = 1/2, M = 1, y el código Golomb corresponde a unario ( n ≥ 0 P ′ seguidos 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 Golomb–Rice b (es decir, parámetro Golomb ) al entero más cercano a ; aunque no siempre es el mejor parámetro, suele ser el mejor parámetro Rice y su rendimiento de compresión es bastante cercano al código Golomb óptimo. (El propio Rice propuso utilizar varios códigos para los mismos datos para determinar cuál era el 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 el uso de un código Rice con una porción binaria que tiene b bits para codificar secuencias de longitud de ejecución donde P tiene una probabilidad p . Si es la probabilidad de que un bit sea parte de una ejecución de k bits ( P s y un 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 se expresa a menudo en términos de , la proporción comprimida. Para , el enfoque de codificación por longitud de ejecución da como resultado relaciones de compresión cercanas a la entropía . Por ejemplo, el uso del código Rice para produce ${\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 de Golomb-Rice de longitud de ejecución adaptativa

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, se determina el parámetro Golomb-Rice a partir de esa PDF estimada. Una variación más simple de ese enfoque es suponer 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 Golomb-Rice óptimo. Ese es el enfoque utilizado en la mayoría de las aplicaciones que se analizan a continuación.

Un enfoque alternativo para codificar de manera eficiente datos enteros cuya PDF no se conoce o varía es utilizar un codificador adaptativo hacia atrás. El codificador RLGR [1] logra esto utilizando 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 una PDF gaussiana generalizada, que cubre una amplia gama de estadísticas observadas 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 tales aplicaciones.

Aplicaciones

Experimento de ratios de compresión del algoritmo Rice codificado por Golomb

Numerosos códecs de señales utilizan un código Rice para predecir residuos. En algoritmos predictivos, dichos residuos tienden a caer en una distribución geométrica bilateral , en la que los residuos pequeños son más frecuentes que los residuos grandes, y el código Rice se aproxima mucho al código Huffman para dicha distribución sin la sobrecarga de tener que transmitir la tabla 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 residuo más altos y más bajos tienen una alta frecuencia de ocurrencias similar, solo los residuos positivos y negativos medianos ocurren con menor frecuencia).

Varios códecs de audio sin pérdida , 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 imagen sin pérdida FELICS .

El codificador Golomb-Rice se utiliza en la etapa de codificación de entropía de los códecs de imágenes sin pérdida basados ​​en el algoritmo Rice . Uno de estos 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.

Véase 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". IEEE Transactions on Information Theory . 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". IEEE Transactions on Information Theory . 46 (1): 229–236. doi :10.1109/18.817520.
3. Kiely, A. (2004). Selección del parámetro Golomb en la codificación Rice (informe técnico). Laboratorio de Propulsión a Chorro . 42-159.
4. "el hombre se acorta". 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, Solomon W. (1966). Codificaciones de longitud de ejecución. IEEE Transactions on Information Theory, IT--12(3):399--401
• Rice, Robert F.; Plaunt, R. (1971). "Codificación de longitud variable adaptativa para la compresión eficiente de datos de televisión de naves espaciales". IEEE Transactions on Communications . 16 (9): 889–897. doi :10.1109/TCOM.1971.1090789.
• Robert F. Rice (1979), "Algunas técnicas prácticas de codificación universal sin ruido", Laboratorio de Propulsión a Chorro, Pasadena, California, JPL Publication 79—22, marzo de 1979.
• Witten, Ian Moffat, Alistair Bell, Timothy. "Administración de gigabytes: compresión e indexación de documentos e imágenes". Segunda edición. Morgan Kaufmann Publishers, San Francisco, CA. 1999 ISBN 1-55860-570-3 
• David Salomon. "Compresión de datos", ISBN 0-387-95045-1 . 
• HS Malvar, Codificación Golomb-Rice/de longitud de ejecución adaptativa 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 el 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 . MIT Press, Cambridge MA, 2010.