Golomb koodit

Golomb - koodit ovat entropiakoodien perhe . Golomb-koodi voi tarkoittaa myös yhtä tämän perheen edustajia.

Tarkastellaan lähdettä, joka muodostaa itsenäisesti ei-negatiivisia kokonaislukuja todennäköisyyksillä , jossa on mielivaltainen positiivinen luku, joka ei ylitä 1, eli lähde, jota kuvaa geometrinen jakauma . Jos positiivinen kokonaisluku on sellainen, että $i$ ${\displaystyle P(i)=(1-p)p^{i))$ $s$ $m$

p^{m}={\frac {1}{2))

silloin optimaalinen merkki merkiltä koodi (eli koodi, joka yhdistää jokaisen koodatun merkin tiettyyn koodisanaan) tällaiselle lähteelle on koodi, joka on rakennettu Solomon Golombin ehdottaman menettelyn mukaisesti, jonka mukaan mikä tahansa koodattu numero , jossa on tunnettu koodisana, numeron yksipuolinen merkintä ja koodattu alla kuvatun menettelyn mukaisesti, jaon loppuosa : $n$ $m$ $q=\left[{\frac {n}{m}}\right]$ $r$ ${\frac {n}{m))$

Jos on 2:n potenssi, niin jäännöskoodi on binääriesitys luvusta , joka on sijoitettu bitteinä. $m$ $r$ $\log_2(m)$
Jos ei ole 2:n potenssi, luku lasketaan . Edelleen: $m$ $b=\lceil \log _{2}(m)\rceil$

Jos , jäännöskoodi on binääriesitys luvusta , joka on sijoitettu bitteinä,

r<2^{b}-m

r

b-1

muussa tapauksessa loppuosa koodataan luvun binäärimerkinnällä , joka on sijoitettu bitteinä.

r

r+2^{b}-m

b

Myöhemmin R. Gallagher ja D. Van Voorhees osoittivat, että Golombin ehdottama koodi ei ole optimaalinen vain erilliselle arvojoukolle, joka täyttää yllä olevan kriteerin, vaan myös kaikille , joille kaksois-epäyhtälö on totta. $s$ $s$

{\displaystyle p^{m}+p^{m+1}\leq 1<p^{m}+p^{m-1))

missä on positiivinen kokonaisluku. Koska millä tahansa on aina korkeintaan yksi arvo , joka täyttää yllä olevan epäyhtälön, S. Golombin ehdottama geometrisen lähteen koodausmenettely osoittautuu optimaaliseksi mille tahansa arvolle . $m$ $s$ $m$ $s$

Erittäin helppokäyttöinen, mutta ei aina optimaalinen Golomb-koodin versio siinä tapauksessa, että potenssi 2 on nimeltään Rice-koodi. $m$

Esimerkki

Anna , numero on koodattava . $p=0,85$ $n=13$

Arvo, joka tyydyttää kaksinkertaisen Gallagher-Van Voorhees-epäyhtälön . $m = 4$

Yllä kuvatun koodausmenettelyn mukaisesti koodattua numeroa 13 vastaava koodisana muodostetaan osamäärän n/m unaariesityksenä:

q=\left[{\frac {n}{m}}\right]=\left[{\frac {13}{4}}\right]=3

(unaarikoodi , eli q nollaa ja yksi), $0001$

ja koodattu loppuosa

r=1

(koodi , eli itse loppuosa, joka on kirjoitettu bitteinä). $01$ $\lceil \log _{2}(m)\rceil$

Tuloksena oleva koodisana

0001|01

Katso myös

Eksponentiaalinen Golomb-koodi

Linkit

SW Golomb. Run-length-koodaukset // IEEE Trans. inf. Theor. - 1966. - Nro 3, IT-12 . - s. 399-401.
R. G. Gallager, D. C. Van Voorhis. Optimaaliset lähdekoodit geometrisesti jakautuneille kokonaislukuaakkosille // IEEE Trans. inf. Theor. - 1975. - Nro 2, IT-21 . - s. 228-230.
R. R. Rice, J. R. Plaunt. Mukautuva muuttuvapituinen koodaus avaruusalusten televisiodatan tehokkaaseen pakkaamiseen // IEEE Trans. yhteisössä. - 1971. - Voi. 16(9). - s. 889-897.
2.3 Golomb-koodit / Amir Said, optimaalisten parametroitujen etuliitekoodien määrittämisestä adaptiivista entropiakoodausta varten. HPL-2006-74

Puristusmenetelmät _

Teoria

Tiedot	Oma Keskinäinen Haje Ehdollinen entropia Monimutkaisuus Redundanssi
Yksiköt	Bitti Nat Napostella Hartley Hartleyn kaava

Häviötön

Entropian pakkaus	Epäsymmetriset lukujärjestelmät Huffmanin algoritmi Mukautuva Huffman-algoritmi Shannon-Fano-algoritmi Shannonin algoritmi Aritmeettinen koodaus ( intervalli ) Golomb koodit Delta Universaali koodi Elias fibonacci
Sanakirjamenetelmät	RLE Tyhjennä LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandardi )
muu	RLE CTW BWT MTF PPM DMC

Audio

Teoria	Convolution PCM Aliasing Näytteenotto Kotelnikovin lause
menetelmät	LPC LAR LSP WLPC CELP ACELP Laki μ-laki ADPCM MDCT Fourier-muunnos Psykoakustinen malli
muu	Äänen kompressori Puheen pakkaus Band koodaus

Kuvat

Ehdot	väriavaruutta Pikseli Saturaatio-alinäytteenotto Pakkausesineitä
menetelmät	RLE DPCM fraktaali aallokko EZW SPIHT LP PrEP PCL
muu	Bittinopeus Normaali testikuva PSNR Kvantisointi

Video

Ehdot	Videon ominaisuudet Kehys Kehystyypit Videon laatu
menetelmät	Liikekompensointi PrEP Kvantisointi aallokko
muu	Videokoodekki Nopeuden vääristymisteoria CBR ABR VBR