BCH-koodeista

Abstract

Tämän tutkielman tarkoituksena on tutustuttaa lukija BCH-koodeihin. BCH-koodit ovat syklisiä koodeja ja ne pystyvät korjaamaan useita virheitä. Tutkielmassa esitetään erilaisia tapoja korjata koodisanoihin tulleita virheitä käyttäen hyväksi äärellisten kuntien teoriaa ja lineaari- sekä polynomialgebraa.

Yksinkertainen kahden sanan koodi koostuu esimerkiksi koodisanoista 000 ja 111. Koodisanojen etäisyys on niiden positioiden määrä, missä sanat eroavat toisistaan. Sanojen 000 ja 111 etäisyys on siis 3. Koodin virheenkorjauskyky on sidottu koodin minimietäisyyteen d(C), joka on kaikkien koodin koodisanojen välinen minimietäisyys. Koodi korjaa t virhettä, jos d(C) on vähintään 2t + 1. Tämä esimerkkikoodi {000, 111} korjaa siis yhden virheen. Virheenkorjaus tapahtuu lähimmän naapurin -periaatteella, missä vastaanotettu sana koodataan siksi koodisanaksi, jota se on lähimpänä eli johon sen etäisyys on lyhin. Ekvivalentti koodi on sellainen koodi, jolla on samat ominaisuudet kuin alkuperäisellä koodilla. Esimerkiksi koodi {010, 101} on ekvivalentti koodin {000, 111} kanssa.

Edistyneemmissä koodeissa, kuten lineaarisissa koodeissa, koodisanojen määrä on suuri. Kaikkia lineaarisen koodin koodisanoja ei kuitenkaan tarvitse luetella vaan niiden muodostamisessa käytetään apuna virittäjämatriisia. Vastaavasti lineaarinen koodi on helppo dekoodata pariteetintarkistusmatriisin avulla. Virittäjä- ja pariteetintarkistusmatriisi voidaan kumpikin esittää standardimuodossa, joka sisältää yksikkömatriisin. Syndrooma on koodisanavektorin ja pariteetintarkistusmatriisin transpoosin tulo. Se ilmaisee koodisanassa virheen paikan.

Sykliset koodit ovat lineaarisia koodeja, mutta näille esitetään virittäjä ja pariteetintarkistus polynomien avulla. Polynomeille voidaan suorittaa modulolaskentaa samoin kuin kokonaisluvuillekin. Tämä vahvuus tekee syklisistä koodeista haluttuja niiden koodauksen ja dekoodauksen suhteellisen helppouden ja nopeuden ansiosta.

Lineaariset Hammingin koodit korjaavat vain yhden virheen. Sykliset koodit pystyvät polynomiominaisuuksiensa ansiosta korjaamaan niin sanottuja purskevirheitä eli peräkkäin esiintyviä virheitä. Jopa 6-pituinen purskevirhe on mahdollista korjata käyttäen vain 2-pituisen purskeen korjaavaa koodia, kun käytetään lomitustekniikkaa. Siinä koodisanoja ei lähetetäkään peräkkäin, vaan kolmen koodisanan ryppäinä lomitettuna. Jos siis halutaan lähettää 7-pituiset koodisanat A = A0A1...A6, B = B0B1...B6 ja C = C0C1...C6, niin sen sijaan, että lähetetään koodisanat peräkkäin: A0A1...A6B0B1...B6C0C1...C6, lähetetäänkin ne lomittain: A0B0C0A1B1C1...A6B6C6. Nyt 6-pituisen purskevirheen sattuessa kukin koodisana A, B ja C kärsii vain kahdesta virheestä, jotka voidaan korjata erikseen kunkin koodisanan kohdalla.

BCH-koodit voidaan esittää syklisinä koodeina ja täten niille pätevät kaikki syklisten koodien algebralliset ominaisuudet. BCH-koodeille esitetään niin sanottu BCH-avainyhtälö, jonka avulla vastaanotetut sanat ovat helposti ja nopeasti dekoodattavissa koodisanoiksi virheistä huolimatta.