El código δ de Elias o código delta de Elias es un código universal que codifica los enteros positivos desarrollado por Peter Elias . [1] : 200
Para codificar un número X ≥ 1:
Una forma equivalente de expresar el mismo proceso:
Para representar un número , Elias delta (δ) usa bits. [1] : 200
El código comienza usando en lugar de :
Número | norte | N + 1 | codificación δ | Probabilidad implícita |
---|---|---|---|---|
1 = 2 0 | 0 | 1 | 1 | 1/2 |
2 = 2 1 + 0 | 1 | 2 | 0 1 0 0 | 1/16 |
3 = 2 1 + 1 | 1 | 2 | 0 1 0 1 | 1/16 |
4 = 2 2 + 0 | 2 | 3 | 0 1 1 00 | 1/32 |
5 = 2 2 + 1 | 2 | 3 | 0 1 1 01 | 1/32 |
6 = 2 2 + 2 | 2 | 3 | 0 1 1 10 | 1/32 |
7 = 2 2 + 3 | 2 | 3 | 0 1 1 11 | 1/32 |
8 = 2 3 + 0 | 3 | 4 | 00 1 00 000 | 1/256 |
9 = 2 3 + 1 | 3 | 4 | 00 1 00 001 | 1/256 |
10 = 2 3 + 2 | 3 | 4 | 00 1 00 010 | 1/256 |
11 = 2 3 + 3 | 3 | 4 | 00 1 00 011 | 1/256 |
12 = 2 3 + 4 | 3 | 4 | 00 1 00 100 | 1/256 |
13 = 2 3 + 5 | 3 | 4 | 00 1 00 101 | 1/256 |
14 = 2 3 + 6 | 3 | 4 | 00 1 00 110 | 1/256 |
15 = 2 3 + 7 | 3 | 4 | 00 1 00 111 | 1/256 |
16 = 2 4 + 0 | 4 | 5 | 00 1 01 0000 | 1/512 |
17 = 2 4 + 1 | 4 | 5 | 00 1 01 0001 | 1/512 |
Para decodificar un entero codificado en delta de Elias:
Ejemplo:
001010011 1. 2 ceros a la izquierda en 001 2. leer 2 bits más, es decir, 00101 3. decodificar N + 1 = 00101 = 5 4. obtenga N = 5 - 1 = 4 bits restantes para el código completo, es decir, '0011' 5. número codificado = 2 4 + 3 = 19
Este código se puede generalizar a números enteros cero o negativos de la misma manera que se describe en la codificación gamma de Elias .
void eliasDeltaEncode ( char * fuente , char * dest ) { IntReader intreader ( fuente ); BitWriter bitwriter ( dest ); while ( intreader . hasLeft ()) { int num = intreader . getInt (); int len = 0 ; int lengthOfLen = 0 ; len = 1 + piso ( log2 ( num )); // calcular 1 + piso (log2 (num)) lengthOfLen = piso ( log2 ( len )); // calcular el piso (log2 (len)) para ( int i = lengthOfLen ; i > 0 ; - i ) bitwriter . outputBit ( 0 ); para ( int i = lengthOfLen ; i > = 0 ; - i ) bitwriter . outputBit (( len >> i ) & 1 ); para ( int i = len -2 ; i > = 0 ; i - ) bitwriter . outputBit (( num >> i ) & 1 ); } bitwriter . cerrar (); intreader . cerrar ();}
void eliasDeltaDecode ( char * fuente , char * dest ) { BitReader bitreader ( fuente ); IntWriter intwriter ( dest ); while ( lector de bits . hasLeft ()) { int num = 1 ; int len = 1 ; int lengthOfLen = 0 ; while ( ! bitreader . inputBit ()) // potencialmente peligroso con archivos mal formados. lengthOfLen ++ ; para ( int i = 0 ; i < lengthOfLen ; i ++ ) { len << = 1 ; si ( lector de bits . inputBit ()) len | = 1 ; } para ( int i = 0 ; i < len -1 ; i ++ ) { num << = 1 ; si ( lector de bits . inputBit ()) num | = 1 ; } intérprete . putInt ( num ); // escribe el valor } lector de bits . cerrar (); intérprete . cerrar ();}
La codificación delta de Elias no codifica números enteros cero o negativos. Una forma de codificar todos los enteros no negativos es sumar 1 antes de codificar y luego restar 1 después de decodificar. Una forma de codificar todos los enteros es configurar una biyección , mapeando todos los enteros (0, 1, −1, 2, −2, 3, −3, ...) a enteros estrictamente positivos (1, 2, 3, 4, 5, 6, 7, ...) antes de codificar. Esta biyección se puede realizar utilizando la codificación "ZigZag" de Protocol Buffers (que no debe confundirse con el código Zigzag , ni con la codificación de entropía JPEG Zig-zag ).