Asymmetric numeral systems, review of advances in entropy coding

No Thumbnail Available
Files
Raivio_Samuli_2024.pdf (781.05 KB)
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Date
2024-03-01
Department
Major/Subject
Tietotekniikka
Mcode
SCI3027
Degree programme
Teknistieteellinen kandidaattiohjelma
Language
en
Pages
45
Series
Abstract
This thesis explores the advances in entropy coding, primarily focusing on asymmetric numeral systems introduced by Jarek Duda. The goal of entropy coding is to compress messages by exploiting redundancy in unequal symbol distributions. For example, the letter “e” occurs 60 times more often in English text than “z”, meaning that encoding either in the same space is immensely wasteful. There exists an intrinsic informational content in a message which determines the shortest message required to transmit that information, which entropy coding aims to reach. Before asymmetric numeral systems, there have been two widely used entropy coding methods: Huffman coding and arithmetic coding. Huffman coding can be decoded very efficiently but it cannot reach the lower bound. Arithmetic coding is nearly optimal, but slower to decode. Asymmetric numeral systems aim to provide the accuracy of arithmetic coding, while retaining the performant decoding of Huffman coding. The thesis is primarily a review of existing literature, but it also contains some experimental work to analyze the properties of various entropy coding systems. The work also contains some survey of literature apart from publications, as many significant advances in entropy coding have occurred outside academia. The research indicated that asymmetric numeral systems are currently the best choice for many, if not most, entropy coding use cases. Many implementation concerns and advances in implementation are considered in the thesis. As such, this work should serve as a solid starting point for understanding and implementing modern and efficient entropy coders.

Entropiakoodaus on oleellinen osa tiedon pakkausta: lähes kaikki käytännön pakkausmuodot (esim. zip, mp3 tai jpg) sisältävät entropiakoodausvaiheen toteutuksissaan. Entropiakoodaus perustuu informaatioteoreettiseen tulokseen, jonka mukaan viestejä voi pakata vain tiettyyn alarajaan asti menettämättä tietoa. Kaksi yleisintä entropiakoodausmenetelmää ovat Huffmanin koodaus sekä aritmeettinen koodaus. Huffmanin koodaus on mahdollista purkaa hyvin tehokkaasti, mutta sitä käyttämällä ei voi saavuttaa optimaalista koodauspituutta useissa tapauksissa. Aritmeettinen koodaus puolestaan pääsee hyvin lähelle pakatun koon raja-arvoa, mutta siten koodattuja viestejä on hitaampi purkaa. Tämä kandidaatintyö tutkii uutta vaihtoehtoista menetelmää: epäsymmetrisiä lukujärjestelmiä (engl. asymmetric numeral system, ANS). Jarek Dudan kehittämien epäsymmetristen lukujärjestelmien väitetään kykenevän saavuttamaan aritmeettisen koodauksen tarkkuuden Huffmanin koodauksen tehokkuudella. Tutkielmassa tarkastellaan etenkin epäsymmetristen lukujärjestelmien rANS- sekä tANS-variantteja, jotka ovat lupaavimmat käytännön tarkoituksiin. Työ on suoritettu suurimmalta osin kirjallisuustutkimuksena. Materiaalina on käytetty artikkeleita, joissa entropiakoodaus ja tekniikat ovat alun perin esitelty. Lisäksi materiaaliin sisältyy laajasti tutkimuksia tekniikoiden jatkokehityksestä sekä niiden ominaisuuksien analysoinnista. Työssä on otettu myös huomioon keskeisiä akateemisen maailman ulkopuolisia lähteitä, sillä suuri osa innovaatiosta entropiakoodauksessa tapahtuu sen ulkopuolella. Monet työssä esitellyt algoritmit ovat myös toteutettu ohjelmallisesti itsenäistä analysointia varten. Tutkimus myös sisältää katsauksen tANS-koodausta käyttävään FiniteStateEntropy-kodeekkiin ja sen suorituskykyyn Huffman-koodaukseen verrattuna. Tutkimus varmistaa väitteen epäsymmetristen lukujärjestelmien lupaavasta tarkkuudesta. Algoritmien toteutuksista paljastui rakenteita vaihtoehtoisen tANS-alustusalgoritmien suhteellisessa tarkkuudessa, joista voi olla hyötyä uusien alustusalgoritmien kehityksessä. Kirjallisuuskatsauksesta selvisi, että epäsymmetristen lukujärjestelmien rANS-variantin on todistettu saavuttavan asymptoottisesti optimaalisen koodauksen, mutta käytännön epätarkkuuden ylärajan tarkasti määrittäminen on yhä avoin ongelma. Tutkimus osoittaa, että epäsymmetriset lukujärjestelmät ovat tällä hetkellä paras valinta suureen osaan entropiakoodaustarpeista. Huffmanin koodaus on yhä laskennallisesti tehokkain vaihtoehto ja aritmeettinen koodaus on luontevampi adaptiivisiin tarkoituksiin. Kandidaatintutkielma toimii myös lähestyttävänä lähteenä epäsymmetrisiin lukujärjestelmiin ja voi siten helpottaa niiden käyttöönottoa.
Description
Supervisor
Savioja, Lauri
Thesis advisor
Chalermsook, Parinya
Keywords
compression, entropy coding, asymmetric numeral systems, Huffman coding, arithmetic coding, range coding
Other note
Citation