CRC doda Ci pewności, cz. 1.pdf

K U R S

CRC doda Ci pewnoci, czêæ 1

O tym, ¿e istniej¹ metody zabezpieczania transmisji wiedz¹

z pewnoci¹ wszyscy nasi Czytelnicy. Niewielu wie natomiast, co

tak naprawdê kryje siê pod magicznym pojêciem CRC, które

jest czêsto traktowane jako synonim bezpieczeñstwa wymiany

danych. Tajemnice CRC wyjanimy w cyklu artyku³ów, którego

czêæ pierwsz¹ publikujemy w tym w³anie numerze EP.

Chyba wiêkszoæ Czytelników spotka-

³a siê kiedy z tytu³owym okreleniem -

CRC. Co to jest? Na ogó³ CRC jest koja-

rzone z zagadnieniami zwi¹zanymi

z transmisj¹ danych. Niektórzy potrafi¹

rozszyfrowaæ ów akronim ( Cyclic Redun-

dancy Codes lub Check ), a zupe³nie nie-

liczni wiedz¹ dok³adnie o co chodzi. Nic

dziwnego. Powi¹zania z nie³atwym apa-

ratem matematycznym sk³aniaj¹ do ob-

chodzenia problemu szerokim ³ukiem.

Proponujê jednak chwilê cierpliwoci.

Okazuje siê, ¿e nie taki diabe³ straszny

jak go maluj¹.

ku jest najczêciej prowadzone bezpo-

rednio w czasie transmisji ( on-line ). Je-

li porównanie jest pomylne (streszcze-

nia s¹ identyczne), praca jest kontynuo-

wana, jeli nieca³y odebrany blok albo

jest ignorowany (jeli mo¿emy sobie na

to pozwoliæ), lub wys³ane jest do na-

dajnika ¿¹danie ponownej transmisji.

W pewnych sytuacjach mo¿liwe jest

nawet samodzielne skorygowanie

treci po stronie odbiorczej, bez koniecz-

noci powtarzania transmisji. Potrzebna

jest do tego jednak pewna nadmiarowoæ

(redundancja) przesy³anych informacji.

Warto w tym miejscu zaznaczyæ, ¿e CRC

mo¿e byæ stosowane nie tylko do kont-

roli transmisji danych. Za pomoc¹ CRC

mo¿na równie¿ kontrolowaæ np. popra-

wnoæ zapisu danych na noniku mag-

netycznym. U¿ytkownicy popularnych

programów archiwizuj¹cych, jak np. ZIP

lub RAR równie¿ korzystaj¹ z jego us³ug.

O metodach obliczania CRC bêdzie mo-

wa w dalszej czêci artyku³u.

Problemy podstawowe

Czy elementowa stopa b³êdów trans-

misji danych równa 10 -12 to du¿o, czy

ma³o? Parametr ten oznacza, ¿e na bi-

lion wys³anych elementów, statystycznie

jeden mo¿e zostaæ przek³amany. Dla lep-

szego uwiadomienia sobie proporcji za-

³ó¿my, ¿e na Ziemi ¿yje 4000 mln ludzi.

Liczba 10 -12 odpowiada wiêc jednemu

cz³owiekowi wybranemu sporód miesz-

kañców 250 planet takich jak Ziemia.

Pytanie pozostaje aktualne. Du¿o to, czy

ma³o? Hmmm, wydaje siê ¿e ma³o, na-

wet bardzo ma³o. Wróæmy wiêc do trans-

misji danych charakteryzuj¹cej siê tak¹

w³anie elementow¹ stop¹ b³êdów. Nie

jest to wartoæ abstrakcyjna. Parametrem

takim charakteryzuje siê np. system 10

Gbd Ethernet. Strach pomyleæ o skut-

kach ewentualnych b³êdów, gdyby prze-

sy³ane dane dotyczy³y np. systemów

podtrzymania ¿ycia czy operacji finanso-

wych. Jeli mówimy o przep³ywnoci to-

ru transmisyjnego równego np. 10 Gbd,

to dla wy¿ej za³o¿onej elementowej sto-

py b³êdów mo¿emy oczekiwaæ przek³a-

mañ co 100 sekund. Spodziewany co

niespe³na 2 minuty b³¹d nie mo¿e pozo-

stawiaæ nas w spokoju. Zdecydowanie

trzeba takim sytuacjom jako zaradziæ.

Jedn¹ z metod wyeliminowania skutków

b³êdów transmisji jest kontrola popra-

wnoci jej przebiegu. W praktyce mo¿e

wygl¹daæ tak: wysy³ane dane grupowane

s¹ w bloki, do ka¿dego bloku do³¹czana

jest na koñcu dodatkowa, krótka infor-

macja zawieraj¹ca specyficzny rodzaj

streszczenia zawartoci bloku. Odbior-

nik odbiera komplet informacji, dokonu-

je samodzielnego streszczenia bloku, po

czym sprawdza, czy w³asna wersja

streszczenia odpowiada wersji odebranej.

W praktyce streszczanie odbieranego blo-

W powy¿szym przyk³adzie dopisana na

koñcu suma kontrolna jest utworzona po-

przez zsumowanie (modulo 256) wszystkich

elementów bloku danych. W odebranej wia-

domoci nast¹pi³o przek³amanie drugiego

elementu. Zamiast 23 odebrano 27. Wyli-

czona w odbiorniku suma kontrolna odebra-

nego bloku nie jest zgodna z przes³an¹ su-

m¹ kontroln¹ (6+27+4=37¹33), co mo¿e byæ

podstaw¹ do stwierdzenia, ¿e odebrany blok

nie jest identyczny z orygina³em. Nie jest to

jednak mechanizm gwarantuj¹cy wystarcza-

j¹c¹ pewnoæ kwalifikacji odbieranych da-

nych. Np. pojedynczy b³¹d odebranej sumy

kontrolnej mo¿e byæ powodem uznania blo-

ku danych jako b³êdnego, mimo ¿e jest on

prawid³owy. Problem powiêksza siê, jeli

dopucimy b³êdy wielokrotne, nie mówi¹c

ju¿ o drastycznym zmniejszeniu skuteczno-

ci metody, gdy zwiêkszymy d³ugoæ bloku

danych, pozostawiaj¹c nadal sumowanie

modulo 256. W powy¿szym przyk³adzie

prawdopodobieñstwo niewykrycia b³êdów

wielokrotnych jest równe 1:256. B³êdy wie-

lokrotne mog¹ na tyle zafa³szowaæ wynik,

¿e nie zauwa¿ymy ich, nawet jeli faktycz-

nie wyst¹pi¹, jak choæby w poni¿szym przy-

k³adzie:

wiadomoæ: 6 23 4

wiadomoæ z sum¹ kontroln¹: 6 23 4 33

odebrana wiadomoæ: 8 20 5 33

Sumy kontrolne zgadzaj¹ siê, ale

blok odebrany nie jest identyczny z na-

dawanym. Sposobem na poprawienie

skutecznoci sprawdzania poprawnoci

transmisji mo¿e byæ zastosowanie d³u¿-

szego rejestru s³u¿¹cego do tworzenia su-

my kontrolnej. Jeli zastosujemy rejestr

16-bitowy (mówimy wiêc o sumowaniu

modulo 65536), znacznie zredukujemy

prawdopodobieñstwo niewykrycia b³êdu.

W konkretnym przypadku zmaleje ono

do wartoci 1:65536. Jednak¿e g³ówn¹

przyczyn¹ niepowodzeñ jest ma³a sku-

Wykrywanie b³êdów

wiat nie jest idealny, o tym dobrze

wiemy. Cz³owiek zawsze d¹¿y³ i d¹¿y do

tego stanu, ale powiedzmy sobie szczerze,

szanse s¹ raczej marne. Dlatego, póki co,

musimy sobie jako radziæ w trudnych sy-

tuacjach. W naszych rozwa¿aniach bêdziemy

siê trzymaæ zagadnieñ transmisji danych.

G³ównym jej wrogiem s¹ szumy kana³u

transmisyjnego i jego zak³ócanie. To w³a-

nie one powoduj¹, ¿e odebrana informacja

niekoniecznie bêdzie zgodna z orygina³em,

co w pewnych sytuacjach mo¿e mieæ bar-

dzo, bardzo przykre skutki. rodkiem na to,

by móc wykryæ ewentualne b³êdy jest - jak

ju¿ doszlimy wczeniej - dodanie pewnego

elementu do przekazywanych danych. In-

formacjê tak¹ nazywamy sum¹ kontroln¹,

chocia¿ sumowanie nie zawsze musi byæ

rozumiane dos³ownie, przynajmniej w zna-

czeniu do jakiego przywyklimy. Mo¿na na-

wet powiedzieæ wiêcej, im bêdzie ono bar-

dziej wymylne, tym wiêksz¹ bêdzie mia³o

skutecznoæ. Na pocz¹tku pozostañmy jed-

nak przy dos³ownym rozumieniu tego s³o-

wa, z zastrze¿eniem, ¿e dotyczy ono liczb

mniejszych od 256. Mówimy o sumie mo-

dulo 256. Wyobramy sobie, ¿e mamy do

czynienia z transmisj¹ przedstawion¹ poni-

¿ej (wszystkie liczby zapisane dziesiêtnie):

wiadomoæ: 6 23 4

wiadomoæ z sum¹ kontroln¹: 6 23 4 33

odebrana wiadomoæ: 6 27 4 33

Bezpieczna wymiana danych w systemach mikroprocesorowych

Elektronika Praktyczna 1/2003

K U R S

tecznoæ samej metody. Mo¿emy powie-

dzieæ, ¿e zastosowany sposób obliczania

sumy kontrolnej, jako zwyk³ej sumy mo-

dulo N, jest za ma³o przypadkowy.

Ka¿dy nadchodz¹cy bajt oddzia³ywuje je-

dynie na jeden bajt rejestru sumuj¹cego

bez wzglêdu na jego ca³kowit¹ d³ugoæ.

Z tego powodu nie jest mo¿liwe wykry-

cie b³êdu jaki wyst¹pi³ w drugim przy-

k³adzie.

Skutecznym rozwi¹zaniem mo¿e byæ

wiêc jedynie zastosowanie bardziej wy-

szukanej metody prowadzenia obliczeñ,

zapewniaj¹cej operowanie na ca³ej sze-

rokoci rejestru sumacyjnego. Widzimy

wiêc dwa aspekty opracowania metody

obliczania sumy kontrolnej. Po pierwsze:

dobranie odpowiedniej d³ugoci rejestru

sumacyjnego, zapewniaj¹cego odpowied-

nio niskie prawdopodobieñstwo b³êdu

(np. rejestr 32-bitowy daje prawdopodo-

bieñstwo b³êdu 1/2 32 ). Po drugie: zasto-

sowanie takiej formu³y obliczeniowej,

która zapewni potencjaln¹ zmianê do-

wolnego bitu w ca³ym rejestrze sumacyj-

nym dla dowolnego bajtu wejciowego.

Metody takie oczywicie opracowano

i bêdziemy o nich dalej mówiæ. Stosowa-

ne do nich okrelenie checksum (suma

kontrolna) ma raczej historyczne znacze-

nie. Dzisiaj czyste sumowanie zosta³o za-

st¹pione operacjami bardziej z³o¿onymi.

11010

-01100

-----

01110 (odejmowanie liczb binarnych)

Odejmujemy od prawej strony: 0-0=0;

1-0=1; 0-1=1 (1 po¿yczamy z s¹siedniej,

lewej kolumny). W nastêpnej kolumnie

mamy 1-1, ale 1 musielimy po¿yczyæ,

mamy wiêc 0-1=1 (1 znowu po¿yczamy

z kolejnej kolumny; w ostatniej mieliby-

my 1-0, ale podobnie jak wczeniej 1 ju¿

po¿yczylimy, wiêc ostatecznie jest 0-

0=0. Sprawdmy na liczbach dziesiêt-

nych. 11010b=26 (przyp. literka b ozna-

cza, ¿e chodzi o liczbê binarn¹),

01100b=12, 01110b=14. 26-12=14. Zgadza

siê, wracamy zatem do obliczania CRC

(kropki u³atwi¹ podpisywanie cyfr w od-

powiednich miejscach):

10101101

----------------

0000011000010111: 1001

1001.......

---.....

==1100.....

1001.....

---...

==1110...

1001...

--..

=1011..

1001..

---

==1011

1001

==10= 2 =

= reszta z dzielenia

Sprawdmy dziesiêtnie: 1559:9=173

reszta 2. Powy¿ej otrzymalimy w wyni-

ku liczbê 10101101b=173 i resztê 2. Ob-

liczenie jest zatem prawid³owe. Zauwa¿-

my, ¿e przek³amanie dowolnego bitu wia-

domoci mo¿e wp³yn¹æ na ostateczn¹

wartoæ ca³ej reszty z dzielenia. Tak nie

by³o w przypadku zwyk³ego dodawania.

Dlatego powy¿sza metoda wykazuje du¿o

wiêksz¹ skutecznoæ wykrywania b³êdów.

1*x 4 +0*x 3 +1*x 2 +1*x 1 +1*x 0

lub krócej:

x 4 +x 2 +x 1 +x 0

Przypuæmy teraz, ¿e chcemy pomno-

¿yæ dwie liczby 1101b i 1011b. Zastosu-

jemy oczywicie mno¿enie wielomianów

(pamiêtamy ze szko³y jak to siê robi):

(x 3 + x 2 + x 0 )*(x 3 + x 1 + x 0 ) = x 6 + x 4 +

x 3 + x 5 + x 3 + x 2 + x 3 + x 1 + x 0 = x 6 + x 5

+ x 4 + 3*x 3 + x 2 + x 1 + x 0

Niepokój mo¿e budziæ sk³adnik 3*x 3 .

Jeli przyjmiemy, ¿e x=2, oka¿e siê, ¿e

sk³adnik ten generuje przeniesienie na

s¹siedni¹, starsz¹ pozycjê. Mamy wiêc:

x 6 + x 5 + x 4 + 3*x 3 + x 2 + x 1 + x 0 = x 6 + x 5

+ 2*x 4 + x 3 + x 2 + x 1 + x 0 = x 6 + 2*x 5 + x 3

+ x 2 + x 1 + x 0 = 2*x 6 + x 3 + x 2 + x 1 + x 0 =

x 7 + x 3 + x 2 + x 1 + x 0

Gdybymy nie znali wartoci x, prze-

niesienie takie nie by³oby mo¿liwe, po-

niewa¿ nie moglibymy stwierdziæ, czy

3*x 3 jest równe x 4 + x 3 , czy te¿ nie. Od-

rzucaj¹c wiêc przeniesienia, wynik po-

wy¿szego mno¿enia by³by równy:

x 6 + x 5 + x 4 + x 3 + x 2 + x 1 + x 0

Tu uwaga: powy¿szy wynik nie bêdzie

oczywicie prawid³owy w klasycznej aryt-

metyce. Rezygnacjê z przeniesieñ wprowa-

dzamy wiadomie, zdaj¹c sobie z tego spra-

wê. Czy takie podejcie mo¿e byæ przydat-

ne do kalkulowania CRC? Popróbujmy.

Arytmetyka binarna bez

przeniesieñ

Przyjmijmy, ¿e dodawanie dwóch liczb

w arytmetyce CRC jest identyczne ze

zwyk³¹ arytmetyk¹ liczb binarnych z wy-

j¹tkiem niestosowania przeniesieñ. Ozna-

cza to, ¿e ka¿da para odpowiednich bitów

okrela tylko bit wyjciowy na tej samej

pozycji, bez wp³ywu na pozosta³e pozy-

cje. Zilustrujmy to przyk³adem dodawania,

dla którego operacje elementarne to:

0+0=0

0+1=1

1+0=1

1+1=0 (brak przeniesienia)

Dodawanie liczby binarnej przebiega

wiêc nastêpuj¹co:

10011011

+11001010

---------

01010001

Podobnie jest dla odejmowania, dla

którego operacje elementarne przedsta-

wiono poni¿ej:

0-0=0

0-1=1 (bez po¿yczki)

1-0=1

1-1=0

Samo odejmowanie wygl¹da nastêpu-

j¹co:

10011011

-11001010

---------

01010001

Zauwa¿my, ¿e elementarne dzia³ania

(dodawanie i odejmowanie) daj¹ ten sam

wynik dla analogicznych par argumentów.

Mo¿na je wiêc zast¹piæ jednym dzia³aniem

odpowiadaj¹cym operacji XOR. Od tej

chwili bêdziemy j¹ oznaczaæ symbolem

Podstawowe zasady obliczeñ CRC

Obecnie stosowane metody w³aciwie

bardziej przypominaj¹ dzielenie ni¿ su-

mowanie, ca³y czas jednak mówimy

o sumowaniu. Ach te przyzwyczajenia!

Ale przecie¿ dzielenie to wielokrotne

odejmowanie, a odejmowanie to dodawa-

nie ze zmienionym znakiem. Tym nieco

pokrêtnym rozumowaniem usprawiedli-

wilimy stosowan¹ nomenklaturê, wiêc

spokojnie mo¿emy przyst¹piæ do dalsze-

go zg³êbiania tematu. Usprawiedliwienie

jest tym bardziej stosowne, ¿e póniej

w praktyce, gdy przyjdzie nam tworzyæ

konkretne programy dla mikroproceso-

rów, bêdziemy korzystaæ z elementarnych

rozkazów dodawania i odejmowania.

Zachowuj¹c ³¹cznoæ z wczeniejszymi

rozwa¿aniami przyjmiemy, ¿e d³ugoæ re-

jestru sumacyjnego bêdzie odpowiada³a

d³ugoci dzielnika w nowej idei. Teraz

transmitowan¹ wiadomoæ traktujemy jako

ogromn¹ (w ogólnym przypadku) liczbê

binarn¹, która bêdzie dzielona przez licz-

bê o ustalonej d³ugoci. Reszta z dzielenia

bêdzie nasz¹ sum¹ kontroln¹. Dalsze po-

stêpowanie jest takie samo, jak wczeniej.

Odbiornik odbiera wiadomoæ, wykonuje

dzielenie, bierze jego resztê traktuj¹c jako

CRC i porównuje z wartoci¹ odebran¹.

Przyk³adowo: wiadomoæ zawiera dwa baj-

ty 6 i 23 (jak w pierwszym przyk³adzie).

W zapisie szesnastkowym bêd¹ to warto-

ci 06h 17h, a rozpisane binarnie dadz¹:

00000110b 00010111b. Przyjmijmy jako

dzielnik jednobajtow¹ liczbê równ¹

00001001b. Tak wiêc CRC otrzymamy ja-

ko resztê z dzielenia liczby

0000011000010111b przez 1001b. Oblicze-

nie wykonamy znan¹ ze szko³y metod¹ pi-

semn¹ z tym, ¿e bêdziemy je wykonywaæ

na liczbach binarnych. Przypomnijmy kró-

tko zasady na poni¿szym przyk³adzie:

Arytmetyka wielomianów

Rezultat uzyskany w poprzednim przy-

k³adzie stanowi znaczny krok do przodu

w porównaniu z pierwszym pomys³em. Dal-

eko nam jednak do doskona³oci. Przyjmij-

my to na razie na wiarê. Komplikujemy

wiêc metodê, w nadziei na osi¹gniêcie ko-

lejnej poprawy. Czeka nas wczeniej jesz-

cze jedna porcja teorii. Ka¿dy, kto prze-

brn¹³ przez szko³ê redni¹, na pewno mia³

do czynienia z wielomianami i zadawa³ so-

bie wtedy pytanie po co uczy siê takich

bzdur. Tym, których dopiero to czeka, ra-

dzê jednak nie spaæ na lekcji. Arytmetyka

wielomianów jest bowiem podstawowym

narzêdziem wykorzystywanym w teorii ko-

dowania nadmiarowego. Omawiane wcze-

niej sk³adniki operacji dzielenia, czyli

dzielna, dzielnik i iloraz reprezentuj¹ do-

datnie liczby ca³kowite. Ka¿da taka liczba

jest ci¹giem bitowym, którego poszczegól-

ne bity stanowi¹ wspó³czynniki wielomia-

nu (binarne). Dla lepszego zrozumienia te-

matu wróæmy do pierwszego przyk³adu.

Mielimy tam dan¹ równ¹ 23=17h=10111b.

Odpowiada jej wiêc wielomian:

XOR mo¿na w zwi¹zku z powy¿szym spo-

strze¿eniem uznaæ za dzia³anie odwracal-

ne. Takie podejcie u³atwia nieco oblicze-

nia, pozwala nam stosowaæ tylko jeden ro-

Elektronika Praktyczna 1/2003

K U R S

dzaj operacji, prowadzi jednak do sytua-

cji, które mog¹ siê wydaæ nawet absurdal-

ne w ujêciu arytmetyki klasycznej. Dla

przyk³adu rozpatrzmy, która z liczb bêdzie

wiêksza 1010b czy 10b. Intuicyjnie czuje-

my, ¿e 1010b, bo ma przecie¿ wiêcej cyfr

znacz¹cych. To samo pytanie postawione

w stosunku do liczb 1010b i 1001b nie da

ju¿ jednoznacznej odpowiedzi, bo okazuje

siê, ¿e jedn¹ z nich mo¿na uzyskaæ zaró-

wno poprzez dodanie, jak i odjêcie pew-

nej liczby:

1001b = 1010b + 0011b i 1001b = 1010b

- 0011b

Wynik nonsensowny w arytmetyce

klasycznej. Popatrzmy teraz jak bêdzie

wygl¹da³o mno¿enie w arytmetyce CRC:

1101

x1011

-----

1101

1101.

1101...

-------

1111111

Pozosta³o do rozpatrzenia jeszcze dzie-

lenie. Tu sprawa jest nieco bardziej skom-

plikowana, poniewa¿ musimy umieæ

okreliæ, czy dzielnik mieci siê we frag-

mencie dzielnej (przypomnijmy sobie dzie-

lenie pisemne) rozpatrywanym w danym

kroku obliczeniowym. To z kolei wi¹¿e siê

z okreleniem, czy dzielnik jest mniejszy

od tego fragmentu. Kilka linijek wy¿ej

mielimy z tym pewne problemy. Przyjmu-

jemy wiêc definicjê: X jest wiêksze lub

równe Y, jeli pozycja najstarszego bitu

równego 1 w liczbie X jest wiêksza lub ta-

ka sama jak najstarszego bitu równego

1 w liczbie Y. A oto przyk³ad dzielenia:

1100001010

--------------

11010110110000: 10011

10011.........

----........

=10011........

10011........

-----...

=====10110...

10011...

---.

==10100.

10011.

---

==1110 reszta z dzielenia

Do rozpatrzenia pozostaje jeszcze

okrelenie dwóch zale¿noci miêdzy licz-

bami. Chodzi mianowicie o okrelenie,

czy liczba A stanowi wielokrotnoæ lub

podwielokrotnoæ liczby B. Jeli A jest

w arytmetyce CRC wielokrotnoci¹ licz-

by B, to da siê j¹ przedstawiæ jako zero

XOR-owane z odpowiednimi przesuniê-

ciami liczby B. Zrozumiemy to, gdy

przeanalizujemy poni¿szy przyk³ad.

Niech A=0111010110b, a B=11b. Zgodnie

z powy¿szym A mo¿emy skonstruowaæ

nastêpuj¹co:

0000000000

Å.......11.

Å....11....

Å...11.....

Å.11.......

-----------

0111010110 = A (znak Å oznacza

operacjê XOR)

Jakakolwiek drobna zmiana liczby A

spowoduje, ¿e nie da siê stworzyæ opi-

sywanej wy¿ej konstrukcji. Jako zadanie

domowe proponujê sprawdziæ, czy

A=0111010111b jest podzielne przez

liczbê B=11b (w rozumieniu arytmetyki

CRC). Przypominam, ¿e odpowied jest

twierdz¹ca, jeli mo¿liwe jest uzyskanie

liczby A jako sumy modulo 2 (XOR)

przesuniêæ liczby B. Ostatecznym spraw-

dzeniem bêdzie wykonanie dzielenia A:B

dla obu powy¿szych przyk³adów ze

szczególnym zwróceniem uwagi na resz-

tê z dzielenia.

Teorii by³o sporo. Trzeba j¹ teraz

jeszcze raz przeanalizowaæ. W nastêpnym

odcinku spróbujemy przybli¿yæ siê do

praktyki.

Jaros³aw Doliñski, AVT

jaroslaw.dolinski@ep.com.pl

Artyku³ powsta³ na podstawie publi-

kacji A painless guide to CRC error de-

tection algorithms, autor Ross N. Wil-

liams. Mo¿na go znaleæ pod adresem

http://www.riccibitti.com/crcguide.htm.

Elektronika Praktyczna 1/2003

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: