Codificación delta de Elias

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:

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

Una forma equivalente de expresar el mismo proceso:

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

Para representar un número${\displaystyle x}$, Elias delta (δ) utiliza${\displaystyle \lfloor \log _{2}(x)\rfloor +2\lfloor \log _{2}(\lfloor \log _{2}(x)\rfloor +1)\rfloor +1}$bits. ^{[ 1 ] : 200} Esto es útil para 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${\displaystyle \log _{2}(\lfloor \log _{2}(x)\rfloor +1)}$parte de la expresión anterior.

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

Para decodificar un número entero codificado con delta de Elias:

1. Lee y cuenta los ceros del flujo hasta que llegues al primero. Llama a este conteo de ceros L.
2. Considerando que el dígito alcanzado es el primer dígito de un entero, con un valor de 2L ^, lee los L dígitos restantes del entero. Llama a este entero N + 1 y réstale uno para obtener N.
3. Coloca un uno en el primer lugar del resultado final, que representa el valor 2 ^N .
4. Lee y añade los siguientes N dígitos.

Ejemplo: 001010011

1. 2 ceros iniciales en 001
2. lee 2 bits más, es decir 00101
3. decodificar N + 1 = 00101 = 5
4. Se obtienen N = 5 − 1 = 4 bits restantes para el código completo, es decir, 0011.
5. Número codificado = 2 ⁴ + 3 = 19

Este código se puede generalizar a enteros cero o negativos de la misma manera que se describe en la codificación gamma de Elias .

La codificación delta de Elias no codifica enteros cero ni negativos. Una forma de codificar todos los enteros no negativos es sumar 1 antes de la codificación y luego restar 1 después de la decodificación. Otra forma de codificar todos los enteros es establecer 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 la codificación. 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 zigzag JPEG ).

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

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