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 Tohtorinväitöskirja (artikkeli)

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ä