[ 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 ]