Epäsymmetriset numerojärjestelmät

Epäsymmetriset numerojärjestelmät ( ANS , sanoista "epäsymmetriset lukujärjestelmät") on Yaroslav (Jarek) Dudan vuonna 2006 keksimä entropiakoodausmenetelmien perhe, joka perustuu hänen esittelemäänsä epäsymmetristen lukujärjestelmien käsitteeseen. Vuodesta 2014 lähtien sitä on käytetty tietojen pakkaamiseen useissa ohjelmissa, koska nämä menetelmät antavat pakkausasteen suhteen suunnilleen yhtä hyvän tarkan approksimation optimaaliseen entropiakoodaukseen kuin aritmeettinen koodaus , mutta niillä on parempi suorituskyky, ei huonompi purkunopeudeltaan kuin Huffmanin koodausalgoritmeilla ; Lisäksi on oleellista, että näitä menetelmiä ei suojata patenteilla ja että ne ovat vapaasti käytettävissä, sillä tekijän tavoitteena oli luoda ja levittää maksuton vaihtoehto aritmeettiselle koodaukselle.

Epäsymmetristen lukujärjestelmien käsite

Epäsymmetriset numerojärjestelmät ovat paikkalukujärjestelmien yleistys, jossa eri merkit voidaan koodata eri numeroilla edeltävistä numeroista (merkeistä) riippuen.

Laskennassa informaatio on tapana esittää bittivirtana ja uuden tiedon - symbolin - lisääminen tapahtuu osoittamalla lopussa olevaan numeroon symbolin koodia vastaavat numerot - uudet alemmat numerot. Perinteisillä paikkanumerojärjestelmillä lähestyttäessä mikä tahansa merkki vastaa samaa määrää numeroita. Tämä sopii hyvin silloin, kun eri symbolien kohtaamisen todennäköisyys on sama.

Kun eri merkkien kohtaamisen todennäköisyydet vaihtelevat, entropiakoodausta käytetään tiedon tallentamiseen kompaktimmin. Joten Huffman-koodauksessa eri merkkejä voidaan kirjoittaa eri bittimäärillä. Kuitenkin tässä tapauksessa merkit koodataan kokonaislukumäärällä bittejä - mikä tarkoittaa erityisesti sitä, että riippumatta siitä, kuinka usein merkki esiintyy, sen koodaamiseen tarvitaan vähintään yksi bitti.

Epäsymmetrisissä lukujärjestelmissä merkin koodaus ei riipu pelkästään siitä, millainen merkki se on, vaan myös tilan heijastamasta aikaisemmasta kontekstista. Vaadittujen numeroiden määrä pysyy kokonaislukuna, mutta se vaihtelee ja voi olla jopa nolla.

Kirjallisuus

• Duda, Jarek. "Optimaalinen koodaus diskreetissä hilassa translaatioinvarianttien rajoituksilla käyttämällä tilastollisia algoritmeja." arXiv preprint arXiv:0710.3861 (2007).

• Duda, Jarek. "Epäsymmetriset numerojärjestelmät" arXiv preprint arXiv:0902.0271 (2009).

• Duda, Jarek, Khalid Tahboub, Neeraj J. Gadgil ja Edward J. Delp. "Epäsymmetristen numerojärjestelmien käyttö huffman-koodauksen tarkkana korvaavana." Arkistoitu 22. lokakuuta 2017 Wayback Machine In Picture Coding Symposiumissa (PCS), 2015, pp. 65-69. IEEE, 2015.

• Duda, Jarek. "Epäsymmetriset numerojärjestelmät: entropiakoodaus, joka yhdistää Huffman-koodauksen nopeuden aritmeettisen koodauksen pakkausasteeseen." arXiv preprint arXiv:1311.2540 (2013).

• Najmabadi, Seyyed Mahdi, Zhe Wang, Yousef Baroud ja Sven Simon. "Korkean suorituskyvyn laitteistoarkkitehtuurit epäsymmetristen numerojärjestelmien entropiakoodaukseen." In Image and Signal Processing and Analysis (ISPA), 2015 9th International Symposium on, pp. 256-259. IEEE, 2015.