Elias Omega Code

Elias Omega Code  je univerzální kód pro kódování kladných celých čísel, který vyvinul Peter Elias.

Stejně jako Eliasovy gama a delta kódy přiřazuje začátku celého čísla řád jeho velikosti v univerzálním kódu. Na rozdíl od ostatních dvou zmíněných kódů však kód omega rekurzivně kóduje prefix, a proto je také známý jako rekurzivní kód Elias .

Chcete-li zakódovat číslo:

  1. Přepište skupinu nul na konci pohledu.
  2. Pokud je kódované číslo jedna, zastavte; pokud ne, přidejte binární reprezentaci čísla jako skupinu na začátek reprezentace.
  3. Opakujte předchozí krok s počtem právě zapsaných číslic (bitů) mínus jedna, jako u nového čísla, které má být zakódováno.

Prvních několik kódů je uvedeno níže. Uvedeno je také tzv. odhadované rozdělení, které popisuje rozdělení hodnot, pro které toto kódování vede ke kódu minimální velikosti (viz: univerzální kód ).

Začněte kódovat:

Číslo Kódování Odhadovaná
pravděpodobnost
jeden 0 1/2
2 100 1/8
3 110 1/8
čtyři 10 100 0 1/64
5 10 101 0 1/64
6 10 110 0 1/64
7 10 111 0 1/64
osm 11 1000 0 1/128
9 11 1001 0 1/128
deset 11 1010 0 1/128
jedenáct 11 1011 0 1/128
12 11 1100 0 1/128
13 11 1101 0 1/128
čtrnáct 11 1110 0 1/128
patnáct 11 1111 0 1/128
16 10 100 10 000 0 1/2048
17 10 100 10001 0 1/2048
…

Algoritmus pro dekódování čísla reprezentovaného v Elias omega kódu:

  1. Začněte s proměnnou N nastavenou na 1.
  2. Přečtěte si první "skupinu" za zbývajícími N číslicemi, které se budou skládat buď z "0" nebo "1". Pokud se skládá z "0", znamená to, že hodnota celého čísla je 1; pokud začíná "1", pak N získá hodnotu skupiny, která je interpretována jako binární číslo.
  3. Přečtěte si každou další skupinu; bude sestávat buď z "0" nebo "1" za zbývajícími N číslicemi. Pokud je skupina "0", znamená to, že hodnota celého čísla je N; pokud začíná "1", pak N nabývá hodnoty skupiny, interpretované jako binární číslo.

Kódování Omega se používá v aplikacích, kde není předem známa největší hodnota, která má být zakódována, nebo pro kompresi dat, kde jsou malé hodnoty mnohem běžnější než velké.

Viz také

Literatura