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).^[1]

Paarsuskontroll

Pikemalt artiklis 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) ^[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 ^[1] :

Andmeteks, mis teele saadetakse, on tekkinud massiiv ridade kaupa koos paarsusbittidega, seega on väljundbitid järgmised: 11011000 01000001 00100100 11011000 11010001 10110100.^[1]

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 ^[1] :

CRC-16 – 16 bitine. Generaatorpolünoomiks on x16+x15+x2+1. Kasutavad näiteks HDLC (High-Level Data Link Control), USB (Universal Series Bus).
CRC-CCITT – 16 bitine. Generaatorpolünoomiks on x16+x12+x5+1. Kasutavad näiteks PPP, Bluetooth.
CRC-32 – Generaatorpolünoomiks on x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x. Kasutab näiteks Ethernet.

CRC on riistvaras palju lihtsam realiseerida kui tarkvaras.^[1]

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.^[1]

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.^[1]

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 ^[1] :


71  38  EE  F3  0D  12  2B  C5

Jaotame andmed 16-bitisteks osadeks:

7138  EEF3  0D12  2BC5

Liidame osad kokku:

7138+EEF3+0D12+2BC5 = 0001 9902

Liidame saadud tulemuse osad omavahel kokku:

0001+9902=9903

Leiame 9903 binaarse eituse:

1001  1001  0000  0011 = 0110  0110  1111  1100

Milleks on 66FC, mis ongi kontrollsumma.

Kontrolliks jagame andmed eelnevalt fikseeritud pikkusega osadeks ja liidame nad kokku koos kontrollsummaga:

7138+EEF3+0D12+2BC5+66FC = 0001 FFFE

Liidame saadud tulemuse osad omavahel kokku:

0001+FFFE = FFFF

Saadud tulemuse binaarne eitus on tõesti null, seega kontroll oli edukas.^[1]

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.^[1]

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.^[2]

CRC Arvutamine ^[3]

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:


11010011101100 <--- Sisend
1011           <--- Jagaja (4 bitt)
--------------
01100011101100 <--- Tulemus

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:


11010011101100 <--- Sisend
1011           <--- Jagaja
01100011101100 <--- Tulemus
 1011          <--- Jagaja
00111011101100
  1011
00010111101100
   1011
00000001101100
       1011
00000000110100
        1011
00000000011000
         1011
00000000001110
          1011
--------------
00000000000101 <---Remainder (3 bits)

Viited

↑ ^1,00 ^1,01 ^1,02 ^1,03 ^1,04 ^1,05 ^1,06 ^1,07 ^1,08 ^1,09 ^1,10 Erkki Laaneoks: "Sissejuhatus võrgutehnoloogiasse" Tartu Ülikooli Kirjastus 2008. Lk 13-14, 37
↑ Ivari Horm, Jaak Kapten Arvutivõrgud konspekt Otsitud 9 Dets 2010.
↑ http://en.wikipedia.org/wiki/Cyclic_redundancy_check

[Erkki-1] 1,00 ^1,01 ^1,02 ^1,03 ^1,04 ^1,05 ^1,06 ^1,07 ^1,08 ^1,09 ^1,10 Erkki Laaneoks: "Sissejuhatus võrgutehnoloogiasse" Tartu Ülikooli Kirjastus 2008. Lk 13-14, 37

[2] Ivari Horm, Jaak Kapten Arvutivõrgud konspekt Otsitud 9 Dets 2010.

[3] ttp://en.wikipedia.org/wiki/Cyclic_redundancy_check

[1]

[2]

[3]