Elias gamma coding

Elias γ-code of Elias gamma code is een universele code voor het coderen van positieve gehele getallen ontwikkeld door Peter Elias.^[1] Het wordt meestal gebruikt voor het coderen van gehele getallen wiens bovengrens niet vooraf bepaald kan worden.

Codering[bewerken]

Om een getal x ≥ 1 te coderen:

Laat $N=\lfloor \log _{2}x\rfloor$ de hoogste macht van 2 zijn die het bevat, dus 2^N ≤ x < 2^N+1.
Schrijf $N$ nullen, dan
Voeg de binaire vorm van $x$ toe, een $(N+1)$ -bits binaire getal.

Een equivalente manier om hetzelfde proces uit te drukken:

Codeer $N$ in [unary|Unary numeral system]; dat wil zeggen, als $N$ nullen gevolgd door een één.
Voeg de resterende $N$ binaire cijfers van $x$ toe aan deze representatie van $N$ .

Om een getal $x$ weer te geven, gebruikt Elias gamma (γ) $2\lfloor \log _{2}(x)\rfloor +1$ bits.^[1]

De code begint (de impliciete kansverdeling van de code is toegevoegd voor duidelijkheid):

Getal	Binaire	γ-codering	Impliciete kans
1 = 2⁰ + 0	`1`	`1`	1/2

2 = 2¹ + 0	`1 0`	`0 1 0`	1/8
3 = 2¹ + 1	`1 1`	`0 1 1`	1/8

4 = 2² + 0	`1 00`	`00 1 00`	1/32
5 = 2² + 1	`1 01`	`00 1 01`	1/32
6 = 2² + 2	`1 10`	`00 1 10`	1/32
7 = 2² + 3	`1 11`	`00 1 11`	1/32

8 = 2³ + 0	`1 000`	`000 1 000`	1/128
9 = 2³ + 1	`1 001`	`000 1 001`	1/128
10 = 2³ + 2	`1 010`	`000 1 010`	1/128
11 = 2³ + 3	`1 011`	`000 1 011`	1/128
12 = 2³ + 4	`1 100`	`000 1 100`	1/128
13 = 2³ + 5	`1 101`	`000 1 101`	1/128
14 = 2³ + 6	`1 110`	`000 1 110`	1/128
15 = 2³ + 7	`1 111`	`000 1 111`	1/128

16 = 2⁴ + 0	`1 0000`	`0000 1 0000`	1/512
17 = 2⁴ + 1	`1 0001`	`0000 1 0001`	1/512

Decodering[bewerken]

Om een Elias gamma-gecodeerd geheel getal te decoderen:

Lees en tel de nullen van de stream tot je de eerste 1 bereikt. Noem deze telling van nullen N.
Beschouw de één die bereikt is als de eerste cijfer van het gehele getal, met een waarde van 2^N, lees de resterende N cijfers van het gehele getal.

Toepassingen[bewerken]

Gamma codering wordt gebruikt in toepassingen waar de grootste gecodeerde waarde niet vooraf bekend is, of om gegevens te comprimeren in situaties waar kleine waarden veel voorkomen dan grote waarden.

Gamma codering kan in die situaties efficiënter zijn in termen van grootte. Bijvoorbeeld, merk op dat in de bovenstaande tabel, als een vaste grootte van 8 bits wordt gekozen om een klein getal als 5 op te slaan, het resulterende binaire getal 00000101 zou zijn, terwijl de γ-codering met variabele bits 00 1 01 zou zijn, met 3 bits minder nodig. Aan de andere kant, grotere waarden, zoals 254 opgeslagen in een vaste grootte van 8 bits, zou 11111110 zijn, terwijl de γ-codering met variabele bits 0000000 1 1111110 zou zijn, met 7 extra bits nodig.

Gamma codering is een bouwsteen in de Elias delta code.

Algemeen[bewerken]

Gamma codering codeert geen nul of negatieve gehele getallen. Een manier om nul te verwerken is door 1 toe te voegen voor het coderen en vervolgens 1 af te trekken na het decoderen. Een andere manier is om elke niet-nul code vooraf te gaan met een 1 en dan nul te coderen als een enkele 0.

Een manier om alle gehele getallen te coderen is door een bijectie op te zetten, waarbij gehele getallen (0, −1, 1, −2, 2, −3, 3, ...) worden toegewezen aan (1, 2, 3, 4, 5, 6, 7, ...) vóór het coderen. In software wordt dit het gemakkelijkst gedaan door niet-negatieve invoer toe te wijzen aan oneven uitvoer, en negatieve invoer aan even uitvoer, zodat het minst significante bit een geïnverteerd [tekenbit|sign bit] wordt: ${\begin{cases}x\mapsto 2x+1&\mathrm {als~} x\geq 0\\x\mapsto -2x&\mathrm {als~} x<0\\\end{cases}}$

Exponential-Golomb coding generaliseert de gamma code tot gehele getallen met een "vlakkere" machtswetverdeling, net als Golomb coding de unary code generaliseert. Het betekent het delen van het getal door een positieve deler, meestal een macht van 2, het schrijven van de gamma code voor één meer dan de quotiënt, en het uitschrijven van de rest in een gewone binair code.