Virheiden havaitseminen ja korjaaminen koodausteorian avulla
Miikka Venäläinen
Matematiikan ja tilastotieteen tutkinto-ohjelma Marraskuu 2023 Tässä tutkielmassa lähestytään koodausteoriaa matriisilaskennan kautta.Koodausteoria tutkii viestien koodaamista siten, että lähetyksen aikaiset kohinan aiheuttamat muutokset voitaisiin havaita ja korjata virheenkorjauskoodin avulla.Kohinasta aiheutuvaa koodisanan muutosta kutsutaan virheeksi.Virheenkorjauskoodin tärkeimmät käsitteet ja tulokset määritellään tutkielman toisessa luvussa.Kolmannessa ja neljännessa luvussa keskitytään ryhmäkoodin määrittelyyn ja Hamming-koodin muodostamiseen.Luvussa 2 esitellään nimitys 𝑛-bittijono sellaisille bittijonoille, joiden pituus on 𝑛.Lukijalle tulee myös tutuksi koodaus-ja purkufunktioiden määritelmät.Tämän jälkeen määritellään Hamming-etäisyys, joka on funktio, ja myös metriikka, joka kertoo kahden 𝑛-bittijonon toisistaan eroavien bittien lukumäärän.Hammingetäisyyden avulla määritellään koodin minimietäisyys, joka on minimi koodisanojen Hamming-etäisyyksien joukosta.Minimietäisyys on virheenkorjauskoodin tärkeä ominaisuus, sillä se määrittää voiko kohinasta aiheutuvaa virhettä havaita tai korjata.Aivan luvun lopussa osoitetaankin yhteys koodin minimietäisyyden ja purkumenetelmän virheentunnistus-ja virheenkorjauskyvyn välillä.Tulokseksi saadaan, että minimietäisyyden ollessa vähintään kolme, purkumenetelmä voi korjata yhden virheen tai havaita yhden ja kahden bitin virheet.Luvun 3 pääpaino on ryhmäkoodeissa ja niiden ominaisuuksissa.Ryhmäkoodit ovat erityislaatuisia koodeja, joiden kahden koodisanan summa on edelleen koodisana.Luvun ensimmäisessä alaluvussa määritellään bittien yhteenlaskutoimitus ja paino, ja osoitetaan painon ja Hamming-etäisyyden välinen yhteys.Toinen alaluku pitää sisällään vektori-ja matriisilaskentaa, joiden tulosten avulla osoitetaan, että ryhmäkoodeja voidaan tuottaa virittäjämatriiseilla, joka on nopea tapa luoda virheenkorjauskoodi.Yksi tällainen virittäjämatriisi on luvun lopussa määritelty kanoninen
•Jan 1, 2023•0 citations