Codificación delta de Elías

El código Elias δ o código Elias delta es un código universal que codifica los números enteros positivos desarrollado por Peter Elias.

Codificación

Para codificar un número X ≥ 1:

1. Vamos N= ⌊log₂ X⌋; ser el poder más alto de 2 en X, así que 2^N ≤ X 2^{N+ 1}.
2. Vamos L= ⌊log₂ N+1⌋ ser el poder más alto de 2 en N+1, so 2^L ≤ N+1^{L+ 1}.
3. Escriba L ceros, seguidos
4. el L+1-bit representación binaria de N+1, seguido
5. todo menos la parte principal (es decir, la última N bits) of X.

Una forma equivalente de expresar el mismo proceso:

1. Separación X en el poder más alto de 2 contiene (2^N) y el resto N dígitos binarios.
2. Código N+1 con Elias gamma codificación.
3. Apéndice el resto N dígitos binarios a esta representación de N+1.

To represent a number x{displaystyle x}, Elias delta (δ) utiliza ⌊ ⌊ log2⁡ ⁡ ()x)⌋ ⌋ +2⌊ ⌊ log2⁡ ⁡ ()⌊ ⌊ log2⁡ ⁡ ()x)⌋ ⌋ +1)⌋ ⌋ +1{displaystyle lfloor log _{2}(x)rfloor +2lfloor log _{2}(lfloor log _{2}(x)rfloor +1)rfloor +1} bits.

El código comienza, utilizando γ γ .{displaystyle gamma} en lugar de γ γ {displaystyle gamma }:

Para decodificar un entero con codificación delta de Elias:

1. Lea y cuente ceros desde el arroyo hasta llegar al primero. Llama a este conteo de ceros L.
2. Considerando el que fue alcanzado para ser el primer dígito de un entero, con un valor de 2^L, leer el resto L dígitos del entero. Llama a este entero N+1, y restar uno para conseguir N.
3. Ponga una en el primer lugar de nuestra salida final, representando el valor 2^N.
4. Lea y apéndice los siguientes N dígitos.

Ejemplo:

001010011
1. 2 ceros principales en 001
2. leer 2 bits más i.e. 00101
3. decodificación N+1 = 00101 = 5
4. obtener N = 5 - 1 = 4 bits restantes para el código completo, es decir, '0011 '
5. número codificado = 24 + 3 = 19

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

Código de ejemplo

Codificación

vacío eliasDeltaIncode()char* fuente, char* dest){} IntReader intreader()fuente); BitWriter bitwriter()dest); mientras ()intreader.hasLeft()) {} int num = intreader.# Int(); int Len = 0; int longitudOfLen = 0; Len = 1 + planta baja()log2()num)); // calcular 1+floor(log2(num)) longitudOfLen = planta baja()log2()Len)); // calcular piso(log2(len)))  para ()int i = longitudOfLen; i ■ 0; --i) bitwriter.Producto Bit()0); para ()int i = longitudOfLen; i >= 0; --i) bitwriter.Producto Bit()Len > i) " 1); para ()int i = Len-2; i >= 0; i--) bitwriter.Producto Bit()num > i) " 1); } bitwriter.cerca(); intreader.cerca();}

Decodificación

vacío eliasDeltaDecode()char* fuente, char* dest){} BitReader bitreader()fuente); IntWriter intwriter()dest); mientras ()bitreader.hasLeft()) {} int num = 1; int Len = 1; int longitudOfLen = 0; mientras ()!bitreader.entrada Bit()) // potencialmente peligroso con archivos malformados. longitudOfLen++; para ()int i = 0; i . longitudOfLen; i++) {} Len " 1; si ()bitreader.entrada Bit()) Len ← 1; } para ()int i = 0; i . Len-1; i++) {} num " 1; si ()bitreader.entrada Bit()) num ← 1; } intwriter.putInt()num); // escriba el valor } bitreader.cerca(); intwriter.cerca();}

Generalizaciones

La codificación delta de Elias no codifica cero ni enteros 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 establecer una biyección, mapeando enteros 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 usando el "ZigZag" codificación de búferes de protocolo (que no debe confundirse con el código Zigzag, ni con la codificación de entropía JPEG Zig-zag).