CRC

Turinys

• Apie CRC (Cyclic Redundancy Check)
• CRC-1
• CRC algebra
• CRC skaičiavimas
• CRC algoritmo implementacija
• Nuorodos

Apie CRC (Cyclic Redundancy Check)

CRC yra kontrolinės sumos (checksum) metodas, naudojamas aptikti duomenų (pvz. duomenų perdavimo) klaidas. Norint patikrinti ar duomenys yra perduodami neiškraipyti - kartų su duomenimis yra perduodama ir kontrolinė suma (apskaičiuojama iš normų perduoti duomenų). Perduodant duomenis su kontroline suma pilnas duomenų srautas įgauna tokia forma: < _norimi perduoti duomenys_ >< _kontrolinė suma apskaičiuota iš norimų perduoti duomenų_ >.

Kiekvienas CRC metodas turi jį atitinkantį polinomą (CRC metodo pavadinime bitų skaičius tik nurodo vienanarių kiekį, bet ne jų koeficientus, todėl prieš skaičiuojant išsiaiškinti pagal kokį polinomą reikia atlikti skaičiavimus. Pavyzdžiui CRC-3 gali naudoti bet kokį x³+a₂x²+a₁x¹+a₀x⁰ = x³+a₂x²+a₁x+1 formos polinomą, kur a_i gali būti 0 arba 1 (aukčiausias koeficientas visada bus 1) t.y. teoriškai ir x³+1 ir x³+x²+x+1 gali būti naudojamas CRC-3 skaičiavime).

CRC-1

Paprasčiausias (taip pat ir mažiausiai patikimas) CRC metodas aptikti perdavimo klaidas yra CRC-1. Visa CRC-1 yra perduodamų duomenų gale pridėti bitą, kuris naudojamas kaip kontrolinė suma. CRC-1 gali būti dviejų tipų: lyginis ir nelyginis. Kai naudojamas lyginis CRC-1 skaičiavimas - kontrolinės sumos bito reikšmė yra 1 tik tuo atveju, jei vienetų (bitų reikšmę) skaičius yra nelyginis (į skaičiavimą neįtraukiamas kontrolinės sumos bitas). Jei vienetų (bitų reikšmė) skaičius yra lyginis - kontrolinės sumos bito reikšmę yra 0. Nelyginio CRC-1 atveju viskas atvirkčiai: kontrolinio bito reikšmę yra 1 kai vienetų skaičius lyginis ir 0 kai - nelyginis. Lyginis CRC-1 yra specialus CRC atvejis, kur vieno bito kontrolinė suma apskaičiuojama pagal x+1 polinomą.

9 bitai duomenų	vienetų suma	perduodami duomenys su kontroline suma (10 bitų)
		lyginis	nelyginis
000000000	0	0000000000	0000000001
1011001001	5	10110010011	10110010010
1110101100	6	11101011000	11101011001
1111111111	9	11111111111	11111111110

"CRC algebra"

Dviejų skaičių sudėtis "CRC aritmetikoje" yra lygiai tokia pat kaip paprasta binarinė sudėtis tik rezultatas turi būti moduliu 2. Paprastai tariant, tai reiškia, kad kiekviena atitinkama bitų pora duoda atitinkamą rezultatą, kuris neįtakoja kitų bitų rezultato. Atitinkami bitai sudedami pagal tokias taisykles:

0+0=0
0+1=1
1+0=1
1+1=0 (bet ne 10)

Pavyzdžiui:

 10110101011
+10010011100
 ===========
 00100110111

Atimtis atliekama analogiškai vadovaujantis tokia logika:

0-0=0
0-1=1 (!)
1-0=1
1-1=0

Pavyzdžiui:

 10110101011
-10010011100
 ===========
 00100110111

Kaip matosi iš pavyzdžiu, sudėtis ir atimtis "CRC aritmetikoje" atitinka XOR operaciją, kuri yra pati sau atvirkštinė operacija.

Apibrėžus sudėti, nesunku atlikti daugybos ir dalybos veiksmus:

Daugyba:

1001 x 1011 = 1010011

   1001
  x1011
=======
   1001
  1001.
 0000..
1001...
=======
1010011

Dalyba:

100110 / 101 = 1011 ir liekana 1

     1011
     ======
101) 100110
     101,,.
     ====,.
      011,.
      000,.
      ====.
       111.
       101.
       ====
        100
        101
        ===
          1 - liekana

CRC skaičiavimas

CRC skaičiavimas yra ne kas kita kaip "CRC algebros" dalyba. Prieš atliekant skaičiavimus yra pasirenkamas daliklis - norimo pločio (aukščiausio 1 bito pozicija. CRC-16 plotis yra 16, CRC-32 - 32 ir t.t.) polinomas.

Tarkim, kad turim duomenis sudarytus is 1101011011 bitų sekos ir norim apskaičiuoti CRC-4 pagal x⁴+x+1 polinomą (atitinka 10011 bitų seką, o plotis yra 4). Prie duomenų sekos yra pridedama polinomo pločio skaičiaus nulinių bitų ("1101011011" + "0000" = "11010110110000") ir atlikama dalyba tarp naujai gautos sekos ir atitinkamos polinomo bitų sekos:

           1100001010
       ==============
10011) 11010110110000
       10011,,.,,....
       =====,,.,,....
        10011,.,,....
        10011,.,,....
        =====,.,,....
         00001.,,....
         00000.,,....
         =====.,,....
          00010,,....
          00000,,....
          =====,,....
           00101,....
           00000,....
           =====,....
            01011....
            00000....
            =====....
             10110...
             10011...
             =====...
              01010..
              00000..
              =====..
               10100.
               10011.
               =====.
                01110
                00000
                =====
                 1110 - liekana (CRC kontrolinė suma)

Trumpai tariant yra trys žingsniai:

• Pasirenkamas W pločio polinomas G
• Duomenys papildomi W skaičiumi nulinių bitų ir gauname naujus duomenis M'
• Atliekę dalybą M' iš G gaunam liekaną, kuri ir yra kontrolinė suma

CRC algoritmo implementacija

Nuorodos

http://www.maximintegrated.com/app-notes/index.mvp/id/3969

https://marcel.wanda.ch/Tutorial/CRC/CyclicRedundancyCheck

http://www.ross.net/crc/download/crc_v3.txt