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}

Codificación

Para codificar un número X ≥ 1:

Sea N = ⌊log ₂ X ⌋; ser la potencia más alta de 2 en X , por lo que 2 ^N ≤ X <2 ^{N +1} .
Sea L = ⌊log ₂ N + 1⌋ la potencia más alta de 2 en N +1, entonces 2 ^L ≤ N +1 <2 ^{L +1} .
Escriba L ceros, seguido de
la representación binaria de L + 1 bit de N +1, seguida de
todos excepto el bit inicial (es decir, los últimos N bits) de X .

Una forma equivalente de expresar el mismo proceso:

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

Para representar un número , Elias delta (δ) usa bits. ^[1]^{: 200} ${\ Displaystyle x}$ ${\ Displaystyle \ lfloor \ log _ {2} (x) \ rfloor +2 \ lfloor \ log _ {2} (\ lfloor \ log _ {2} (x) \ rfloor +1) \ rfloor +1}$

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

Número	norte	N + 1	codificación δ	Probabilidad implícita
1 = 2 ⁰	0	1	`1`	1/2

2 = 2 ¹ + 0	1	2	`0 1 0 0`	1/16
3 = 2 ¹ + 1	1	2	`0 1 0 1`	1/16

4 = 2 ² + 0	2	3	`0 1 1 00`	1/32
5 = 2 ² + 1	2	3	`0 1 1 01`	1/32
6 = 2 ² + 2	2	3	`0 1 1 10`	1/32
7 = 2 ² + 3	2	3	`0 1 1 11`	1/32

8 = 2 ³ + 0	3	4	`00 1 00 000`	1/256
9 = 2 ³ + 1	3	4	`00 1 00 001`	1/256
10 = 2 ³ + 2	3	4	`00 1 00 010`	1/256
11 = 2 ³ + 3	3	4	`00 1 00 011`	1/256
12 = 2 ³ + 4	3	4	`00 1 00 100`	1/256
13 = 2 ³ + 5	3	4	`00 1 00 101`	1/256
14 = 2 ³ + 6	3	4	`00 1 00 110`	1/256
15 = 2 ³ + 7	3	4	`00 1 00 111`	1/256

16 = 2 ⁴ + 0	4	5	`00 1 01 0000`	1/512
17 = 2 ⁴ + 1	4	5	`00 1 01 0001`	1/512

Para decodificar un entero codificado en delta de Elias:

Lea y cuente los ceros de la secuencia hasta llegar al primero. Llame a este número de ceros de L .
Considerando que el que se alcanzó es el primer dígito de un entero, con un valor de 2 ^L , lea los L restantes del número entero. Llame a este número entero N 1, y restar uno para obtener N .
Poner un uno en el primer lugar de nuestro producto final, que representa el valor 2 ^N .
Lea y agregue los siguientes N dígitos.

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 ⁴ + 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 .

Código de ejemplo

Codificación

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 ();}

Descodificación

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 ();}

Generalizaciones

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 ).

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 .

Otras lecturas

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 . Consultado el 9 de julio de 2018 . (NB. El código δ de Elias coincide con la representación URR de Hamada).

[Elias-1] 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 .

[1]