Analiza CRC-a

Mehanizam CRC-a je sasvim jednostavan. Još uvek nismo odgovorili na pitanje ima li ikakve koristi od ovog metoda. Da li će primalac moći da detektuje oštećeni okvir? Oslanjamo se na pretpostavku da će deljenje oštećenog okvira sa G(x) dati ostatak različit od nule. Ali, da li je to uvek tačno? Da li je moguće da se bitovi u nizu T promene tako da posle deljenja sa G(x) ostatak bude nula?

Kompletan i detaljan dokaz zahteva poznavanje svojstava faktorizacije prstena polinoma (oblast apstraktne matematike) i ovde se nećemo baviti time. Umesto toga, sledi kraća rasprava koja će Vam pomoći da steknete osećaj za način na koji funkcioniše. Za početak, definišimo preciznije šta tražimo. Promena bitova u nizu T je analogna sabiranju nekog nepoznatog polinoma sa T(x). Dakle, ako T' predstavlja primljeni niz i ako je T'(x) pridruženi polinom, onda je T'(x) = T(x) + E(x), gde je E(x) nepoznat primaocu niza T'. U prethodnom primeru

niz T = 11010111010 odgovara polinomu T(x) = x10 + x9 + x7 + x5 + x4 + x3 + x
niz E = 00010110000 odgovara polinomu E(x) = x7 + x5 + x4
niz T' = 11000001010 odgovara polinomu T'(x) = x10 + x9 + x3 + x


Ne zaboravite da se sabiranje izvodi pomoću operacije isključivo ILI. Na primer, sabiranje članova x7 iz E(x) i T(x) daje x7 + x7 = (1 + 1) *x7 = 0.

Moramo da damo odgovor na pitanje kada T(x) + E(x)/G(x) daje ostatak nula. Pošto je (T(x) + E(x))/G(x) = T(x)/G(x) + E(x)/G(x) i pošto prvi član daje ostatak nula, drugi član određuje ostatak. Zbog toga, postavljeno pitanje može da se preformuliše tako da glasi za koje polinome E(x) deljenje E(x)/G(x) daje ostatak nula.

Sada možemo da tvrdimo sledeće:

Nedetektovane greške u toku prenosa odgovaraju greškama za koje je G(x) faktor polinoma E(x).

Sledeće pitanje je pod kojim je uslovima G(x) faktor polinoma E(x). Proučićemo najpre najjednostavniji primer, gde se menja samo jedan bit u nizu T. U ovom slučaju E(x) ima samo jedan član - xk za neki celi broj k. Jedini način da G(x) bude faktor xk je da je G(x) jednako x podignut na neki stepen. Sve dok biramo G(x) sa najmanje dva člana, to neće biti moguće. Tako će CRC moći da detektuje sve jednostruke greške.

Zatim, razmotrimo navalnu grešku dužine k <= r = stepen G(x).

* Pretpostavimo da je polinom T(x) predstavljen kao

tntn-1 . . . ti+k-1ti+k-2 . . . ti ti-1 . . . t1t0

k bitovi na koje smetnje utiču (k affected bits)

a ti+k-1 . i ti su prvi i poslednji bit koji će biti oštećeni. Bitovi između ova dva bita se proizvoljno menjaju. To znači da je

E(x) = xi+k-1 + . . . + xi = xi * (xk-1 + . . . + 1)

Zato je

E(x)/ G(x) =  xi * (xk-1 + . . . + 1)/G(x)

Pretpostavimo sada da je G(x) izabrano tako da x nije faktor G(x). Zbog toga, G(x) i xi iz prethodnog razlomka nemaju zajedničke faktore. Ako je G(x) faktor brojioca, onda mora da bude faktor (xk-1. + 1). Pošto smo izabrali k <= r, onda je k - 1 < r i G(x) ne može da bude faktor polinoma sa manjim stepenom.

Zato donosimo sledeći zaključak:

Ako x nije faktor G(x), onda se detektuju sve navalne greške koje imaju dužinu manju, ili jednaku stepenu G(x).

Razmotrite sledeću navalnu grešku bilo koje dužine u kojoj je oštećen neparan broj bitova. Pošto E(x) ima član za svaki oštećeni bit, sadrži neparan broj članova. Zbog toga, E(1) (isključivo ILI neparnog broja jedinica) daje 1. Sa druge strane, pretpostavimo da je x + 1 faktor polinoma G(x). U tom slučaju, možemo da zapišemo G(x) = (x + 1) * H(x), gde je H(x) neki izraz.

* Stepen polinoma je najveći eksponent za x.

Pogledajte sada šta se dešava ako se pretpostavi da su se javile neke nedetektovane greške.  Sećate se da nedetektovana greška znači da je G(x) faktor polinoma E(x). Zamenom G(x) sa (x + 1) * H(x) dobija se da je E(x) = (x + 1) * H(x) * K(x). Sada, ako se ova jednačina izračuna za x = 1, faktor x + 1 izjednačava E(1) sa 1.

Jasno je da oboje ne može da se javi istovremeno. Ako i dalje pretpostavljamo da je x + 1 faktor polinoma G(x), onda pretpostavka o nedetektovanoj grešci koja oštećuje neparan broj bitova nije opravdana. Drugim rečima:

Ako je x + 1 faktor G(x), onda su sve navalne greške koje oštećuju neparan broj bitova detektovane.

Poslednji slučaj koji razmatramo je navalna greška sa dužinom većom od stepena polinoma G(x).
Na osnovu prethodne rasprave zaključujemo da je

E(x)/ G(x) =  xi * (xk-1 + . . . + 1)/G(x)

Međutim, pošto ovoga puta pretpostavljamo da je k +> 1 = r = stepen G(x), moguće je da je G(x) faktor (xk-1 + . + 1). Kolike su šanse da će se ovo desiti? Razmotrimo najpre slučaj k - 1 = r. Pošto je stepen polinoma G(x) takođe  r, onda činjenica da je G(x) faktor (xr + . + 1) znači da je G(x) = (xr + . + 1). Sada članovi između xr i 1 definišu bitove na kojima je došlo do grešaka. Pošto postoji r - 1 takvih članova, postoji 2r-1  mogućih kombinacija oštećenih bitova. Ako pretpostavimo da se sve kombinacije javljaju sa podjednakom verovatnoćom, postoji verovatnoća od 1/2r-1 da kombinacije tačno odgovaraju članovima polinoma G(x). Drugim rečima, verovatnoća da neke greške neće biti detektovane iznosi 1/2r-1.

Slučaj za k - 1 > r je složeniji i ovde ga nećemo analizirati. Međutim, moguće je pokazati da verovatnoća da neke greške neće biti detektovane iznosi 1/2r. U literaturi možete da pronađete detaljniju analizu kodova za detekciju grešaka.

CRC se široko koristi u lokalnim mrežama (LAN mrežama), gde postoje standardni polinomi za G(x), poput sledećih:

CRC-12:    x12 + x11 + x3 + x2 + x + 1
CRC-16:    x16 + x15 + x2 + 1
CRC-ITU:    x16 + x12 + x5 +1
CRC-32:    x32 + x26 + x23 + x22 + x16 + x12 + x11
+ x10 + x8 + x7 + x5 + x4 + x2 + x + 1

U opštem slučaju, CRC je veoma efikasan ako se G(x) ispravno izabere. Specifično, G(x) može da se izabere tako da x nije faktor, ali x+1 jeste. U ovom slučaju CRC detektuje sledeće greške:

·   Sve navalne greške dužine r manje od stepena polinoma G(x)
·   Sve navalne greške koje utiču na neparan broj bitova
·   Sve navalne greške čija je dužina jednaka r + 1, sa verovatnoćom (2r-1 - 1)/2r-1
·   Sve navalne greške čija je dužina veća od r + 1, sa verovatnoćom (2r - 1)/2r

Na primer, CRC-32 polinom detektuje sve navalne greške čija je dužina veća od 33, sa verovatnoćom (232 - 1)/232. Ovo je ekvivalentno 99,99999998 odsto tačnosti. Nije loše.

Pripremio Dragan Marković

Nije lose