Código delta de Elías

El código delta de Elias es un código universal para codificar números enteros positivos, desarrollado por Peter Elias.

Codificación

Algoritmo para codificar el número N:

Recuento : el número de bits significativos en la representación binaria del número . $L$ $norte$
Recuento : el número de bits significativos en la representación binaria del número . $METRO$ $L$
Escribe ceros y una unidad. $M-1$
Agregar : los bits menos significativos de la representación binaria del número sin el más significativo ( ). $L_{2}$ $M-1$ $L$ $2^{{M-1}}$
Agregar : los bits menos significativos de la representación binaria del número sin el más significativo ( ). $N_2$ $L-1$ $norte$ $2^{{L-1}}$

De lo contrario, este algoritmo se puede describir de la siguiente manera:

Recuento : el número de bits significativos en la representación binaria del número . $L$ $norte$
Codificar con el código gamma de Elias (γ(L)). $L$
Agrega la representación binaria del número sin el primero. $norte$

Es decir, tanto en el código delta como en el de Elias gamma, un número se codifica como un exponente (la capacidad de un número, el número de bits significativos) y una mantisa (bits realmente significativos), pero en el código gamma el exponente se escribe en forma unaria , y en el código delta se le aplica nuevamente la codificación gamma. $L$ $N_2$

Un ejemplo de codificación del número 10:

La representación binaria de un número tiene 4 bits significativos ( ). $N=10=1010_{2}$ $L=4$
La representación binaria de un número tiene 3 bits significativos ( ). $L=4=100_{2}$ $METRO=3$
Escribimos cero y una unidad → . $M-1=2$ 001
Sumemos los bits del número sin la unidad más alta → . $L$ 00
Sumemos los bits del número sin la unidad más alta → . $norte$ 010
Resultado - 00100010.

Los resultados de codificar los primeros 17 números (a modo de comparación, también se muestra el código gamma):

norte		L		METRO	código delta		Longitud, poco	Probabilidad estimada	código gama		Longitud, poco
norte		L		METRO	γ(L)	$N_2$	Longitud, poco	Probabilidad estimada	$L$	$N_2$	Longitud, poco
una	$1_{2}$	una	$1_{2}$	una	una		una	1/2	una		una
2	$10_{2}$	2	$10_{2}$	2	01 0	0	cuatro	1/16	01	0	3
3	$11_{2}$	2	$10_{2}$	2	01 0	una	cuatro	1/16	01	una	3
cuatro	$100_{2}$	3	$11_{2}$	2	01 1	00	5	1/32	001	00	5
5	$101_{2}$	3	$11_{2}$	2	01 1	01	5	1/32	001	01	5
6	$110_{2}$	3	$11_{2}$	2	01 1	diez	5	1/32	001	diez	5
7	$111_{2}$	3	$11_{2}$	2	01 1	once	5	1/32	001	once	5
ocho	$1000_{2}$	cuatro	$100_{2}$	3	001 00	000	ocho	1/256	0001	000	7
9	$1001_{2}$	cuatro	$100_{2}$	3	001 00	001	ocho	1/256	0001	001	7
diez	$1010_{2}$	cuatro	$100_{2}$	3	001 00	010	ocho	1/256	0001	010	7
once	$1011_{2}$	cuatro	$100_{2}$	3	001 00	011	ocho	1/256	0001	011	7
12	$1100_{2}$	cuatro	$100_{2}$	3	001 00	100	ocho	1/256	0001	100	7
13	$1101_{2}$	cuatro	$100_{2}$	3	001 00	101	ocho	1/256	0001	101	7
catorce	$1110_{2}$	cuatro	$100_{2}$	3	001 00	110	ocho	1/256	0001	110	7
quince	$1111_{2}$	cuatro	$100_{2}$	3	001 00	111	ocho	1/256	0001	111	7
dieciséis	$10000_{2}$	5	$101_{2}$	3	001 01	0000	9	1/512	00001	0000	9
17	$10001_{2}$	5	$101_{2}$	3	001 01	0001	9	1/512	00001	0001	9

Con un procesamiento adicional de los valores originales, el código delta también se puede usar para codificar cero y enteros negativos (ver: Elias Gamma Code#Generalization ).

Decodificación

Algoritmo para decodificar un número del código delta de Elias:

Recuento : el número de ceros en el flujo de entrada hasta el primero. $METRO$
A uno le siguen los bits menos significativos del número , léelos y suma el valor al resultado . Si los bits en el flujo de entrada se escriben de mayor a menor, el primero después de la serie inicial de ceros se puede leer como parte de la representación binaria del número , en cuyo caso no es necesario agregarlo en un paso separado . . $METRO$ $L$ $2^{M}$ $L$ $L$ $2^{M}$
Luego vienen los bits menos significativos del número , léalos y agregue el valor al resultado . $L-1$ $norte$ $2^{{L-1}}$

Un ejemplo de decodificación de la secuencia de bits 001010001 :

Lea del flujo 001 y determine que hay 2 ceros a la izquierda ( ) al principio. $METRO=2$
Lea los siguientes bits de la secuencia → 01 ; da _ $METRO=2$ $L=2^{M}+01_{2}=4+1=5$
Lee los siguientes bits del flujo → 0001 ; da _ $L-1=4$ $N=2^{{L-1}}+0001_{2}=16+1=17$

Eficiencia

Para los números 2, 3, 8…15 el código delta es más largo que el código gamma, para los números 1, 4…7, 16…31 la longitud del código delta es la misma que la longitud del código gamma, para todos los demás números, el código delta es más corto que el código gamma. En consecuencia, el código delta es menos rentable que el código gamma, más desigual es la distribución de probabilidad de los números codificados y más probables son sus valores cuando se acercan a cero.

Véase también

Código Elías Omega

Literatura

D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin. Sección 1. Métodos de compresión sin pérdidas. Capítulo 1. Codificación de fuentes de datos sin memoria. Separación de mantisas y exponentes // Métodos de compresión de datos. Disposición de archivadores, compresión de imagen y video. - M. : Diálogo-MEPhI, 2002. - S. 23-24. — 384 pág. — ISBN 5-86404-170-x .
Conjuntos de palabras clave universales y representaciones de los números enteros // Transacciones IEEE sobre teoría de la información : diario. - 1975. - Marzo ( vol. 21 , n. 2 ). - pág. 194-203 . -doi : 10.1109/ tit.1975.1055349 .