CRC

Kode ziklikoek, CRC kode (Cyclic Redundancy Check) izena hartzen dute, baita polinomio kode izena ere. Hauen erabilera oso hedaturik dago, hardwarean modu erraz batean implementa daitezkeelako eta oso ahaltsuak direlako.

Kode hauek oinarri bezala G(X) polinomio eraikitzaile bat dute, r gradukoa eta printzipio hau ere oinarritzat daukate: n bit datu bitar baldin badauzkagu, hauek n-1 mailako polinomio baten koefiziente izan daitezke.

Adibidez, 10111 zenbaki bitarra x⁴ + x² + x¹ + x⁰ polinomiotzat tratatu dezakegu.

Datuak adierazten dituzten bit hauei, erredundantziako r bit gehitzen zaizkie horrela sortzen den polinomioa hasierako polinomioarekin zatigarria izan dadin. Hartzaileak jasotako polinomioa G(X)-ekin zatigarria den edo ez egiaztatuko du. Hau horrela ez bada, [transmisio errore] bat egongo da.

Datu-bitak blokeetan zatitzen dira (ingelesez frame deiturikoak) eta bloke bakoitzari r gradua kalkulatzen zaio, zeinak blokearen egiaztapen sekuentzia (Frame Check Sequence, FCS, ingelesez) izena ere hartzen duen.

Hauek dira gehien erabiltzen diren polinomio eraikitzaileak:

CRC-12: x¹²+ x¹¹ + x³ + x² + x¹ + 1. 6 biteko fluxuak transmititzeko erabiltzen da, erredundantziako 12 bitekin batera. Beste era batera esanda, 6 biteko blokeak erabiltzen ditu eta 12 bitetik sortzen duen FCS bat gehitzen die.

CRC-16: x¹⁶ + x¹⁵ + x² + 1. 8 biteko fluxuetarako erabiltzen da, erredundantziarentzat 16 erabiliz. AEB-tan erabiltzen da nagusiki.

CRC-CCITT: x¹⁶ + x¹² + x⁵ + 1. 8 biteko fluxuetarako, erredundantziarentzat 16 erabiliz. Europan erabiltzen da nagusiki.

CRC-32: x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1. 16 biteko CRC kodeek baino segurtasun handiagoa eskaintzen du, azken hauek nahikoa eskaintzen duten arren. Sare lokalen estandarren batzordean erabiltzen du (IEEE 802), hala nola AEB-en Defentsako departamentuak.

G(x)=x²+1 motako polinomio eraikitzaile bat baldin badugu, CRC-k errore bakoiti guztiak antzeman ditzake, 2 biteko erredundantzia sortuko du eta ez da errore bikoitz guztiak antzemateko gai izango, adibidez, errore-balioko sekuentzia bat beti oharkabea litzateke.

Adibide honetan, 14 biteko mezuari dagokion CRC kodea lortuko dugu. Erabiliko dugun CRC polinomioa x³+x+1 izango. 3.mailako polinomio honek 4 koefiziente ditu: 1.x³+0.x²+1.x+1.x⁰, beraz polinomioa bitar bezala idatziz 1,0,1,1. Eta emaitza 3 zenbakikoa izango da.

Erabiliko den mezua:

11010011101100

Lehenik 0ak sartuko ditugu eskuinetik. Polinomio zatitzailea izango denaren n luzera - 1 eginaz. Gure polinomio zatitzailea 1,0,1,1 da beraz 4-1=3 zero sartuko ditugu eskuinetik. 3-biteko CRCa lortzeko lehe zatiketa.

11010011101100 000 <--- input right padded by 3 bits
1011               <--- zatitzailea(4 bits) = x³+x+1
------------------
01100011101100 000 <--- emaitza

Zatiketa XOR eragiketa erabiliz egiten da. (XOR taula laburtua: 1-1=0; 0-0=0; 1-0=1; 0-1=1). Ezkerraldeko bit zenbakitzailea 0 denean ez da ezer egiten:

11010011101100 000 <--- bidaltzera goazen trama eskubitik 3 bit gehitu ondoren
1011               <--- zatitzailea
01100011101100 000 <--- emaitza
 1011              <--- zatitzailea...
00111011101100 000
  1011
00010111101100 000
   1011
00000001101100 000 <--- "tokatzen diren" ezkerraldeko bitak 0 izatera, zuzenean mugitu dugu polinomio izendatzailea
       1011
00000000110100 000
        1011
00000000011000 000
         1011
00000000001110 000
          1011
00000000000101 000 
           101 1
-----------------
00000000000000 100 <--- hondarra (3 bit)

Mezua ongi bidalia izan dela egiaztatzeko, hartzaileak, bidalitako trama osoaren -datu bitak + CRC kodea- zatiketa berriro egitea besterik ez du. Oraingoan, errorerik ez baldin badago emaitza 0 izango da.

11010011101100 100 <--- hartzaileak jasotakoa CRC kodea barne duelarik
1011               <--- izendatzailea
01100011101100 100 <--- emaitza
 1011              <--- izendatzailea...
00111011101100 100

......
  
00000000001110 100
          1011
00000000000101 100 
           101 1
------------------
                 0 <--- hondarra

• CRC-ren azalpena ingelesez