> golomb | optimal | komprimering <
// Golomb-kodning - Optimal heltalskomprimering med flexibel divisor
>> funktioner
Flexibel divisor
Välj valfritt M-värde för maximal komprimeringseffektivitet.
Trunkerad binär
Använder minsta möjliga antal bitar för restkodning.
Allmänt bruk
Fungerar för alla fördelningar av icke-negativa heltal.
>> teknisk information
Hur Golomb-kodning fungerar
Golomb-kodning dividerar varje heltal n med en divisor M för att få kvot q och rest r. Kvoten kodas unärt och resten med trunkerad binärkodning, vilket använder minsta möjliga antal bitar för de M möjliga värdena. Detta ger en optimal kod för geometriska fördelningar med parameter p = 1/M.
Exempel på Golomb-kodning (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 bitar för r<3) 1 → q=0, r=1 → 0|01 → 001 (2 bitar för r<3) 2 → q=0, r=2 → 0|10 → 010 (2 bitar för r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 bitar för r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 bitar för 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 Trunkerad binär: r<3 använder 2 bitar, r≥3 använder 3 bitar
Varför använda Golomb-kodning
- Optimal för geometriska fördelningar
- Flexibel M-parameter
- Minimalt bitantal
- Enkel implementation
- Bevisad optimalitet
>> vanliga frågor
Vad är Golomb-kodning?
Golomb-kodning är en optimal, prefixfri kod med variabel längd för geometriska fördelningar. Heltal delas med en justerbar parameter M, kvoten kodas unärt och resten med trunkerad binärkodning, vilket ger optimal komprimering för data som följer P(n) = (1-p)^n × p.
Hur väljer jag M-parametern?
Det optimala M beror på den geometriska parametern p för dina data. För data med medelvärde μ gäller ungefär M ≈ μ + 1. För exponentiellt avtagande sannolikheter med parameter p är det optimala M = ⌈-1/log₂(1-p)⌉. Använd analysfunktionen för att hitta det bästa M för dina data.
Vad är trunkerad binärkodning?
Trunkerad binärkodning minimerar antalet bitar när ett av M möjliga värden kodas. Om M är en tvåpotens används vanlig binärkodning. Annars använder vissa värden ⌊log₂M⌋ bitar och andra ⌈log₂M⌉ bitar, vilket ger entydig avkodning med minimal medellängd.
Var används Golomb-kodning?
Golomb-kodning används i JPEG-LS-bildkomprimering, H.264-videokodning (som Exp-Golomb) och i förlustfria ljudformat. Den är idealisk för run-length-kodning, restkodning efter prediktion och all data med geometriska eller exponentiella fördelningar.