Codificación Golomb

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

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, 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

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 usó este conjunto de códigos en un esquema de codificación adaptable; "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 de Rice sean convenientes para usar en una computadora, ya que la multiplicación y la división por 2 se pueden implementar de manera más eficiente en la 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 compresión de imágenes sin pérdidas.

Resumen

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 20% del tiempo; los códigos de 3 bits 010, 011, y 100 se utilizan más del 38% del tiempo; 4 bits o más se necesitan en una minoría de 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

Codificación de cordero utiliza un parámetro ajustable $M$ 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 no irritada, seguido por el resto en codificación binaria truncada. Cuando $M=1$ , Coding Golomb es equivalente a codificación no irritada.

Los códigos Golomb–Rice se pueden considerar como códigos que indican un número por la posición del bin ( $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 de enteros $x$ utilizando el parámetro Golomb–Rice $M = 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 entero no negativo que se codifica:

{displaystyle q=leftlfloor {frac {x}{M}}rightrfloor }

{displaystyle r=x-qM}

Esta imagen muestra la redundancia, en pedazos, del código Golomb, cuando

M

es elegido óptimamente, para

1 - p (0) \geq 0,45

Ambos $q$ y $r$ se codificará usando números variables de bits: $q$ por un código siniestro, y $r$ por $b$ bits for Rice code, or a choice between $b$ y $b + 1$ bits for Golomb code (i.e. $M$ no es un poder de 2), con ${displaystyle b=lfloor log _{2}(M)rfloor }$ . Si $<math alttext="{displaystyle rr.2b+1− − M{displaystyle r made2^{b+1}-M}<img alt="{displaystyle r$ , entonces uso $b$ bits to encode $r$ ; de lo contrario, uso $b$ +1 bits para codificar $r$ . Claramente, $b=log _{2}(M)$ si $M$ es un poder de 2 y podemos codificar todos los valores de $r$ con $b$ bits.

El entero $x$ tratado por Golomb fue la longitud de ejecución de un proceso de Bernoulli, que tiene una distribución geométrica a partir de 0. La mejor elección del parámetro $M$ es una función del proceso correspondiente de Bernoulli, que es parametizada por ${displaystyle p=P(x=0)}$ la probabilidad de éxito en un juicio dado de Bernoulli. $M$ es la mediana de la distribución o la mediana ±1. Estas desigualdades pueden determinarse:

<math alttext="{displaystyle (1-p)^{M}+(1-p)^{M+1}leq 1()1− − p)M+()1− − p)M+1≤ ≤ 1.()1− − p)M− − 1+()1− − p)M,{displaystyle (1-p)^{M}+(1-p)^{M+1}leq 1 done(1-p)^{M-1}+(1-p)^{M}}<img alt="{displaystyle (1-p)^{M}+(1-p)^{M+1}leq 1

que se resuelven con

{displaystyle M=leftlceil -{frac {log(2-p)}{log(1-p)}}rightrceil }

Para el ejemplo con $p (0) = 0.2$ :

{displaystyle M=leftlceil -{frac {log(1.8)}{log(0.8)}}rightrceil =leftlceil 2.634rightrceil =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 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 solapamiento e interleave esquema, en el que todos los valores son reasignados a algún número positivo de una manera única y reversible. La secuencia comienza: 0, 1, −2, 2, −3, 3, −4, 4,... El n- el valor negativo (es decir, $-n$ ) es mapeado a n^T número extraño $2n-1$ ), y el m^T valor positivo se asigna al m- incluso número ( $2m$ ). Esto puede expresarse matemáticamente como sigue: un valor positivo $x$ es mapeado a ( ${displaystyle x'=2|x|=2x, xgeq 0}$ ), y un valor negativo $Sí.$ es mapeado a ( $<math alttext="{displaystyle y'=2|y|-1=-2y-1, ySí..=2SilencioSí.Silencio- - 1=- - 2Sí.- - 1,Sí..0{displaystyle y'=2 vidas inquietos. <img alt="{displaystyle y'=2|y|-1=-2y-1, y$ ). Tal código puede ser utilizado para la simplicidad, incluso si suboptimal. Los códigos realmente óptimos para las distribuciones geométricas de dos caras incluyen múltiples variantes del código Golomb, dependiendo de los parámetros de distribución, incluyendo éste.

Algoritmo simple

A continuación se muestra la codificación Rice-Golomb, donde el resto del código utiliza una codificación binaria truncada simple, también denominada "codificación Rice" (Otras codificaciones binarias de longitud variable, como la aritmética o las codificaciones de Huffman, son posibles para los códigos restantes, si la distribución estadística de los códigos restantes no es plana, y en particular cuando no se utilizan todos los posibles residuos 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:

Arregla el parámetro M a un valor entero.
Para N, el número a ser codificado, encontrar
1. quotient = q = pisoN/M)
2. resto = r = N modulo M
Generar palabra clave
1. El formato de código: ■Código de coojo indicativoCódigo de propiedad, donde
2. Código colateral (en codificación no deseada)
  1. Escribe un q- cuerda de longitud de 1 bits (alternativamente, de 0 bits)
  2. Escribe un poco (respectivamente, un poco)
3. Código restante (en codificación binaria truncada)
  1. Vamos b=⌊ ⌊ log2⁡ ⁡ ()M)⌋ ⌋ {displaystyle b=lfloor log _{2}(M)rfloor } ${displaystyle b=lfloor log _{2}(M)rfloor }$
    1. Si $<math alttext="{displaystyle rr.2b+1− − M{displaystyle r made2^{b+1}-M}<img alt="{displaystyle r$ código r en representación binaria b bits.
    2. Si ${displaystyle rgeq 2^{b+1}-M}$ código del número ${displaystyle r+2^{b+1}-M}$ en representación binaria b + 1 bits.

Decodificación:

Decodificar la representación no deseada de q (contar el número 1 en el principio del código)
Skip the 0 delimiter
Vamos b=⌊ ⌊ log2⁡ ⁡ ()M)⌋ ⌋ {displaystyle b=lfloor log _{2}(M)rfloor } ${displaystyle b=lfloor log _{2}(M)rfloor }$
1. Interpretación siguiente b bits como un número binario r '. Si $<math alttext="{displaystyle r'r..2b+1− − M{displaystyle r'ecto2^{b+1}-M}<img alt="{displaystyle r'$ y luego el recordatorio ${displaystyle r=r'}$
2. De lo contrario, interpretar b + 1 bits como un número binario r ', el recordatorio se da por ${displaystyle r=r'-2^{b+1}+M}$
Computación ${displaystyle N=q*M+r}$

Ejemplo

Set $M = 10$ . Así ${displaystyle b=lfloor log _{2}(10)rfloor =3}$ . El corte es ${displaystyle 2^{b+1}-M=16-10=6}$ .

Incoding of quotient part
$q$	bits de salida
0	0
1	10
2	110
3	1110
4	11110
5	111110
6	1111110
$vdots$	$vdots$
N	$underbrace {111cdots 111} _{N}0$

Incoding of remainder part
$r$	offset	binario	bits de salida
0	0	0000	000
1	1	0001	001
2	2	0010	010
3	3	0011	011
4	4	0100	100
5	5	0101	101
6	12	1100	1100
7	13	1101	1101
8	14	1110	1110
9	15	1111	1111

Por ejemplo, con una codificación Rice–Golomb usando 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 necesita codificar la coma de separación en el flujo de salida, porque el 0 al final del $q$ código es suficiente para decir cuando $q$ termina y $r$ comienza; tanto el qcode como el rcode están autodelimitados).

Utilizar para la codificación de longitud de ejecución

Note que $p$ y $1 - p$ se invierten 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 \geq 1/2$ , la codificación Golomb se puede utilizar para codificar las carreras de cero o más P′s separados por un solo Q′s. En esta aplicación, el mejor ajuste del parámetro M es el entero más cercano a ${displaystyle -{frac {1}{log _{2}p}}}$ . Cuando p = 1/2, M = 1, y el código Golomb corresponde a unary ( $n \geq 0$ P′ s seguido por un Q está codificado como n los seguidos por 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 ${displaystyle M=2^{b}}$ ) al entero más cercano a ${displaystyle -log _{2}(-log _{2}p)}$ ; aunque no siempre el mejor parámetro, es generalmente el mejor parámetro Rice y su rendimiento de compresión está bastante cerca del código Golomb óptimo. (Rice mismo propuso utilizar varios códigos para los mismos datos para averiguar cuál era el mejor. A later JPL researcher proposed various methods of optimizing or estimating the code parameter.)

Considerar el uso de un código Rice con una porción binaria $b$ bits to run-length codifica secuencias donde P tiene una probabilidad $p$ . Si ${displaystyle mathbb {P} [{text{bit is part of }}k{text{-run}}]}$ es la probabilidad de que un poco sea parte de $k$ -bit run $k-1$ Ps y uno Q) y ${displaystyle ({text{compression ratio of }}k{text{-run}})}$ es la relación de compresión de esa carrera, entonces la relación de compresión esperada es

{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 ${displaystyle 1-mathbb {E} [{text{compression ratio}}]}$ , la proporción comprimida. Para ${displaystyle papprox 1}$ , el enfoque de codificación de longitud de carrera resulta en ratios de compresión cercanas a la entropía. Por ejemplo, usando el código Rice ${displaystyle b=6}$ para ${displaystyle p=0.99}$ rendimientos 91,89% compresión, mientras que el límite de entropía es 91,92%.

Codificación adaptativa 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 usa un enfoque de dos pasos: primero, el bloque de datos se escanea para estimar una función de densidad de probabilidad (PDF) para los datos. A continuación, se determina el parámetro Golomb-Rice 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 discutidas a continuación.

Un enfoque alternativo para codificar eficientemente datos enteros cuyo PDF no se conoce o varía, es usar un codificador adaptativo hacia atrás. El código Golomb-Rice (RLGR) de longitud de ejecución logra eso usando un algoritmo muy simple que ajusta el parámetro Golomb-Rice hacia arriba o hacia abajo, según el ú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 tales aplicaciones.

Aplicaciones

Golomb-coded ratios de compresión de experimentos de algoritmo de arroz

Numerosos códecs de señal 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 tal 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 similar de ocurrencias, solo la mediana positiva y negativa los residuos ocurren con menos frecuencia).

Varios códecs de audio sin pérdida, como Shorten, FLAC, Apple Lossless y MPEG-4 ALS, usan 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érdidas FELICS.

El codificador Golomb-Rice se utiliza en la etapa de codificación de entropía de los códecs de imagen 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 Golomb-Rice (RLGR) de longitud de ejecución de la codificación Golomb-Rice, mencionada anteriormente, se usa para codificar contenido de pantalla en máquinas virtuales en el componente RemoteFX del protocolo de escritorio remoto de Microsoft.

Contenido relacionado

Más resultados...