Elias gamma koodi
Elias-gammakoodi on Peter Eliasin kehittämä yleinen koodi positiivisten kokonaislukujen koodaamiseen . Sitä käytetään yleisesti koodattaessa kokonaislukuja, joiden enimmäisarvoa ei voida määrittää etukäteen.
Algoritmin kuvaus
Numeron koodaaminen:
- Kirjoita se binäärimuodossa.
- Lisää nollia ennen luvun binääriesitystä. Nollien määrä on yhden vähemmän kuin bittien määrä luvun binääriesituksessa.
Samanlainen tapa kuvata tämä prosessi on:
- Valitse kokonaisluvusta merkitsevin bitti (2:n suurin potenssi, jonka luku sisältää -2 N ) ja vähiten merkitsevä N bittiä.
- Kirjoita N unaarikoodiin; eli N nollaa, jota seuraa yksi.
- Lisää tämän unaarikoodin jälkeisen luvun N vähiten merkitsevää binaarinumeroa.
Aloita koodaus:
| Määrä |
Merkitys |
Koodaus |
Arvioitu
todennäköisyys
|
| yksi |
20 + 0 |
yksi |
1/2
|
| 2 |
2 1 + 0 |
0 1 0 |
1/8
|
| 3 |
2 1 + 1 |
0 1 1 |
1/8
|
| neljä |
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
|
| kahdeksan |
2³ + 0 |
000 1000 |
1/128
|
| 9 |
2³ + 1 |
000 1 001 |
1/128
|
| kymmenen |
2³ + 2 |
000 1010 |
1/128
|
| yksitoista |
2³ + 3 |
000 1 011 |
1/128
|
| 12 |
2³ + 4 |
000 1100 |
1/128
|
| 13 |
2³ + 5 |
000 1 101 |
1/128
|
| neljätoista |
2³ + 6 |
000 1 110 |
1/128
|
| viisitoista |
2³ + 7 |
000 1 111 |
1/128
|
| 16 |
24 + 0 |
0000 10000 |
1/512
|
| 17 |
2 4 + 1 |
0000 10001 |
1/512
|
| … |
|
|
|
Koodien oletettujen todennäköisyyksien jakauma on lisätty selvyyden vuoksi.
Elias-gammakoodin koodaaman numeron purkamiseksi sinun tulee:
- Laske kaikki nollat ensimmäiseen 1:een asti. Olkoon N näiden nollien lukumäärä.
- Ottaen huomioon yhden, joka on kokonaisluvun ensimmäinen (merkittävin) bitti, jonka arvo on 2 N , laske kokonaisluvun loput N numeroa.
Gammakoodausta käytetään sovelluksissa, joissa suurinta arvoa ei voida tietää etukäteen, tai sellaisten tietojen pakkaamiseen, joissa pieniä arvoja esiintyy useammin kuin suuria arvoja.
Yleistys
Gammakoodaus ei sovellu nolla-arvojen tai negatiivisten lukujen koodaamiseen. Ainoa tapa koodata nolla on lisätä siihen 1 ennen koodausta ja vähentää dekoodauksen jälkeen. Toinen tapa on lisätä minkä tahansa nollasta poikkeavan koodin eteen 1 ja koodata sitten nolla yksinkertaiseksi 0:ksi. Ainoa tapa koodata kaikki kokonaisluvut on asettaa bijektio (match) ennen koodauksen aloittamista yhdistämällä kokonaisluvut arvosta (0, 1, −1, 2, −2, 3, −3, …) (1, 2, 3, 4, 5, 6, 7, …).
Esimerkki koodista
// Koodaus
void eliasGammaEncode ( char * lähde , char * dest )
{
IntReader intreader ( lähde );
BitWriter bitwriter ( dest );
while ( intreader . hasLeft ())
{
int num = syöttölaite . getint ();
intl = log2 ( luku ) ;
for ( int a = 0 ; a < l ; a ++ )
{ bitwriter . putBit ( false ); //laita nollia näyttääksesi kuinka monta bittiä seurata }
bitwriter . putBit ( tosi ); //merkitse loppunollat kohteelle ( int a = l -1 ; a >= 0 ; a -- ) //kirjoita bitit yksinkertaisina binäärilukuina {
jos ( numero & ( 1 << a ))
bitwriter . putBit ( tosi );
muu
bitwriter . putBit ( false );
}
}
tunkeutuja . sulje ();
bitwriter . sulje ();
}
// Purkaa
void eliasGammaDecode ( char * lähde , char * dest )
{
BitReader bitreader ( lähde );
BitWriter bitwriter ( dest );
int numberBits = 0 ;
while ( bitreader.hasLeft ( ) )
{
while ( ! bitreader . getBit () || bitreader . hasLeft ()) numberBits ++ ; //jatka lukemista, kunnes sellainen löytyy... int current = 0 ;
for ( int a = 0 ; a < numberBits ; a ++ ) // lue numberBits bits {
if ( bitreader.getBit ( ) )
virta += 1 << a ;
}
//kirjoita se 32-bittisenä numerona
current = current | ( 1 << numerobittiä ) ; //viimeistä bittiä ei pureta! for ( int a = 0 ; a < 32 ; a ++ ) //lue numerobitit {
jos ( nykyinen & ( 1 << a ))
bitwriter . putBit ( tosi );
muu
bitwriter . putBit ( false );
}
}
}
Katso myös
Kirjallisuus