El código γ de Elias o el código gamma de Elias es un código universal que codifica enteros positivos desarrollado por Peter Elias . [1] : 197, 199 Se utiliza con mayor frecuencia 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:
- Dejar sea la potencia más alta de 2 que contiene, por lo que 2 N ≤ x <2 N +1 .
- Escriba N bits cero, luego
- Agregue la forma binaria de x , un número binario de N + 1 bit.
Una forma equivalente de expresar el mismo proceso:
- Codifique N en unario ; es decir, como N ceros seguidos de uno.
- Añadir el resto de N dígitos binarios de x a esta representación de N .
Para representar un número , Elias gamma (γ) utiliza bits. [1] : 199
El código comienza (la distribución de probabilidad implícita para el código se agrega para mayor claridad):
Número | Binario | codificación γ | Probabilidad implícita |
---|---|---|---|
1 = 2 0 + 0 | 1 | 1 | 1/2 |
2 = 2 1 + 0 | 1 0 | 0 1 0 | 1/8 |
3 = 2 1 + 1 | 1 1 | 0 1 1 | 1/8 |
4 = 2 2 + 0 | 1 00 | 00 1 00 | 1/32 |
5 = 2 2 + 1 | 1 01 | 00 1 01 | 1/32 |
6 = 2 2 + 2 | 1 10 | 00 1 10 | 1/32 |
7 = 2 2 + 3 | 1 11 | 00 1 11 | 1/32 |
8 = 2 3 + 0 | 1 000 | 000 1 000 | 1/128 |
9 = 2 3 + 1 | 1 001 | 000 1 001 | 1/128 |
10 = 2 3 + 2 | 1 010 | 000 1 010 | 1/128 |
11 = 2 3 + 3 | 1 011 | 000 1 011 | 1/128 |
12 = 2 3 + 4 | 1 100 | 000 1 100 | 1/128 |
13 = 2 3 + 5 | 1 101 | 000 1 101 | 1/128 |
14 = 2 3 + 6 | 1 110 | 000 1 110 | 1/128 |
15 = 2 3 + 7 | 1 111 | 000 1 111 | 1/128 |
16 = 2 4 + 0 | 1 0000 | 0000 1 0000 | 1/512 |
17 = 2 4 + 1 | 1 0001 | 0000 1 0001 | 1/512 |
Descodificación
Para decodificar un entero codificado por gamma de Elias:
- Leer y contar 0s de la corriente hasta llegar a la primera llamada 1. Este recuento de ceros N .
- 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.
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 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 números enteros cero o negativos. Una forma de manejar el cero es sumar 1 antes de codificar y luego restar 1 después de decodificar. Otra forma es prefijar cada código distinto de cero con un 1 y luego codificar cero como un solo 0.
Una forma de codificar todos los enteros es configurar una biyección , mapeando enteros (0, −1, 1, −2, 2, −3, 3, ...) a (1, 2, 3, 4, 5, 6 , 7, ...) antes de codificar. En el software, esto se hace más fácilmente asignando entradas no negativas a salidas impares y entradas negativas a salidas pares, por lo que el bit menos significativo se convierte en un bit de signo invertido :
La codificación exponencial de Golomb generaliza el código gamma a números enteros con una distribución de ley de potencia "más plana", al igual que la codificación de 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
Referencias
- ↑ a b Elias, Peter (marzo de 1975). "Conjuntos de palabras de código universales y representaciones de los números enteros". Transacciones IEEE sobre teoría de la información . 21 (2): 194-203. doi : 10.1109 / tit.1975.1055349 .