Código gamma de Elías
El código gamma de Elias es un código universal para codificar números enteros positivos, desarrollado por Peter Elias . Se usa comúnmente cuando se codifican números enteros cuyo valor máximo no se puede determinar de antemano.
Descripción del algoritmo
Para codificar un número:
- Escríbelo en forma binaria.
- Agregue ceros antes de la representación binaria del número. El número de ceros es uno menos que el número de bits en la representación binaria del número.
Una forma similar de describir este proceso es:
- Seleccione el bit más significativo del entero (la mayor potencia de 2, que incluye el número - 2 N ) y los N bits menos significativos.
- Escriba N en código unario; es decir, N ceros seguidos de un uno.
- Suma los N dígitos binarios menos significativos del número que sigue a este código unario.
Empezar a codificar:
Número |
Sentido |
Codificación |
Probabilidad
estimada |
una |
20 + 0 |
una |
1/2
|
2 |
2 1 + 0 |
0 1 0 |
1/8
|
3 |
2 1 + 1 |
0 1 1 |
1/8
|
cuatro |
2² + 0 |
00 1 00 |
1/32
|
5 |
2² + 1 |
00 1 01 |
1/32
|
6 |
2² + 2 |
00 1 10 |
1/32
|
7 |
2² + 3 |
00 1 11 |
1/32
|
ocho |
2³ + 0 |
000 1000 |
1/128
|
9 |
2³ + 1 |
000 1 001 |
1/128
|
diez |
2³ + 2 |
000 1 010 |
1/128
|
once |
2³ + 3 |
000 1 011 |
1/128
|
12 |
2³ + 4 |
000 1 100 |
1/128
|
13 |
2³ + 5 |
000 1 101 |
1/128
|
catorce |
2³ + 6 |
000 1 110 |
1/128
|
quince |
2³ + 7 |
000 1 111 |
1/128
|
dieciséis |
24 + 0 |
0000 1 0000 |
1/512
|
17 |
2 4 + 1 |
0000 1 0001 |
1/512
|
… |
|
|
|
La distribución de probabilidades asumidas para los códigos se ha agregado para mayor claridad.
Para decodificar el número codificado por el código gamma de Elias, se debe:
- Cuente todos los ceros hasta el primer 1. Sea N el número de estos ceros.
- Considerando el uno, que será el primer bit (el más significativo) del entero, con valor 2 N , cuente los N dígitos restantes del entero.
La codificación gamma se usa en aplicaciones donde el valor más grande no se puede conocer de antemano, o para comprimir datos en los que los valores pequeños ocurren con más frecuencia que los valores grandes.
Generalización
La codificación gamma no es adecuada para codificar valores cero o números negativos. La única forma de codificar cero es sumarle 1 antes de codificar y restar después de decodificar. Otra forma es anteponer cualquier código distinto de cero con 1 y luego codificar cero como un simple 0. La única forma de codificar todos los enteros es establecer una biyección (coincidencia) antes de comenzar a codificar, mapeando los enteros desde (0, 1, −1, 2, −2, 3, −3, …) en (1, 2, 3, 4, 5, 6, 7, …).
Ejemplo de código
// Codificación
void eliasGammaEncode ( char * source , char * dest )
{
IntReader intreader ( fuente );
Bitwriter BitWriter ( destino );
mientras que ( intreader . hasLeft ())
{
int num = interoperador . getint ();
intl = log2 ( numero ) ;
para ( int a = 0 ; a < l ; a ++ )
{ escritor de bits . ponerBit ( falso ); //poner ceros para mostrar cuantos bits siguen }
escritor de bits ponerBit ( verdadero ); //marca ceros finales para ( int a = l -1 ; a >= 0 ; a -- ) //escribe bits como números binarios simples {
si ( número & ( 1 << a ))
escritor de bits ponerBit ( verdadero );
más
escritor de bits ponerBit ( falso );
}
}
intruso _ cerrar ();
escritor de bits cerrar ();
}
// Decodificar
void eliasGammaDecode ( char * source , char * dest )
{
Lector de bits BitReader ( fuente ) ;
Bitwriter BitWriter ( destino );
int numeroBits = 0 ;
while ( lector de bits.hasLeft ( ) )
{
while ( ! lector de bits . getBit () || lector de bits . hasLeft ()) numberBits ++ ; //continuar leyendo hasta encontrar uno... int current = 0 ;
for ( int a = 0 ; a < numberBits ; a ++ ) // leer numberBits bits {
si ( lector de bits.getBit ( ) )
corriente += 1 << a ;
}
//escribirlo como un número de 32 bits
actual = actual | ( 1 << numeroBits ) ; // ¡El último bit no se decodifica! for ( int a = 0 ; a < 32 ; a ++ ) //leer númeroBits bits {
si ( actual & ( 1 << a ))
escritor de bits ponerBit ( verdadero );
más
escritor de bits ponerBit ( falso );
}
}
}
Véase también
Literatura