Golombovy kódy

Golombovy kódy jsou rodinou entropických kódů . Golombův kód může znamenat i jednoho ze zástupců této čeledi.

Uvažujme zdroj, který nezávisle generuje nezáporná celá čísla s pravděpodobnostmi , kde libovolné kladné číslo nepřesahuje 1, tedy zdroj popsaný geometrickým rozdělením . Pokud je kladné celé číslo takové, že $i$ ${\displaystyle P(i)=(1-p)p^{i))$ $p$ $m$

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

pak optimálním kódem znak po znaku (to znamená kód, který spojuje každý zakódovaný znak s určitým kódovým slovem) pro takový zdroj bude kód vytvořený v souladu s postupem navrženým Solomonem Golombem , podle kterého např. jakékoli zakódované číslo se známým kódovým slovem, unárním zápisem čísla a zakódovaným v souladu s postupem popsaným níže, zbytek dělení : $n$ $m$ $q=\left[{\frac {n}{m}}\right]$ $r$ ${\frac {n}{m))$

Jestliže je mocnina 2, pak zbývající kód je binární reprezentace čísla , umístěná v bitech. $m$ $r$ $\log_2(m)$
Pokud není mocnina 2, vypočítá se číslo . Dále: $m$ $b=\lceil \log _{2}(m)\rceil$

Jestliže , je zbývající kód binární reprezentace čísla , umístěná v bitech,

r<2^{b}-m

r

b-1

jinak je zbytek zakódován binárním zápisem čísla , umístěným v bitech.

r

r+2^{b}-m

b

Později R. Gallagher a D. Van Voorhees ukázali, že kód navržený Golombem je optimální nejen pro diskrétní sadu hodnot splňujících výše uvedené kritérium, ale také pro všechny, pro které platí dvojitá nerovnost. $p$ $p$

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

kde je kladné celé číslo. Protože pro libovolnou vždy existuje maximálně jedna hodnota , která splňuje výše uvedenou nerovnost, ukazuje se postup pro kódování geometrického zdroje navržený S. Golombem jako optimální pro jakoukoli hodnotu . $m$ $p$ $m$ $p$

Extrémně snadno implementovatelná, ale ne vždy optimální verze Golombova kódu v případě, kdy je mocnina 2, se nazývá Riceův kód. $m$

Příklad

Nechte , je nutné zakódovat číslo . $p=0,85$ $n=13$

Hodnota, která vyhovuje dvojité Gallagher-Van Voorheesově nerovnosti . $m=4$

V souladu s výše popsaným kódovacím postupem je kódové slovo odpovídající kódovanému číslu 13 konstruováno jako unární reprezentace kvocientu n/m:

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

(unární kód , tj. q nul následovaných jedničkou), $0001$

a kódovaný zbytek

r=1

(kód , tedy samotný zbytek, zapsaný v bitech). $01$ $\lceil \log _{2}(m)\rceil$

Výsledné kódové slovo

0001|01

Viz také

Exponenciální Golombův kód

Odkazy

SW Golomb. Run-length encodings // IEEE Trans. inf. teor. - 1966. - č. 3, IT-12 . - S. 399-401.
R. G. Gallager, D. C. Van Voorhis. Optimální zdrojové kódy pro geometricky rozložené celočíselné abecedy // IEEE Trans. inf. teor. - 1975. - č. 2, IT-21 . - S. 228-230.
R. R. Rice, J. R. Plaunt. Adaptivní kódování s proměnnou délkou pro efektivní kompresi televizních dat kosmické lodi // IEEE Trans. o komunitě. - 1971. - Sv. 16(9). - S. 889-897.
2.3 Golombovy kódy / Amir Said, O stanovení optimálních parametrizovaných prefixových kódů pro kódování adaptivní entropie. HPL-2006-74

Kompresní metody

Teorie

Informace	Vlastní Vzájemné Entropie Podmíněná entropie Složitost Nadbytek
Jednotky	Bit Nat Okusovat Hartley Hartleyho vzorec

Bezztrátový

Entropická komprese	Asymetrické číselné soustavy Huffmanův algoritmus Adaptivní Huffmanův algoritmus Shannon-Fano algoritmus Shannonův algoritmus Aritmetické kódování ( interval ) Golombovy kódy Delta Univerzální kód Eliáš fibonacci
Slovníkové metody	RLE Vyfouknout LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
jiný	RLE CTW BWT MTF PPM DMC

Zvuk

Teorie	Konvoluce PCM Aliasing Vzorkování Kotelnikovova věta
Metody	LPC LAR LSP WLPC CELP ACELP Zákon μ-zákon ADPCM MDCT Fourierova transformace Psychoakustický model
jiný	Audio kompresor Komprese řeči Pásmové kódování

snímky

Podmínky	barevný prostor Pixel Saturační podvzorkování Kompresní artefakty
Metody	RLE DPCM fraktál vlnka EZW SPIHT LP Přípravka PCL
jiný	Bitová rychlost Standardní testovací obrázek PSNR Kvantování

Video

Podmínky	Vlastnosti videa Rám Typy rámů Kvalita videa
Metody	Kompenzace pohybu Přípravka Kvantování vlnka
jiný	Video kodek Teorie zkreslení sazby CBR ABR VBR