Codificación gamma de Elias

Elías${\displaystyle \gamma }$El código o código gamma de Elias es un código universal que codifica enteros positivos desarrollado por Peter Elias . ^{[ 1 ] : 197, 199} Se utiliza más comúnmente cuando se codifican enteros cuyo límite superior no se puede determinar de antemano.

Para codificar un número x  ≥ 1:

1. Dejar${\displaystyle N=\lfloor \log _{2}x\rfloor }$sea ​​la mayor potencia de 2 que contiene, por lo que 2 ^N ≤ x < 2 ^{N +1} .
2. Escribir${\displaystyle N}$cero bits, entonces
3. Agregue la forma binaria de${\displaystyle x}$, un${\displaystyle (N+1)}$Número binario de -bits.

Una forma equivalente de expresar el mismo proceso:

1. Codificar${\displaystyle N}$en unario ; es decir, como${\displaystyle N}$ceros seguidos de un uno.
2. Añada lo restante${\displaystyle N}$dígitos binarios de${\displaystyle x}$a esta representación de${\displaystyle N}$.

Para representar un número${\displaystyle x}$, Elias gamma (γ) utiliza${\displaystyle 2\lfloor \log _{2}(x)\rfloor +1}$bits. ^{[ 1 ] : 199}

El código comienza (la distribución de probabilidad implícita para el código se agrega para mayor claridad):

Para decodificar un número entero codificado con la función gamma de Elias:

1. Lee y cuenta los 0 del flujo hasta que llegues al primer 1. Llama a este recuento de ceros N.
2. Considerando que el que se alcanzó es el primer dígito del entero, con un valor de 2 ^N , lea los N dígitos restantes del entero.

La codificación gamma se utiliza en aplicaciones donde no se conoce de antemano el valor codificado más grande, o para comprimir datos en los que los valores pequeños son mucho más frecuentes que los valores grandes.

La codificación gamma puede ser más eficiente en términos de tamaño en esas situaciones. Por ejemplo, observe que, en la tabla anterior, si se elige un tamaño fijo de 8 bits para almacenar un número pequeño como el 5, el binario resultante sería 00000101, mientras que la versión de bits variables con codificación gamma sería 00 1 01, necesitando 3 bits menos. Por el contrario, valores mayores, como 254 almacenados en un tamaño fijo de 8 bits, serían , 11111110mientras que la versión de bits variables con codificación gamma sería 0000000 1 1111110, necesitando 7 bits adicionales.

La codificación gamma es un componente fundamental del código delta de Elias .

La codificación gamma no codifica el cero ni los números enteros negativos. Una forma de manejar el cero es sumar 1 antes de codificar y luego restar 1 después de decodificar. Otra forma es anteponer un 1 a cada código distinto de cero y luego codificar el cero como un solo 0.

Una forma de codificar todos los enteros es establecer una biyección , mapeando los enteros (0, −1, 1, −2, 2, −3, 3, ...) a (1, 2, 3, 4, 5, 6, 7, ...) antes de la codificación. En software, esto se hace más fácilmente mapeando las entradas no negativas a las salidas impares y las entradas negativas a las salidas pares, de modo que el bit menos significativo se convierte en un bit de signo invertido : ${\displaystyle {\begin{cases}x\mapsto 2x+1&\mathrm {cuando~} x\geq 0\\x\mapsto -2x&\mathrm {cuando~} x<0\\\end{cases}}}$

La codificación exponencial-Golomb generaliza el código gamma a enteros con una distribución de ley de potencias más plana, al igual que la codificación Golomb generaliza el código unario. Consiste en dividir el número por un divisor positivo, generalmente una potencia de 2, escribir el código gamma para el cociente que sigue a la unidad y escribir el resto en código binario ordinario.

• Codificación delta de Elias (δ) – Codificación de código universal para números enteros positivos 
• Codificación omega de Elias (ω) – Codificación de código universal para números enteros positivos 
• Posit (formato numérico) – Variante de los números de coma flotante en computadoras Páginas que muestran descripciones breves de destinos de redirección 

• Sayood, Khalid (2003). "Códigos gamma de Levenstein y Elias". Manual de compresión sin pérdidas . Elsevier . ISBN 978-0-12-620861-0.