Codificación gamma de Elias

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

El código Elias ${\displaystyle \gamma }$ o código gamma 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 cuando se codifican 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 potencia más alta de 2 que contiene, entonces 2 ^N ≤ x < 2 ^{N +1} . ${\displaystyle N=\lfloor \log _{2}x\rfloor }$
2. Escriba cero bits, luego ${\displaystyle N}$
3. Agregue la forma binaria de , un número binario de bits. ${\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. Agregue 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 (la distribución de probabilidad implícita del código se agrega para mayor claridad):

Descodificación

Para decodificar un entero codificado gamma de Elias:

1. Lea y cuente ceros de la secuencia hasta llegar al primer 1. Llame a este recuento de ceros N.
2. Considerando que el que se alcanzó es el primer dígito del número entero, con un valor de 2 ^N , lea los N dígitos restantes del número 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 ^{[ dudosos ]} 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 cero ni 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 cada código distinto de cero con un 1 y luego codificar el cero como un solo 0.

Una forma de codificar todos los números enteros es configurar una biyección , asignando números enteros (0, −1, 1, −2, 2, −3, 3, ...) a (1, 2, 3, 4, 5, 6). , 7, ...) antes de codificar. En 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 exponencial-Golomb generaliza el código gamma a números enteros con una distribución de ley de potencia "más plana", tal como 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.

Ver también

• Codificación Elias delta (d)  : código universal que codifica números enteros positivosPáginas que muestran descripciones de wikidata como alternativa
• Codificación Elias omega (?)  : código universal que codifica números enteros positivos
• Posit (formato de número)  : variante de los números de coma 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 números enteros". Transacciones IEEE sobre teoría de la información . 21 (2): 194-203. doi :10.1109/tit.1975.1055349.

Otras lecturas

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