Asymmetriske talsystemer

Asymmetriske talsystemer ( ANS , fra "asymmetriske talsystemer") er en familie af entropikodningsmetoder opfundet af Yaroslav (Jarek) Duda i 2006 baseret på konceptet om asymmetriske talsystemer, han introducerede. Siden 2014 har den været brugt til datakomprimering i en række programmer, da disse metoder, hvad angår komprimeringsgraden, giver nogenlunde samme gode nøjagtige tilnærmelse til den optimale entropikodning som aritmetisk kodning , men de har højere ydeevne, ikke ringere i dekompressionshastighed end Huffmans kodningsalgoritmer ; desuden er det væsentligt, at disse metoder ikke er beskyttet af patenter og er gratis at bruge, da oprettelsen og distributionen af ​​et gratis alternativ til aritmetisk kodning var forfatterens mål.

Konceptet med asymmetriske talsystemer

Asymmetriske talsystemer er en generalisering af positionstalsystemer, hvor forskellige tegn kan indkodes med et forskelligt antal cifre, afhængigt af de foregående cifre (tegn).

I databehandling er det sædvanligt at repræsentere information som en strøm af bit, og tilføjelsen af ​​ny information - et symbol - sker ved at tildele tallet i slutningen de cifre, der svarer til symbolets kode - nye lavordenscifre. Når man nærmer sig med konventionelle positionsnummersystemer, svarer ethvert tegn til det samme antal cifre. Dette er velegnet i tilfælde, hvor sandsynligheden for at møde forskellige symboler er den samme.

Når sandsynligheden for at støde på forskellige tegn er forskellige, bruges entropikodning til mere kompakt at registrere information. Så i Huffman-kodning kan forskellige tegn skrives i forskellige antal bits. Men i dette tilfælde er tegn kodet af et helt antal bits - hvilket især betyder, at uanset hvor ofte et tegn forekommer, kræves der mindst en bit for at kode det.

I asymmetriske talsystemer afhænger kodningen af ​​et tegn ikke kun af, hvilken slags karakter det er, men også af den tidligere kontekst, der afspejles af staten. Antallet af nødvendige cifre forbliver et heltal, men det varierer og kan endda være nul.

Litteratur

• Duda, Jarek. "Optimal kodning på diskret gitter med translationelle invariante begrænsninger ved hjælp af statistiske algoritmer." arXiv preprint arXiv:0710.3861 (2007).

• Duda, Jarek. "Asymmetriske talsystemer" arXiv fortryk arXiv:0902.0271 (2009).

• Duda, Jarek, Khalid Tahboub, Neeraj J. Gadgil og Edward J. Delp. "Brugen af ​​asymmetriske talsystemer som en nøjagtig erstatning for huffman-kodning." Arkiveret 22. oktober 2017 på Wayback Machine In Picture Coding Symposium (PCS), 2015, s. 65-69. IEEE, 2015.

• Duda, Jarek. "Asymmetriske talsystemer: entropikodning, der kombinerer hastigheden af ​​Huffman-kodning med komprimeringshastigheden for aritmetisk kodning." arXiv preprint arXiv:1311.2540 (2013).

• Najmabadi, Seyyed Mahdi, Zhe Wang, Yousef Baroud og Sven Simon. "Højgennemløbshardwarearkitekturer til asymmetriske talsystemers entropikodning." I Image and Signal Processing and Analysis (ISPA), 2015 9th International Symposium on, pp. 256-259. IEEE, 2015.