Codificación Golomb-Rice

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

La codificación Golomb es un tipo de codificación de entropía inventada por Solomon W. Golomb que es óptima para alfabetos que siguen una distribución geométrica, lo que significa que los valores bajos son mucho más comunes que los altos. Si aparecen valores negativos en la entrada se usa un esquema de intervalo y superposición (overlap and interleave), donde los valores no negativos se mapean como números pares (x^\prime=2|x|=2x, x\ge0), y los negativos como impares (x^\prime=2|x|-1=-2x-1, x<0).

La codificación de Golomb también se puede usar (como indica el artículo original de Golomb) para codificar un alfabeto de dos símbolos donde uno de ellos es más probable que el otro. En este caso se puede considerar una "codificación sobre la marcha" (Run-length encoding).

La codificación Rice es una caso especial de codificación de Golomb. Fue descrita primero (e inventada) por Robert F. Rice. Es equivalente a la codificación de Golomb cuando el parámetro a ajustar es potencia de dos. Este caso es extremadamente eficiente para usar en ordenadores, dado que la operación de división se convierte en un desplazamiento de bits (bitshift) y el resto de la operación es la máscara de bits (bitmask) de la operación.

La codificación de Rice se usa como codificación de entropía en una gran cantidad de algoritmos de compresión de imágenes y audio sin pérdida.