Gama kód je jednoduchý algoritmus pro kódování přirozených čísel. V tomto kódování se využívá kódování alfa, kódování beta a kódování beta s čárkou. Gama kód je permutací gama kódu s čárkou (viz níže).

Gama kód přirozeného čísla N se vytváří z těchto komponent:

  • alfa kód délky beta kódu N (slovo A)
  • beta s čárkou N (slovo B)

Slovo A je vždy o jeden symbol delší, než část B. Proto je možné "vložit" mezi jednotlivé symboly delší část všechny symboly kratšího slova tak, že liché symboly pochází ze slova A, zatímco všechny sudé symboly z části B (například ze slov AAAA a BBB vznikne slovo ABABABA).

Nechť je tedy zavedena funkce F, která toto "vnoření" kratšího řetězce do delšího provede. Gama kód je pak definován takto:

£ \gamma (N) = F(\alpha (|\beta(N)|), \beta' (N)) £
ČísloSlovo ASlovo BKód
11prázdný řetězec1
2010001
3011011
40010000001
50010100011
1000010100001001
10000000011001000100000100001

Příklad

Kódování čísla 42

Beta kód (binární zápis) čísla 42 je 101010. Délka tohoto řetězce je 6. Alfa kód čísla 6 je 000001. Tím máme hotovou první část (slovo A). Nyní znovu vezmeme beta kód čísla 42 a odebereme z něj první jedničku, čímž získáme jeho beta kód s čárkou, což je 01010. Toto je druhá část (slovo B). Nyní "vnoříme" kratší slovo (slovo B) do slova delšího (slovo A). Získáme tak výsledný gama kód: 00010001001.

Gama kód s čárkou

Gama kód s čárkou přirozeného čísla N se vytváří ze stejných komponent jako gama kód:

  • alfa kód délky beta kódu N (slovo A)
  • beta s čárkou N (slovo B)

Namísto funkce F, která jednotlivá slova "vložila" do sebe, je použito obyčejné zřetězení:

£ \gamma' (n) = \alpha (|\beta(n)|) \dotplus \beta' (n) £
ČísloSlovo ASlovo BKód
11prázdný řetězec1
2010010
3011011
40010000100
50010100101
1000010100001010
10000000011001000000001100100

Příklad

Kódování čísla 42

Beta kód (binární zápis) čísla 42 je 101010. Délka tohoto řetězce je 6. Alfa kód čísla 6 je 000001. Tím máme hotovou první část (slovo A). Nyní znovu vezmeme beta kód čísla 42 a odebereme z něj první jedničku, čímž získáme jeho beta kód s čárkou, což je 01010. Toto je druhá část (slovo B). Nyní už jen obě části zřetězíme (000001 a 01010) a získáme výsledný gama kód s čárkou: 00000101010.

Reference

  • předmět X36KOD na ČVUT