Reedin ja Solomonin koodit

Abstract

Huttunen Katariina, Reedin ja Solomonin koodit, matematiikan pro gradututkielma, 49 s., Jyväskylän yliopisto, Matematiikan ja tilastotieteen laitos, syksy 2016. Tutkielman tarkoituksena on esitellä Reedin ja Solomonin koodeja ja niiden ymmärtämiseksi tarvittavia esitietoja. Reedin ja Solomonin koodit ovat virheenkorjaamiskoodeja, joiden käsittelyssä käytetään äärellisiä kuntia. Virheenkorjaamiskoodeja tarvitaan kun dataa siirretään paikasta toiseen, koska siirron aikana voi tapahtua virheitä ja näin ollen perille tullut data eroaa alkuperäisestä.Virheenkorjaamiskoodienavullaalkuperäinendatavoidaanmahdollisesti selvittää perille tulleesta viallisesta datasta. Edellä käytetään sanaa mahdollisesti,koskavirheenkorjaamiskoodeillaonolemassaylärajasillekuinka monta virhettä saa tapahtua, jotta alkuperäinen data voidaan vielä selvittää. Reedin ja Solomonin koodien kohdalla tämä yläraja riippuu koodin parametreistä n ja k yhtälön t =bn−k+1 2 c mukaan. Parametri n on koodin koodisananpituus ja parametri k on koodin dimensio, toisin sanoen koodisanan varsinaista informaatiota sisältävän osan pituus. Varsinaisten informaatiota välittävän osanlisäksivirheenkorjaamiskoodeissaonpätkädataa,jotakäytetäänvirheenkorjaamiseen. Tähän osaan kuuluvia symboleita kutsutaan rendundanssisymboleiksi ja niiden määrä on siis n−k. Redundanssisymbolit ovat lineaarisesti riippuvia informaatiosymboleista. Reedin ja Solomonin koodeista on olemassa syklinen versio ja alkuperäinen ei-syklinenversio.SyklisetReedinjaSolomoninkooditovatnykyisinenemmän käytetty muoto, koska niille on olemassa tehokkaita algoritmeja, joilla koodisanat voidaan purkaa alkuperäiseksi viestiksi. Syklisen Reedin ja Solomonin koodin koodisanojen pituus on n = pm −1 ja alkuperäisellä tavalla muodostetun Reedin ja Solomonin koodin koodisanan pituus on taas n = pm. Tässä pm on äärellisen kunnan Fpm alkioiden lukumäärä. Äärellistä kuntaa käytetään Reedin ja Solomonin koodien molemmissa tapauksissa koodin aakkostona eli koodisanojenmerkkisymbolitovatjonkinsopivanäärellisenkunnanalkioita.Se mitääärellistäkuntaakäytetäänriippuulähetettävänviestinkoosta,halutusta virheenkorjaamiskyvystä ja minkälaista kanavaa käytetään.