Golombovo kódování

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Golombovo kování je bezeztrátová kompresní metoda patřící do skupiny kódu vynalezených Solomonem W. Golombem v 60. letech. Pro takové abecedy, které mají geometrické rozdělení pravděpodobnosti, bude Golombovo kódování optimální a bude tvořit prefixový kód. Z této vlastnosti plyne, že toto kódování bude velmi vhodné pro takové případy, kdy pravděpodobnost malých hodnot na vstupu bude mnohonásobně vyšší než pravděpodobnost velkých.

Ricovo kódování (podle Roberta F. Ricea) označuje podmnožinu Golombových kódů, které vytvářejí jednodušší (ale teoreticky suboptimální) prefixový kód. Rice použil tuto množinu kódů v rámci adaptivního kódování; "Riceovo kódování" tak může odkazovat buď na toto adaptivní kódování, nebo na speciální podmnožinu Golombových kódů. Zatímco v obecném Golombově kódování může být volitelný parametr M libovolné kladné celé číslo, Riceovo kódování volí parametr tak, aby byl mocninou dvou. Tato vlastnost činí Riceovo kódování vhodnějším pro počítačové využití, protože násobení a dělení dvěma je v binární aritmetice mnohem efektivnější.

Riceovo kódování se používá v mnoha bezeztrátových kompresních algoritmech pro obrázky a zvuk.

Přehled[editovat | editovat zdroj]

Tvorba kódu[editovat | editovat zdroj]

Golombovo kódování používá nastavitelný parametr M k tomu, aby vstupní hodnoty rozdělilo na dvě části: q, výsledek celočíselného dělení M a r zbytek po dělení. Hodnota q se zakóduje pomocí unárního kódování a je následována zbytkem zakódovaným pomocí zkráceného binárního kódování. Pokud M=1, pak je Golombovo kódování shodné s unárním.

Golomb rice code.svg

Golomb-Riceovo kódování si můžeme představit jako zakódování čísla pomocí pozice q a posunu r. Obrázek výše ukazuje pozici q a posun r pro kódování čísla N za použití Golomb-Riceova kódování s parametrem M.

Formálně jsou dvě části definovány následujícím výrazem, kde x je číslo, které chceme zakódovat: q = \left \lfloor \frac{\left (x-1 \right )}{M} \right \rfloor a r = x-qM-1 Konečný výsledek pak je: \left( q+1 \right) r.

r se může sestávat z proměnlivého počtu bitů, speciálně z b bitů pro Riceovo kódování, v případě Golombova kódování se mění mezi b-1 a b bity. Nechť b = \lceil\log_2(M)\rceil. Když 0 \leq r < 2^b-M, pak se použije b-1 bitů pro zakódování r, pokud 2^b-M \leq r < M pak se použije b bitů. Je zřejmé, že b=\log_2(M) pokud M je mocnina dvou tak můžeme zakovat všechny hodnoty r pomocí b bitů.

Parametr M je funkcí odpovídajícího Bernouliho procesu, který je parametrizován pomocí p=P(X=0) pravděpodobností úspěchu daného binomického rozdělení. M je buď mediánem daného rozdělení, nebo medián +/- 1. Můžeme ho odvodit z následujících nerovností:

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

Golomb ve své práci tvrdí, že pro velká M je velmi malý postih, když vybereme M = \left\lfloor \frac{-1}{\log_2(1-p)}\right\rfloor.

Golombovo kování je ekvivalentní Huffmanovu kódování pro zadané pravděpodobnosti, kdyby bylo možné vytvořit Huffmanův kód (což pro geometrické rozdělení nejde, neboť se nejedná o diskrétní rozdělení).

Případ s celými čísly[editovat | editovat zdroj]

Golombovo bylo navrženo k zakódování sekvencí nezáporných čísel. Může být ale snadno rozšířeno tak, aby bylo schopné zakódovat i obecné posloupnosti celých čísel. Všem vstupním hodnotám přiřadíme nové hodnoty z množiny celých kladných čísel, tak aby byly unikátní a mohli jsme je později přiřadit zpět. Posloupnost začínající: 0,-1,1,-2,2,-3,3,-4,5 ... n-tá negativní hodnota (t.j. -n) je namapována jako n-té liché číslo (2n-1), a m-té kladné číslo je vyjádřeno jako m-té sudé číslo (2m). Optimální prefixový kód vznikne jen v případě, že kladná čísla a hodnoty záporných čísel odpovídají tomu samému geometrickému rozdělení.

Jednoduchý algoritmus[editovat | editovat zdroj]

Následující algoritmus popisuje, jak zakódovat hodnotu na vstupu pomocí Rice-Golombova kódování.

  1. Zaokrouhlit M na celočíselnou hodnotu.
  2. Pro číslo N, které chceme zakódovat, najděme
    1. podíl = q = int[N/M]
    2. zbytek = r = N mod M
  3. Vygenerujeme kódové slovo
    1. Formát kódu : <zakódovaný podíl><zakódovaný zbytek>, kde
    2. zakódovaný podíl je (zakódován unárně)
      1. Zakódujeme q jako sekvenci q 1 a na konec přidáme 0
    3. kód zbytku je (zakódován zkráceně binárně)
      1. Když M je mocnina dvou, bude potřeba \log_2(M) bitů. (Riceovo kódování)
      2. Když M není mocnina 2, tak b = \lceil\log_2(M)\rceil
        1. Když r < 2^b-M zakódujeme r pomocí standardního binárního kódování délky b-1 bitů.
        2. Když r \ge 2^b-M zakódujeme číslo r+2^b-M pomocí standardního binárního kódování o délce b bitů.

Příklad[editovat | editovat zdroj]

Nastavme M = 10. Tedy b = \lceil\log_2(10)\rceil = 4. Ořez pak bude 2^b-M = 16-10 = 6

Zakódování podílu
q výstupní bity
0 0
1 10
2 110
3 1110
4 11110
5 111110
6 1111110
: :
N <N opakování 1>0
Zakódování zbytku
r posun binárně bity na výstupu
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

Například pro Golomb-Rice kódování s parametrem M=10 a číslem pro zakódování 42 se nejprve spočítá q=4 a r=2. Pak se obě částí zakódují q=11110 a r=010 a výsledné kódové slovo vznikne složením těchto dvou částí. Části už není potřeba od sebe oddělovat, protože první část poznáme snadno - končí tam, kde se poprvé objeví nula.

Ukázkový kód algoritmu[editovat | editovat zdroj]

Tento základní kód předpokládá Riceovo kódování, tedy že M=2k.

Zakódování[editovat | editovat zdroj]

 void golombEncode(char* vstup, char* vystp, int M)
 {
     IntReader intreader(vstup);
     BitWriter bitwriter(vystup);
     while(intreader.hasLeft())
     {
         int num = intreader.getInt();
         int q = num / M;
         for (int i = 0 ; i < q; i++)
             bitwriter.putBit(true);   // zapíše q jedniček
         bitwriter.putBit(false);      // zapíše jednu nulu
         int v = 1;
         for (int i = 0 ; i < log2(M); i++)
         {            
             bitwriter.putBit( v & num );  
             v = v << 1;         
         }
     }
     bitwriter.close();
     intreader.close();
 }

Dekódování[editovat | editovat zdroj]

 void golombDecode(char* vstup, char* vystup, int M)
 {
     BitReader bitreader(vstup);
     IntWriter intwriter(vystup);
     int q = 0;
     int nr = 0;
     while (bitreader.hasLeft())
     {
         nr = 0;
         q = 0;
         while (bitreader.getBit()) q++;     
         for (int a = 0; a < log2(M); a++)   
             if (bitreader.getBit())
                 nr += 1 << a;
         nr += q*M;                          
         intwriter.putInt(nr);               
     }
     bitreader.close();
     intwriter.close();
 }

Použití pro run-length kódování[editovat | editovat zdroj]

Obrázek ukazuje Golombovo kódování, když vybíráme M optimálně pro dané p ≥ 1/2.

Máme-li abecedu o dvou symbolech, nebo množinu dvou událostí P a Q s pravděpodobnostmi p a (1 - p), kde p\geq \frac{1}{2}. Golombovo kódování může být použito k zakódování nula nebo více P oddělených jedním Q. V takovém případě je nejlepší nastavit parametr M jako nejbližší celé číslo k  \frac{-1}{\log_{2}p}. Když p=\frac{1}{2}, M = 1 a Golombovo kódování je shodné s unárním.

Aplikace[editovat | editovat zdroj]

Riceovo kódování je použito v několika kódech pro zpracování signálu pro predikci zbytků. V prediktivních algoritmech, kde zbytky mají tendenci se rozdělit tak, že odpovídají dvoustrannému geometrickému rozdělení s malými zbytky častějšími než velkými, Riceův kód téměř odpovídá Huffmanovu kódu pro dané rozdělení s tou výhodou, že nemusí přenášet Huffmanovu tabulku. Jediný signál, který neodpovídá geometrickému rozdělení je sinová vlna, kde jsou velké a malé zbytky podobně pravděpodobné.

Několik bezeztrátových zvukových kompresních algoritmů jako jsou Shorten,[1] FLAC,[2] Apple Lossless, a MPEG-4 ALS používá Riceovo kódování v rámci svého kódovacího procesu. Riceovo kódování je také použito pro bezeztrátovou kompresi obrázků FELIICS.

Rice-Golombovo kódování je použito jako součást Riceova algoritmu pro bezeztrátovou kompresi obrázků. Na grafu je vidět porovnání kompresních poměrů Riceova kódování a algoritmu Gzip.

Experiment - zkoumání kompresních poměrů

Riceovo kódování může produkovat dlouhé posloupnosti jedniček pro podíl zakódovaný unárně, často je tedy nutné nastavit nějaký limit. Modifikovaná verze Rice-Golombova kódování umožňuje nahradit dlouhé sekvence jedniček pomocí rekurzivního Rice-Golombova kódování.

Reference[editovat | editovat zdroj]

  1. man shorten
  2. FLAC documentation: format overview

Literatura[editovat | editovat zdroj]