Elias gammakod
Elias gammakod är en universell kod för att koda positiva heltal, utvecklad av Peter Elias . Det används ofta vid kodning av heltal vars maximala värde inte kan bestämmas i förväg.
Beskrivning av algoritmen
För att koda ett nummer:
- Skriv det i binär form.
- Lägg till nollor före den binära representationen av talet. Antalet nollor är en mindre än antalet bitar i den binära representationen av talet.
Ett liknande sätt att beskriva denna process är:
- Välj den mest signifikanta biten från heltal (den största potensen 2, som talet inkluderar - 2 N ) och de minst signifikanta N bitarna.
- Skriv N i unär kod; det vill säga N nollor följt av en etta.
- Lägg till de N minst signifikanta binära siffrorna i numret efter denna unära kod.
Börja koda:
| siffra |
Menande |
Kodning |
Uppskattad
sannolikhet
|
| ett |
20 + 0 |
ett |
1/2
|
| 2 |
2 1 + 0 |
0 1 0 |
1/8
|
| 3 |
2 1 + 1 |
0 1 1 |
1/8
|
| fyra |
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
|
| åtta |
2³ + 0 |
000 1000 |
1/128
|
| 9 |
2³ + 1 |
000 1 001 |
1/128
|
| tio |
2³ + 2 |
000 1 010 |
1/128
|
| elva |
2³ + 3 |
000 1 011 |
1/128
|
| 12 |
2³ + 4 |
000 1 100 |
1/128
|
| 13 |
2³ + 5 |
000 1 101 |
1/128
|
| fjorton |
2³ + 6 |
000 1 110 |
1/128
|
| femton |
2³ + 7 |
000 1 111 |
1/128
|
| 16 |
24 + 0 |
0000 1 0000 |
1/512
|
| 17 |
2 4 + 1 |
0000 1 0001 |
1/512
|
| … |
|
|
|
För tydlighetens skull har fördelningen av antagna sannolikheter för koderna lagts till.
För att avkoda numret kodat av Elias gammakod bör man:
- Räkna alla nollor upp till den första 1:an. Låt N vara antalet av dessa nollor.
- Med tanke på den, som kommer att vara den första (mest signifikanta) biten i heltal, med värdet 2 N , räkna de återstående N siffrorna i heltalet.
Gammakodning används i applikationer där det största värdet inte kan vara känt i förväg, eller för att komprimera data där små värden förekommer oftare än stora värden.
Generalisering
Gammakodning är inte lämplig för kodning av nollvärden eller negativa tal. Det enda sättet att koda noll är att lägga till 1 till den före kodning och subtrahera efter avkodning. Ett annat sätt är att lägga 1 före vilken kod som helst som inte är noll, och sedan koda noll som en enkel 0. Det enda sättet att koda alla heltal är att ställa in en bijektion (matchning) innan du börjar koda, avbilda heltalen från (0, 1, −1, 2, −2, 3, −3, …) till (1, 2, 3, 4, 5, 6, 7, …).
Kodexempel
// Kodning
void eliasGammaEncode ( char * source , char * dest )
{
IntReader intreader ( källa );
BitWriter bitwriter ( dest );
while ( intreader . hasLeft ())
{
int num = inträdare . getint ();
intl = log2 ( antal ) ;
för ( int a = 0 ; a < l ; a ++ )
{ bitwriter . putBit ( falskt ); //sätt nollor för att visa hur många bitar som ska följas }
bitwriter . putBit ( sant ); //markera slutnollor för ( int a = l -1 ; a >= 0 ; a -- ) //skriv bitar som enkla binära tal {
if ( num & ( 1 << a ))
bitwriter . putBit ( sant );
annan
bitwriter . putBit ( falskt );
}
}
inträdare . stäng ();
bitwriter . stäng ();
}
// Decode
void eliasGammaDecode ( char * source , char * dest )
{
BitReader bitläsare ( källa );
BitWriter bitwriter ( dest );
int numberBits = 0 ;
while ( bitreader.hasLeft ( ) )
{
while ( ! bitläsare . getBit () || bitläsare . hasLeft ()) numberBits ++ ; //fortsätt läsa tills en påträffas... int current = 0 ;
for ( int a = 0 ; a < numberBits ; a ++ ) // read numberBits bits {
if ( bitreader.getBit ( ) )
nuvarande += 1 << a ;
}
//skriv det som ett 32-bitars nummer
ström = aktuell | ( 1 << numberBits ) ; //sista biten är inte avkodad! for ( int a = 0 ; a < 32 ; a ++ ) //läs antalBits bitar {
if ( aktuell & ( 1 << a ))
bitwriter . putBit ( sant );
annan
bitwriter . putBit ( falskt );
}
}
}
Se även
Litteratur