[ Pobierz całość w formacie PDF ]

dzielenie, bierze jego reszt� traktuj�c jako bie wtedy pytanie po co uczy si� takich j�co:
CRC i por�wnuje z warto�ci� odebran�. bzdur. Tym, kt�rych dopiero to czeka, ra- 10011011
Przyk�adowo: wiadomo�� zawiera dwa baj- dz� jednak nie spa� na lekcji. Arytmetyka -11001010
ty 6 i 23 (jak w pierwszym przyk�adzie). wielomian�w jest bowiem podstawowym ---------
W zapisie szesnastkowym b�d� to warto�- narz�dziem wykorzystywanym w teorii ko- 01010001
ci 06h 17h, a rozpisane binarnie dadz�: dowania nadmiarowego. Omawiane wcze�- Zauwa�my, �e elementarne dzia�ania
00000110b 00010111b. Przyjmijmy jako niej sk�adniki operacji dzielenia, czyli (dodawanie i odejmowanie) daj� ten sam
dzielnik jednobajtow� liczb� r�wn� dzielna, dzielnik i iloraz reprezentuj� do- wynik dla analogicznych par argument�w.
00001001b. Tak wi�c CRC otrzymamy ja- datnie liczby ca�kowite. Ka�da taka liczba Mo�na je wi�c zast�pi� jednym dzia�aniem
ko reszt� z dzielenia liczby jest ci�giem bitowym, kt�rego poszczeg�l- odpowiadaj�cym operacji XOR. Od tej
0000011000010111b przez 1001b. Oblicze- ne bity stanowi� wsp۳czynniki wielomia- chwili b�dziemy j� oznacza� symbolem �".
nie wykonamy znan� ze szko�y metod� pi- nu (binarne). Dla lepszego zrozumienia te- XOR mo�na w zwi�zku z powy�szym spo-
semn� z tym, �e b�dziemy je wykonywa� matu wr��my do pierwszego przyk�adu. strze�eniem uzna� za dzia�anie odwracal-
na liczbach binarnych. Przypomnijmy kr�- Mieli�my tam dan� r�wn� 23=17h=10111b. ne. Takie podej�cie u�atwia nieco oblicze-
tko zasady na poni�szym przyk�adzie: Odpowiada jej wi�c wielomian: nia, pozwala nam stosowa� tylko jeden ro-
Elektronika Praktyczna 1/2003
90
K U�R S
dzaj operacji, prowadzi jednak do sytua- mieli�my z tym pewne problemy. Przyjmu- 0000000000
cji, kt�re mog� si� wyda� nawet absurdal- jemy wi�c definicj�: X jest wi�ksze lub �".......11.
ne w uj�ciu arytmetyki klasycznej. Dla r�wne Y, je�li pozycja najstarszego bitu �"....11....
przyk�adu rozpatrzmy, kt�ra z liczb b�dzie r�wnego 1 w liczbie X jest wi�ksza lub ta- �"...11.....
wi�ksza 1010b czy 10b. Intuicyjnie czuje- ka sama jak najstarszego bitu r�wnego �".11.......
my, �e 1010b, bo ma przecie� wi�cej cyfr 1 w liczbie Y. A oto przyk�ad dzielenia: -----------
znacz�cych. To samo pytanie postawione 1100001010 0111010110 = A (znak �" oznacza
w stosunku do liczb 1010b i 1001b nie da -------------- operację XOR)
ju� jednoznacznej odpowiedzi, bo okazuje 11010110110000: 10011 Jakakolwiek drobna zmiana liczby A
si�, �e jedn� z nich mo�na uzyska� zar�- 10011......... spowoduje, �e nie da si� stworzy� opi-
wno poprzez dodanie, jak i odj�cie pew- ----........ sywanej wy�ej konstrukcji. Jako zadanie
nej liczby: =10011........ domowe proponuj� sprawdzi�, czy
1001b = 1010b + 0011b i 1001b = 1010b 10011........ A=0111010111b jest podzielne przez
- 0011b -----... liczb� B=11b (w rozumieniu arytmetyki
Wynik nonsensowny w arytmetyce =====10110... CRC). Przypominam, �e odpowied� jest
klasycznej. Popatrzmy teraz jak b�dzie 10011... twierdz�ca, je�li mo�liwe jest uzyskanie
wygl�da�o mno�enie w arytmetyce CRC: ---. liczby A jako sumy modulo 2 (XOR)
1101 ==10100. przesuni�� liczby B. Ostatecznym spraw-
x1011 10011. dzeniem b�dzie wykonanie dzielenia A:B
----- --- dla obu powy�szych przyk�ad�w ze
1101 ==1110 reszta z dzielenia szczeg�lnym zwr�ceniem uwagi na resz-
1101. Do rozpatrzenia pozostaje jeszcze t� z dzielenia.
1101... okre�lenie dw�ch zale�no�ci mi�dzy licz- Teorii by�o sporo. Trzeba j� teraz
------- bami. Chodzi mianowicie o okre�lenie, jeszcze raz przeanalizowa�. W nast�pnym
1111111 czy liczba A stanowi wielokrotno�� lub odcinku spr�bujemy przybli�y� si� do
Pozosta�o do rozpatrzenia jeszcze dzie- podwielokrotno�� liczby B. Je�li A jest praktyki.
lenie. Tu sprawa jest nieco bardziej skom- w arytmetyce CRC wielokrotno�ci� licz- Jaros�aw Doli�ski, AVT
plikowana, poniewa� musimy umie� by B, to da si� j� przedstawi� jako zero jaroslaw.dolinski@ep.com.pl
okre�li�, czy dzielnik mie�ci si� we frag- XOR-owane z odpowiednimi przesuni�-
mencie dzielnej (przypomnijmy sobie dzie- ciami liczby B. Zrozumiemy to, gdy Artyku� powsta� na podstawie publi-
lenie pisemne) rozpatrywanym w danym przeanalizujemy poni�szy przyk�ad. kacji �A painless guide to CRC error de-
kroku obliczeniowym. To z kolei wi��e si� Niech A=0111010110b, a B=11b. Zgodnie tection algorithms�, autor Ross N. Wil-
z okre�leniem, czy dzielnik jest mniejszy z powy�szym A mo�emy skonstruowa� liams. Mo�na go znale�� pod adresem
od tego fragmentu. Kilka linijek wy�ej nast�puj�co: http://www.riccibitti.com/crcguide.htm.
Elektronika Praktyczna 1/2003
91 [ Pobierz całość w formacie PDF ]