Asymetrické číselné soustavy

Asymetrické číselné soustavy ( ANS , od „asymetrické číselné soustavy“) je rodina metod kódování entropie , kterou vynalezl Yaroslav (Jarek) Duda v roce 2006 na základě konceptu asymetrických číselných soustav, který představil. Od roku 2014 se používá pro kompresi dat v řadě programů, protože tyto metody dávají z hlediska stupně komprese přibližně stejně dobré přesné přiblížení optimálnímu entropickému kódování jako aritmetické kódování , ale mají vyšší výkon, není horší v rychlosti dekomprese než Huffmanovy kódovací algoritmy ; kromě toho je nezbytné, aby tyto metody nebyly chráněny patenty a byly volně použitelné, protože vytvoření a distribuce bezplatné alternativy aritmetického kódování bylo cílem autora.

Pojem asymetrických číselných soustav

Asymetrické číselné soustavy jsou zobecněním pozičních číselných soustav, ve kterých mohou být různé znaky kódovány různým počtem číslic v závislosti na předcházejících číslicích (znakech).

Ve výpočetní technice je obvyklé reprezentovat informaci jako proud bitů a k přidání nové informace - symbolu - dochází tak, že se číslu na konci přiřadí číslice odpovídající kódu symbolu - nové číslice nízkého řádu. Při použití konvenčních pozičních číselných systémů odpovídá jakýkoli znak stejnému počtu číslic. To se dobře hodí v případě, kdy je pravděpodobnost setkání s různými symboly stejná.

Když se pravděpodobnost setkání s různými znaky liší, používá se entropické kódování pro kompaktnější záznam informací. Takže v Huffmanově kódování mohou být různé znaky zapsány v různém počtu bitů. Znaky jsou však v tomto případě kódovány celočíselným počtem bitů – což konkrétně znamená, že bez ohledu na to, jak často se znak vyskytuje, je k jeho zakódování potřeba alespoň jeden bit.

V asymetrických číselných soustavách závisí kódování znaku nejen na tom, o jaký znak se jedná, ale také na předchozím kontextu reflektovaném státem. Počet požadovaných číslic zůstává celé číslo, ale liší se a může být dokonce nula.

Literatura

• Duda, Jarek. "Optimální kódování na diskrétní mřížce s translačními invariantními omezeními pomocí statistických algoritmů." arXiv předtisk arXiv:0710.3861 (2007).

• Duda, Jarek. "Asymetrické číselné soustavy" arXiv předtisk arXiv:0902.0271 (2009).

• Duda, Jarek, Khalid Tahboub, Neeraj J. Gadgil a Edward J. Delp. "Použití asymetrických číselných soustav jako přesné náhrady za Huffmanovo kódování." Archivováno 22. října 2017 na Wayback Machine In Picture Coding Symposium (PCS), 2015, pp. 65-69. IEEE, 2015.

• Duda, Jarek. "Asymetrické číselné systémy: entropické kódování kombinující rychlost Huffmanova kódování s rychlostí komprese aritmetického kódování." arXiv předtisk arXiv:1311.2540 (2013).

• Najmabadi, Seyyed Mahdi, Zhe Wang, Yousef Baroud a Sven Simon. "Vysoce propustné hardwarové architektury pro entropické kódování asymetrických číselných systémů." In Image and Signal Processing and Analysis (ISPA), 2015 9th International Symposium on, pp. 256-259. IEEE, 2015.