Computational Methods for Classification of Codes

Julkaisun otsikon käännös: Laskennallisia mentelmiä koodien luokitteluun

Janne I. Kokkala

    Tutkimustuotos: Doctoral ThesisCollection of Articles

    Abstrakti

    Digitaalisessa viestinnässä ja tiedontallennusjärjestelmissä keskeinen ongelma on löytää hyviä koodausmenetelmiä, joilla voidaan siirtää tai tallentaa tietoa tehokkaasti tilanteissa, joissa voi esiintyä virheitä. Monet koodausteorian ongelmat voidaan esittää kombinatoristen objektien avulla, ja näitä ongelmia voidaan ratkoa teoreettisilla ja laskennallisilla menetelmillä. Tässä työssä kehitetään algoritmeja koodien ja peittotaulukoiden luokittelu- ja olemassaolo-ongelmiin. Peittotaulukot muistuttavat matemaattisesti koodeja, ja niitä käytetään esimerkiksi ohjelmistojen testeissä. Algoritmit käyttävät yleisiä tekniikoita kattavaan hakuun ja isomorfisten objektien karsimiseen. Kehitettyjä menetelmiä sovelletaan työssä kolmeen ongelmaan. Ensiksi luokitellaan kaikki MDS-koodit (engl. maximum distance separable), joiden aakkoston koko on enintään 8 ja minimietäisyys vähintään 3. Luokittelussa löydetään kolme uutta ekvivalenssiluokkaa täydellisiä yhden virheen korjaavia MDS-koodeja, joiden aakkoston koko on 8. Toiseksi luokitellaan pieniä peittotaulukoita. Luokittelun tarkoitus on auttaa niiden rakenteen tutkimisessa, ja saadut tulokset myös ratkaisevat optimaalisen peittotaulukon koon joissakin tapauksissa. Kolmantena ratkaistaan 8-ulotteisen hyperkuution neliön kromaattinen luku. 1990-luvun alkupuolelta alkaneista yrityksistä huolimatta tähän ongelmaan ei ole aiemmin löydetty ratkaisua. Tässä työssä ongelma ratkaistaan lähestymällä sitä koodausteorian näkökulmasta ja käyttämällä menetelmää, jossa kiinnitetään haettavan rakenteen symmetrioita.
    Julkaisun otsikon käännösLaskennallisia mentelmiä koodien luokitteluun
    AlkuperäiskieliEnglanti
    PätevyysTohtorintutkinto
    Myöntävä instituutio
    • Aalto-yliopisto
    Valvoja/neuvonantaja
    • Östergård, Patric, Vastuuprofessori
    Kustantaja
    Painoksen ISBN978-952-60-7581-5
    Sähköinen ISBN978-952-60-7580-8
    TilaJulkaistu - 2017
    OKM-julkaisutyyppiG5 Artikkeliväitöskirja

    Tutkimusalat

    • algoritmi
    • luokittelu
    • MDS-koodi
    • peittotaulukko
    • kromaattinen luku

    Sormenjälki

    Sukella tutkimusaiheisiin 'Laskennallisia mentelmiä koodien luokitteluun'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

    Siteeraa tätä