Golomb coding

Voorbeeld van Golomb-codering voor een bron x met een geometrische verdeling, met parameter p(0) = 0.2, met Golomb-code met M = 3. De 2-bits code 00 wordt 20% van de tijd gebruikt; de 3-bits codes 010, 011 en 100 worden meer dan 38% van de tijd gebruikt; 4 bits of meer zijn nodig in een minderheid van gevallen. Voor deze bron, entropie = 3.610 bits; voor deze code met deze bron, snelheid = 3.639 bits; redundantie dus = 0.030 bits, of efficiëntie = 0.992 bits per bit.

Golomb-codering is een verliesvrije gegevenscompressie methode die gebruik maakt van een familie van gegevenscompressie codes uitgevonden door Solomon W. Golomb in de jaren 1960. Alfabetten die een geometrische verdeling volgen, zullen een Golomb-code als optimale prefix code hebben, wat Golomb-codering zeer geschikt maakt voor situaties waarin het voorkomen van kleine waarden in de invoerstroom aanzienlijk waarschijnlijker is dan grote waarden.

Rice-codering

Rice-codering (uitgevonden door Robert F. Rice) betekent het gebruik van een subset van de familie van Golomb-codes om een eenvoudigere (maar mogelijk suboptimale) prefix code te produceren. Rice gebruikte deze set codes in een adaptief coderings schema; "Rice-codering" kan verwijzen naar dat adaptieve schema of naar het gebruik van die subset van Golomb-codes. Terwijl een Golomb-code een afstembare parameter heeft die elke positieve gehele waarde kan zijn, zijn Rice-codes die waarbij de afstembare parameter een macht van twee is. Dit maakt Rice-codes handig voor gebruik op een computer, aangezien vermenigvuldiging en deling door 2 efficiënter kunnen worden geïmplementeerd in binaire rekenkunde.

Rice werd gemotiveerd om deze eenvoudigere subset voor te stellen vanwege het feit dat geometrische verdelingen vaak in de tijd variëren, niet precies bekend zijn, of beide, zodat het selecteren van de schijnbaar optimale code misschien niet zeer voordelig is.

Rice-codering wordt gebruikt als de entropie-codering fase in een aantal verliesvrije beeldcompressie en audiogegevenscompressie methoden.

Overzicht

Golomb-codering gebruikt een afstembare parameter M om een invoerwaarde x te verdelen in twee delen: q, het resultaat van een deling door M, en r, de restwaarde. De quotient wordt verzonden in unaire codering, gevolgd door de restwaarde in afgeknotte binaire codering. Wanneer M = 1, is Golomb-codering equivalent aan unaire codering.

Golomb-Rice-codes kunnen worden beschouwd als codes die een getal aangeven door de positie van de bin (q), en de offset binnen de bin (r). Het voorbeeldfiguur toont de positie q en offset r voor de codering van een geheel getal x met de Golomb-Rice-parameter M = 3, met bronkansen die een geometrische verdeling volgen met p(0) = 0.2.

Formeel zijn de twee delen gegeven door de volgende expressie, waar x het te coderen niet-negatieve gehele getal is:

$q=\left\lfloor {\frac {x}{M}}\right\rfloor$

en

$r=x-qM$.

Zowel q als r worden gecodeerd met variabele aantallen bits: q door een unaire code, en r door b bits voor Rice-code, of een keuze tussen b en b + 1 bits voor Golomb-code (d.w.z. M is geen macht van 2), met $b=\lfloor \log _{2}(M)\rfloor$. Als $r<2^{b+1}-M$, dan gebruik b bits om r te coderen; anders gebruik b + 1 bits om r te coderen. Duidelijk is $b=\log _{2}(M)$ als M een macht van 2 is en we alle waarden van r met b bits kunnen coderen.

Het gehele getal x dat door Golomb werd behandeld, was de looplengte van een Bernoulli-proces, dat een geometrische verdeling heeft die begint bij 0. De beste keuze van parameter M is een functie van het corresponderende Bernoulli-proces, dat geparametriseerd is door $p=P(x=0)$ de kans op succes in een gegeven Bernoulli-proef. M is ofwel de mediaan van de verdeling of de mediaan ±1. Het kan bepaald worden door deze ongelijkheden:

$(1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M},$

die opgelost worden door

$M=\left\lceil -{\frac {\log(2-p)}{\log(1-p)}}\right\rceil$.

Voor het voorbeeld met p(0) = 0.2:

$M=\left\lceil -{\frac {\log(1.8)}{\log(0.8)}}\right\rceil =\left\lceil 2.634\right\rceil =3$.

De Golomb-code voor deze verdeling is equivalent aan de Huffman code voor dezelfde kansen, als het mogelijk zou zijn om de Huffman-code voor de oneindige set van bronwaarden te berekenen.

Gebruik met getekende gehele getallen

Het schema van Golomb was ontworpen om rijtjes niet-negatieve getallen te coderen. Het is echter eenvoudig uit te breiden om rijtjes te accepteren die negatieve getallen bevatten met behulp van een overlap and interleave schema, waarbij alle waarden op unieke en omkeerbare wijze worden toegewezen aan een positief getal. De rij begint: 0, −1, 1, −2, 2, −3, 3, −4, 4, ... Het n-de negatieve getal (d.w.z. −n) wordt toegewezen aan het n-de oneven getal (2n−1), en het m-de positieve getal wordt toegewezen aan het m-de even getal (2m). Dit kan als volgt wiskundig worden uitgedrukt: een positief getal x wordt toegewezen aan ($x'=2|x|=2x,\ x\geq 0$), en een negatief getal y wordt toegewezen aan ($y'=2|y|-1=-2y-1,\ y<0$). Dergelijke code kan voor eenvoud worden gebruikt, zelfs als suboptimaal. Echt optimale codes voor tweezijdige geometrische verdelingen omvatten meerdere varianten van de Golomb-code, afhankelijk van de verdelingsparameters, inclusief deze.

Eenvoudig algoritme

Hieronder staat de Rice-Golomb-codering, waarbij de restcode gebruik maakt van eenvoudige afgeknotte binaire codering, ook genaamd "Rice-codering" (andere variabel-lengte binaire coderingen, zoals aritmetische of Huffman-coderingen, zijn mogelijk voor de restcodes, als de statistische verdeling van de restcodes niet plat is, en met name wanneer niet alle mogelijke resten na de deling worden gebruikt). In dit algoritme, als de parameter M een macht van 2 is, wordt het equivalent aan de eenvoudigere Rice-codering:

1. Stel de parameter M in op een geheel getal.
2. Voor N, het te coderen getal, vind

rest = r = N modulo M

1. Genereer codewoord

Restcode (in afgeknotte binaire codering)

Laat $b=\lfloor \log _{2}(M)\rfloor$

Als $r\geq 2^{b+1}-M$ codeer het getal $r+2^{b+1}-M$ in binaire representatie met b + 1 bits.

Decoderen:

1. Decodeer de unaire representatie van q (tel het aantal 1 in het begin van de code)
2. Sla de 0-delimiter over
3. Laat $b=\lfloor \log _{2}(M)\rfloor$

Anders interpreteer b + 1 bits als een binaar getal r', de rest wordt gegeven door $r=r'-2^{b+1}+M$

1. Bereken $N=q*M+r$

Voorbeeld

Stel M = 10. Dus $b=\lfloor \log _{2}(10)\rfloor =3$. De afbreekwaarde is $2^{b+1}-M=16-10=6$.

Codering van quotient deel Sjabloon:Mvar uitvoer bits 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 $\vdots$ $\vdots$ N $\underbrace {111\cdots 111} _{N}0$

Codering van rest deel Sjabloon:Mvar offset binair uitvoer bits 0 0 0000 000 1 1 0001 001 2 2 0010 010 3 3 0011 011 4 4 0100 100 5 5 0101 101 6 12 1100 1100 7 13 1101 1101 8 14 1110 1110 9 15 1111 1111

Bijvoorbeeld, met een Rice-Golomb-codering met parameter M = 10, zou het decimale getal 42 eerst gesplitst worden in q = 4 en r = 2, en zou gecodeerd worden als qcode(Sjabloon:Mvar),rcode(Sjabloon:Mvar) = qcode(4),rcode(2) = 11110,010 (je hoeft de scheidende komma in de uitvoerstroom niet te coderen, omdat de 0 aan het einde van de q-code voldoende is om te zeggen wanneer q eindigt en r begint; zowel de qcode als de rcode zijn zelf-begrensd).

Gebruik voor run-length-codering

Let op dat p en 1 – p in deze sectie omgekeerd zijn ten opzichte van het gebruik in eerdere secties.

Gegeven een alfabet van twee symbolen, of een set van twee gebeurtenissen, P en Q, met kansen p en (1 − p), respectievelijk, waar p ≥ 1/2, kan Golomb-codering worden gebruikt om lopen van nul of meer Ps gescheiden door enkele Qs te coderen. In deze toepassing is de beste instelling van de parameter M het dichtstbijzijnde gehele getal bij $-{\frac {1}{\log _{2}p}}$. Wanneer p = 1/2, M = 1, en de Golomb-code komt overeen met unaire (n ≥ 0 Ps gevolgd door een Q wordt gecodeerd als n enen gevolgd door een nul). Als een eenvoudigere code gewenst is, kan men de Golomb-Rice-parameter b (d.w.z. Golomb-parameter M = 2^b) toewijzen aan het gehele getal het dichtstbij $-\log _{2}(-\log _{2}p)$; hoewel niet altijd de beste parameter, is het meestal de beste Rice-parameter en de compressieprestaties zijn zeer dicht bij de optimale Golomb-code. (Rice zelf stelde voor om verschillende codes voor dezelfde gegevens te gebruiken om te bepalen welke het beste was. Een latere JPL onderzoeker stelde verschillende methoden voor om de codeparameter te optimaliseren of te schatten.)

Beschouw het gebruik van een Rice-code met een binair deel met b bits om rijtjes te coderen waar P een kans p heeft. Als $\mathbb {P} [{\text{bit is deel van }}k{\text{-loop}}]$ de kans is dat een bit deel zal uitmaken van een k-bits loop (k−1 Ps en één Q) en $({\text{compressieratio van }}k{\text{-loop}})$ de compressieratio van die loop is, dan is de verwachte compressieratio

<math>\begin{align}

\mathbb{E}[\text{compressieratio}] &= \sum_{k=1}^\infty (\text{compressieratio van }k\text{-loop}) \cdot \mathbb{P}[\text{bit is deel van }k\text{-loop}] \\ &= \sum_{k=1}^\infty \frac{b+1+\lfloor 2^{-b}(k-1) \rfloor}{k} \cdot kp^{k-1} (1-p)^2 \\ &= (1-p)^2 \sum_{j=0}^\infty (b+1+j) \cdot \sum_{i=j2^b+1}^{(j+1)2^b} p^{i-1} \\ &= (1-p)^2 \sum_{j=0}^\infty (b+1+j)

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• Golomb coding in English