Codificación delta de Elias

El código δ de Elias o código delta de Elias es un código universal que codifica los números enteros positivos desarrollado por Peter Elias . ^{[1] : 200}

Codificación

Para codificar un número X  ≥ 1:

1. Sea N  = ⌊log ₂ X ⌋; la mayor potencia de 2 en X , entonces 2 ^N ≤ X < 2 ^{N +1} .
2. Sea L  = ⌊log ₂ N +1⌋ la mayor potencia de 2 en N +1, entonces 2 ^L ≤ N +1 < 2 ^{L +1} .
3. Escribe L ceros, seguidos de
4. la representación binaria de L +1 bit de N +1, seguida de
5. todos excepto el bit inicial (es decir, los últimos N bits) de X.

Una forma equivalente de expresar el mismo proceso:

1. Separa X en la potencia más alta de 2 que contiene (2 ^N ) y los N dígitos binarios restantes.
2. Codifique N +1 con codificación gamma Elias .
3. Agregue los N dígitos binarios restantes a esta representación de N +1.

Para representar un número , la delta de Elias (δ) utiliza bits. ^{[1] : 200} Esto es útil para números enteros muy grandes, donde los bits de la representación codificada general terminan siendo menores [que los que se podrían obtener usando la codificación gamma de Elias ] debido a la parte de la expresión anterior. ${\displaystyle x}$ ${\displaystyle \lfloor \log _{2}(x)\rfloor +2\lfloor \log _{2}(\lfloor \log _{2}(x)\rfloor +1)\rfloor +1}$ ${\displaystyle \log _{2}(\lfloor \log _{2}(x)\rfloor +1)}$

El código comienza usando en lugar de : ${\displaystyle \gamma '}$ ${\displaystyle \gamma }$

Para decodificar un entero codificado con delta de Elias:

1. Lee y cuenta los ceros de la secuencia hasta llegar al primero. Llama a este recuento de ceros L.
2. Considerando que el uno que se alcanzó es el primer dígito de un entero, con un valor de 2 ^L , se leen los L dígitos restantes del entero. Se llama a este entero N +1 y se le resta uno para obtener N .
3. Coloque un uno en el primer lugar de nuestra salida final, representando el valor 2 ^N .
4. Lea y agregue los siguientes N dígitos.

Ejemplo:

0010100111. 2 ceros a la izquierda en 0012. lee 2 bits más, es decir 001013. decodificar N+1 = 00101 = 54. 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 cero o a números enteros negativos de las mismas formas descritas en la codificación gamma de Elias .

Código de ejemplo

Codificación

void eliasDeltaEncode ( char * fuente , char * destino ) { IntReader intreader ( fuente ); BitWriter bitwriter ( destino ); mientras ( intreader . hasLeft ()) { int num = intreader . obtenerInt (); longitud int = 0 ; int longitudDeLen = 0 ;                        len = 1 + piso ( log2 ( num ) ); // calcular 1+piso(log2(num)) lengthOfLen = piso ( log2 ( len )); // calcular 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.close ( ) ; intreader.close ( ) ; }                                                   

Descodificación

void eliasDeltaDecode ( char * fuente , char * destino ) { BitReader bitreader ( fuente ) ; IntWriter intwriter ( destino ); while ( bitreader.hasLeft ( ) ) { int num = 1 ; int len ​​= 1 ; int lengthOfLen = 0 ; while ( ! bitreader.inputBit ()) // potencialmente peligroso con archivos malformados. lengthOfLen ++ ; for ( int i = 0 ; i < lengthOfLen ; i ++ ) { len << = 1 ; if ( bitreader.inputBit ()) len | = 1 ; } for ( int i = 0 ; i < len -1 ; i ++ ) { num << = 1 ; if ( bitreader.inputBit ( ) ) num | = 1 ; } intwriter.putInt ( num ) ; // escribe el valor } bitreader . close (); intwriter . close (); }                                                                      

Generalizaciones

La codificación delta de Elias no codifica números enteros cero o negativos. Una forma de codificar todos los números enteros no negativos es sumar 1 antes de codificar y luego restar 1 después de decodificar. Una forma de codificar todos los números enteros es configurar una biyección , asignando todos los números enteros (0, 1, −1, 2, −2, 3, −3, ...) a números 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 ).

Véase también

• Codificación gamma (γ) de Elias
• Codificación omega (ω) de Elias
• Código de Golomb-Rice

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

• Hamada, Hozumi (junio de 1983). "URR: Representación universal de números reales". Computación de nueva generación . 1 (2): 205–209. doi :10.1007/BF03037427. ISSN  0288-3635. S2CID  12806462 . Consultado el 9 de julio de 2018 .(NB. El código δ de Elias coincide con la representación URR de Hamada.)