> golomb | optimale | compressie <
// Golomb-codering - Optimale integercompressie met flexibele deler
>> functies
Flexibele deler
Kies elke M-waarde voor maximale compressie-efficiëntie.
Afgekort binair
Gebruikt het minimale aantal bits voor de restcodering.
Algemeen gebruik
Werkt met elke verdeling van niet-negatieve gehele getallen.
>> technische info
Hoe Golomb-codering werkt
Golomb-codering deelt elk geheel getal n door een deler M om quotiënt q en rest r te verkrijgen. Het quotiënt wordt unair gecodeerd en de rest met afgekorte binaire codering, waarbij zo weinig mogelijk bits worden gebruikt voor de M mogelijke waarden. Dit levert een optimale code op voor geometrische verdelingen met parameter p = 1/M.
Voorbeeld van Golomb-codering (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 bits voor r<3) 1 → q=0, r=1 → 0|01 → 001 (2 bits voor r<3) 2 → q=0, r=2 → 0|10 → 010 (2 bits voor r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 bits voor r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 bits voor r≥3) 5 → q=1, r=0 → 10|00 → 1000 6 → q=1, r=1 → 10|01 → 1001 7 → q=1, r=2 → 10|10 → 1010 Afgekort binair: r<3 gebruikt 2 bits, r≥3 gebruikt 3 bits
Waarom Golomb-codering gebruiken
- Optimaal voor geometrische verdelingen
- Flexibele M-parameter
- Minimaal bitgebruik
- Eenvoudige implementatie
- Bewezen optimaliteit
>> veelgestelde vragen
Wat is Golomb-codering?
Golomb-codering is een optimale, prefixvrije code met variabele lengte voor geometrische verdelingen. Gehele getallen worden gedeeld door een instelbare parameter M, waarbij het quotiënt unair en de rest met afgekorte binaire codering wordt weergegeven, wat optimale compressie oplevert voor data met P(n) = (1-p)^n × p.
Hoe kies ik de M-parameter?
De optimale M-waarde hangt af van de geometrische parameter p van je data. Voor data met gemiddelde μ geldt ongeveer M ≈ μ + 1. Voor exponentieel dalende kansen met parameter p is de optimale waarde M = ⌈-1/log₂(1-p)⌉. Gebruik de analysefunctie om de beste M-waarde voor jouw data te vinden.
Wat is afgekorte binaire codering?
Afgekorte binaire codering minimaliseert het aantal bits bij het coderen van een van de M mogelijke waarden. Als M een macht van 2 is, wordt standaard binair gebruikt. Anders gebruiken sommige waarden ⌊log₂M⌋ bits en andere ⌈log₂M⌉ bits, wat unieke decodering met minimale gemiddelde lengte garandeert.
Waar wordt Golomb-codering gebruikt?
Golomb-codering wordt gebruikt in JPEG-LS-beeldcompressie, H.264-videocodering (als Exp-Golomb) en verliesloze audioformaten. Het is ideaal voor runlengtecodering, restcodering na voorspelling en alle data met geometrische of exponentiële verdelingen.