Omega kód je jednoduchý algoritmus kódování přirozených čísel. Omega kód čísla 1 je definován jako 0, kód obecného přirozeného čísla N > 1 lze definovat rekurzivně pomocí tohoto algoritmu:

  1. Nechť řetězec A je binární zápis (kódování beta) čísla N.
  2. Je-li délka řetězce A větší než 2, opakuj předchozí krok pro N = délka řetězce A zmenšená o jedničku.
  3. Na konec kódového slova přidej nulu.
ČísloKonstrukce kóduKód
100
210.0100
311.0110
410.100.0101000
510.101.0101010
1011.1010.01110100
10010.110.1100100.01011011001000

Příklad

Kódování čísla 38

Binární zápis (beta kód) čísla 38 je 100110, což uložím jako aktuální kódové slovo. Délka tohoto řetězce je ale 6, což je více než 2. Na začátek kódového slova tedy vložíme binární zápis čísla 6 - 1 = 5, což je 101. Délka tohoto řetězce je 3, což je více než 2. Na začátek kódového slova tedy vložíme binární zápis čísla 3 - 1 = 2, což je 10. Délka tohoto řetězce je 2, což není více než 2. Proto skončíme a na konec kódového slova přidáme nulu. Výsledné kódové slovo je tedy zřetězení řetězců 10, 101, 100110 a 0, což je 10101100110.

Omega kód s čárkou

Omega kód s čárkou funguje na stejném principu jako kód omega, ale rekurze se zastaví dříve a vznikají tak obecně kratší kódová slova. Omega kód s čárkou čísla 1 je definován jako 00, kód obecného přirozeného čísla N > 1 lze definovat rekurzivně pomocí tohoto algoritmu:

  1. Nechť řetězec A je binární zápis (beta kód) čísla N.
  2. Je-li délka řetězce A větší než 3, opakuj předchozí krok pro N = délka řetězce A zmenšená o jedničku.
  3. Na konec kódového slova přidej nulu.
ČísloKonstrukce kóduKód
10.000
2010.00100
3011.00110
4100.01000
5101.01010
10011.1010.001110100
100110.1100100.011011001000

Příklad

Kódování čísla 38

Binární zápis (beta kód) čísla 38 je 100110, což uložím jako aktuální kódové slovo. Délka tohoto řetězce je ale 6, což je více než 3. Na začátek kódového slova tedy vložíme binární zápis čísla 6 - 1 = 5, což je 101. Délka tohoto řetězce je 3, což není více než 3. Proto skončíme a na konec kódového slova přidáme nulu. Výsledné kódové slovo je tedy zřetězení řetězců 101, 100110 a 0, což je 1011001100.

Reference

  • předmět X36KOD na ČVUT