Golomb-koodi
Golomb-koodit ovat koodausmenetelmä, jolla voidaan esittää kokonaislukuja tiiviimmässä muodossa. Menetelmä on nimetty sen keksijän, yhdysvaltalaisen matemaatikon Solomon Golombin mukaan. Golomb-koodauksella voidaan esittää pakattuna sarja kokonaislukuja, joiden arvoalue saattaa olla suuri, mutta jossa nollaa lähempänä olevat arvot ovat merkittävästi yleisempiä kuin siitä kaukana olevat. Golomb-koodit ovat tarkalleen ottaen koodiperhe, jossa jokaisen koodin määrittää kokonaislukuparametri M. Mitä suurempi parametri on, sitä tiiviimmin nollasta kaukaisemmat luvut esitetään nollaa lähempien kustannuksella.
Esitettävä luku jaetaan parametrilla M, ja osamäärä sekä jakojäännös esitetään erikseen. Osamäärän esittämiseen käytetään unaarikoodausta, eli niin monta 1-bittiä kuin arvo on ja lopuksi 0-bitti (tai päinvastoin), kun taas jakojäännös esitetään typistetyssä binäärimuodossa, jossa sen koodaamiseen käytetään joko tai bittiä; jälkimmäinen pätee vain, kun M ei ole kahden potenssi ja jakojäännös on vähintään .
Negatiivisia kokonaislukuja voidaan esittää niin, että etumerkkiä vuorotellaan; sen sijaan että esitettäisiin lukuja 0, 1, 2, 3 ja niin edelleen, esitetäänkin lukuja 0, −1, +1, −2, +2 ja niin edelleen. Jos luvut eivät voi olla negatiivisia, ne voidaan esittää sellaisenaan.
Esimerkiksi, kun esitetään luku 9 (sellaisenaan) parametrilla M = 4, niin jakojäännöksen esittämiseen tarvitaan aina kaksi bittiä; tällöin tulos on 110 01 (sillä 9 : 4 = 2, jakojäännös 1). Sen sijaan jos parametri olisi M = 5, niin luvut 6 ja 9 esitettäisiin (sellaisenaan) muodoissa 10 01 ja 10 111.
Niin sanotut Rice-koodit (nimetty Robert F. Ricen mukaan) tai Golomb–Rice-koodit ovat Golomb-koodien alajoukko, joissa parametri M on aina kahden potenssi. Tällöin kerto- ja jakolaskut voidaan korvata bittisiirroilla, mikä tekee koodien tulkinnasta nopeampaa binääritietokoneilla; jakojäännös esitetään myös aina samalla määrällä bittejä ().
Exp-Golomb-koodi on Golomb-koodien muunnos, jolla voidaan esittää mikä tahansa ei-negatiivinen kokonaisluku bittisarjana, jonka pituutta ei tarvitse erikseen esittää. Koodissa esitetään haluttua kokonaislukua yhtä suurempi luku mahdollisimman lyhyessä binäärimuodossa, ja sen eteen 0-bittiä, missä b vastaa luvun esitysmuodon bittien lukumäärää. Näin esitysmuodot kokonaisluvuille nollasta alkaen alkavat seuraavasti: 1 (= 0), 0 10 (= 1), 0 11 (= 2), 00 100 (= 3), 00 101 (= 4). Exp-Golomb-koodeja käytetään mm. H.264-videokoodauksessa.[1]