Codificación gamma de Elias

Esquema de codificación universal para números enteros positivos

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

Codificación

Para codificar un número x  ≥ 1:

1. Sea la mayor potencia de 2 que contiene, entonces 2 ^N ≤ x < 2 ^{N +1} . ${\displaystyle N=\lfloor \log _{2}x\rfloor }$
2. Escribe los bits cero y luego ${\displaystyle N}$
3. Agregue la forma binaria de , un número binario de -bit. ${\displaystyle x}$ ${\displaystyle (N+1)}$

Una forma equivalente de expresar el mismo proceso:

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

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

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

Descodificación

Para decodificar un entero codificado con gamma de Elias:

1. Lee y cuenta los 0 del flujo hasta llegar al primer 1. Llama a este conteo de ceros N.
2. Considerando que el alcanzado es el primer dígito del entero, con valor 2 ^N , leer los N dígitos restantes del entero.

Usos

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

La codificación gamma es un componente básico del código delta de Elias .

Generalizaciones

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 números enteros es configurar una biyección , asignando los números enteros (0, −1, 1, −2, 2, −3, 3, ...) a (1, 2, 3, 4, 5, 6, 7, ...) antes de codificarlos. En el software, esto se hace más fácilmente asignando entradas no negativas a salidas impares y entradas negativas a salidas pares, de modo que el bit menos significativo se convierta en un bit de signo invertido :
${\displaystyle {\begin{cases}x\mapsto 2x+1&\mathrm {when~} x\geq 0\\x\mapsto -2x&\mathrm {when~} x<0\\\end{cases}}}$

La codificación Golomb exponencial generaliza el código gamma a números enteros con una distribución de ley de potencia "más plana", de la misma manera que la codificación Golomb generaliza el código unario. Implica dividir el número por un divisor positivo, comúnmente una potencia de 2, escribir el código gamma para uno más que el cociente y escribir el resto en un código binario ordinario.

Véase también

• Codificación delta (d) de Elias  : código universal que codifica números enteros positivosPáginas que muestran descripciones de wikidata como alternativa
• Codificación omega (?) de Elias  : código universal que codifica números enteros positivos
• Posit (formato numérico)  : variante de los números de punto flotante en las computadorasPáginas que muestran descripciones breves de los objetivos de redireccionamiento

Referencias

1. Elias, Peter (marzo de 1975). "Conjuntos de palabras de código universales y representaciones de los números enteros". IEEE Transactions on Information Theory . 21 (2): 194–203. doi :10.1109/tit.1975.1055349.

Lectura adicional

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