Kontrollkood

Kontrollkood ("redundancy check") on arvutivõrgus ülekandevigade avastamiseks ja parandamiseks mõeldud kood. Andmete saatmisel võib neis tekkida vigu (näiteks sideliini häirete tõttu võib saaja või vahendav võrguseade mõnda bitti valesti tõlgendada). Seetõttu on oluline kontrolli võimalus. Selleks on võimalus andmete juurde lisada kontrollkoodina lisabitte, mille põhjal saaks mingi tõenäosusega kindlaks teha, kas andmed on vastuvõtul samad, mis algselt saadetud. Kontrollkood peaks olema võimalikult väikesemahuline. Kontrollkood on mõeldud tehniliselt toimunud vigade avastamiseks, kuid see ei paku kaitset ründajate vastu. Kontrollkoodi arvutamiseks on kolm põhilist moodust: paarsuskontroll, CRC ja kontrollsumma ("checksum").
Paarsuskontroll.
Paarsuskontrolli teostades loetakse kokku andmeühikus olevate bittide "1" arv. Kui bitte "1" oli paarisarv, siis paarsuskontrolli bitiks on "0", paaritu arvu "1" bittide korral on paarsuskontrolli bitiks "1". Selliselt saab avastada paaritu arvu bittide vigu. Oletame, et tahame saata andmeid, mille andmeühiku pikkus paarsuskontrolli bittide jaoks on 7 bitti ja paarsusbitt lisatakse kaheksandaks bitiks.
Olgu saadetavad andmed: 1101100 0100000 0010010 1101100 1101000, siis peale paarsusbittide lisamist oleks tulemus järgmine: 1101100(0) 0100000(1) 0010010(0) 1101100(0) 1101000(1) (paarsusbittidel on sulud ümber).
Kahemõõtmeline paarsuskontroll.
Täiendatud paarsuskontroll, mille puhul andmeühikud pannakse kahemõõtmelisse massiivi, kus paarsus leitakse nii ridade kui veergude põhjal. Olgu meil lähteandmeteks 1101100 0010010 1101100 0100000 1101000. Paigutame väiksemad andmeühikud ridade kaupa massiivi ja leiame nii veergude kui ridade paarsusbitid, samuti ridade paarsusbittide paarsusbiti. Seega oleks massiiv järgmine :
Andmeteks, mis teele saadetakse, on tekkinud massiiv ridade kaupa koos paarsusbittidega, seega on väljundbitid järgmised: 11011000 01000001 00100100 11011000 11010001 10110100.
CRC.
CRC ("cyclic redundancy check") on võimas ja paindlik vigade avastamise meetod. CRC koostab polünoomi, kus termi kordajateks on andmete bitid. Olgu edastavateks bittideks näiteks "10111101", siis polünoomiks on 1x7+0x6+1x5+1x4+1x31x2+0x1+1x0. Seejärel see polünoom jagatakse läbi kindla generaatorpolünoomiga. Selle jagamise jääk ongi CRC kontrollsumma. Erinevate CRC generaatorpolünoome :
CRC on riistvaras palju lihtsam realiseerida kui tarkvaras.
Kontrollsumma.
Kontrollsumma leidmisel jagatakse andmed fikseeritud pikkusega osadeks, mis liidetakse arvudena kokku. Saadud tulemuse number lahutatakse jällegi eelnevalt fikseeritud pikkusega osadeks ja liidetakse kokku. Saadud tulemusest võetakse binaarne eitus, mis ongi kontrollusmma väärtus.
Kontrollsumma kontrollimiseks jagatakse jällegi andmed eelnevalt fikseeritud pikkusega osadeks ja liidetakse omavahel arvudena kokku koos kontrollsumma osaga. Saadud tulemus jagatakse jällegi eelnevalt fikseeritud pikkusega osadeks ja liidetakse omavahel kokku ja kui saadud tulemuse binaarne eitus on null, siis kontrollsumma klappis, vastasel korral mitte.
Teeme protsessi läbi kuueteistkümne biti pikkuse kontrollsumma näite varal (seda kasutab näiteks IP protokoll). Lühiduse ja lihtsuse mõttes leiame kaheksa baidi jagu andmetele kontrollsumma. Olgu nendeks andmeteks, millele arvutame kontrollsumma, kuueteistkümnendsüsteemis :
Kontrolliks jagame andmed eelnevalt fikseeritud pikkusega osadeks ja liidame nad kokku koos kontrollsummaga:
Liidame saadud tulemuse osad omavahel kokku:
Saadud tulemuse binaarne eitus on tõesti null, seega kontroll oli edukas.
Ethernet kaader. Ethernet tehnoloogias arvutatakse kontrollsumma sihtaadressist kuni andmete osa lõpuni. Kui kontrollsumma ei klapi, siis visatakse kaader vastuvõtul minema. Kui hakkab tekkima liiga palju vigase kontrollsummaga kaadreid, siis võib see viidata vigasele Etherneti võrguliidesele, rikutud või vigastele draiveritele, halvasti paigaldatud kaabli otsikule, vigasele kaablile, välisele mürale vmt. Kontrollsummana kasutatakse CRC-32 4 baiti.
Tsükliline liiasuse kontroll.
Arvutatakse CRC kontrollsumma. Peaaegu võimatu on juhuslike bitimuudatuste tulemusena saada sama kontrollsummat. Andmeid käsitletakse bitijadana. Esimesed 8 bitti laaditakse arvuti registrisse ja teostatakse XOR-tehe. Esimeseks operandiks on registris olevad 8 bitti, teine on vabalt valitud polünoom, mis peab olema teada ka andmete saajale (et oleks võimalik sama arvutus paketi saamisel ka läbi viia). Tehete tulemus salvestatakse uuesti registrisse, selle järel nihutatakse registri sisu vasakule ja madalamale järgule salvestatakse uus andmebitt. Tekkinud arvuga tehakse uuesti XOR-tehe (kasutades sama polünoomi) ja tulemus salvestatakse uuesti registrisse. Tsüklit korratakse senikaua, kuni andmeid jätkub. Antud tsükli lõppedes on registris kontrollsumma, mis salvestatakse paketi päisesse. Vastuvõtmisel teostatakse sama operatsioon. Kui saadakse päises identne tulemus päises olevaga, ei ole andmete sisu moondunud.
CRC Arvutamine
Binaarse CRC n-biti arvutamisel, tuleb sisendbitid rivistada järjest ja (n+1) biti CRC jagaja ("divisor") paigutada selle alla, vasakusse äärde. Näitena kasutame 3-bit CRC:
Kui sisendbit ("input") vasakpoolsema biti väärtus on 0, ei tohi seda kaotada vaid jagaja tuleb nihutada ühe biti koha võrra paremale. Kui aga sisendi vasakpoolsem bit omab väärtust 1, siis jagajaga sooritatakse XOR tehe. Jagaja seejärel nihutatakse jällegi biti võrra paremale ja protsess kordub seni, kui jagaja jõuab sisendi bitirea parempoolsesse otsa. Vaatame järgmist näidet: