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

K U R S

CRC doda Ci pewnoci, czêæ 2

Kontynuujemy omawianie metody obliczania CRC (Cyclic Redundancy

Codes). W pierwszej czêci artyku³u zapoznalimy siê z podstawami

arytmetyki stosowanej do tego celu. Bazuj¹c na tej wiedzy, postaramy

siê uchwyciæ istotê metody obliczania CRC.

Po sporej dawce teorii z poprzednie-

go odcinka, Czytelnicy zapewne sprag-

nieni s¹ bardziej praktycznych æwiczeñ.

Wiemy jednak, ¿e nie od razu Kraków

zbudowano. Nie uda nam siê jeszcze

stworzyæ gotowej procedury, któr¹ bêdzie

mo¿na wykorzystaæ we w³asnym progra-

mie, jakkolwiek mam nadziejê, ¿e przy-

k³ady zawarte w tym odcinku znacznie

zbli¿¹ nas do celu.

Przed przyst¹pieniem do kolejnych

æwiczeñ proponujê szybciutko przypo-

mnieæ sobie samodzielnie na czym pole-

ga dzielenie w arytmetyce CRC. W dal-

szych rozwa¿aniach dzielnik ilorazu bê-

dziemy nazywaæ wielomianem generuj¹-

cym lub krótko generatorem . W termino-

logii angielskiej stosuje siê równie¿

okrelenie poly . Jego znaczenie jest bar-

dzo istotne we wszystkich algorytmach

obliczaj¹cych CRC. Jak siê oka¿e, szcze-

gólnie wa¿ny bêdzie stopieñ tego wielo-

mianu. Jest on okrelony przez pozycjê

najstarszego wspó³czynnika o wartoci 1.

Na przyk³ad wielomian 10011 jest stop-

nia 4 (ozn. W=4), nie 5, bo pozycja naj-

starszej jedynki jest równa 4 (liczymy od

zera). Bêdziemy go u¿ywaæ w dalszych

obliczeniach. W praktyce wykorzystuje

siê najczêciej wielomiany stopnia 16

lub 32, co u³atwia implementacjê algo-

rytmów w programach komputerowych.

Maj¹c wybrany generator spróbujmy

jeszcze raz podzieliæ przez niego wielo-

mian reprezentuj¹cy pewn¹ transmitowa-

n¹ wiadomoæ (obliczenia w arytmetyce

CRC). Przed przyst¹pieniem do obliczeñ

zastosujemy jednak ma³y trik polegaj¹cy

na dopisaniu na koñcu wiadomoci ta-

kiej liczby zer, która odpowiada stopnio-

wi generatora, czyli w naszym przypad-

ku 4:

wiadomoæ oryginalna: 1101011011

generator: 10011

wiadomoæ przygotowana do obliczeñ:

11010110110000

==10100.

10011.

-----

==1110 Reszta z dzielenia

(suma kontrolna)

Sam wynik dzia³ania (iloraz) jest dla

naszych celów zupe³nie nieistotny, mo-

¿emy go ca³kowicie zignorowaæ. Najwa¿-

niejsza jest reszta z dzielenia stanowi¹-

ca obliczon¹ sumê kontroln¹. Zazwy-

czaj jest ona zapisywana do przesy-

³anej wiadomoci (tak jak w powy-

¿szym przyk³adzie zrobilimy z zera-

mi) i utworzony w ten sposób zmodyfi-

kowany komunikat jest nastêpnie trans-

mitowany. W omawianym przypadku wy-

sy³ana wiadomoæ mia³aby postaæ:

11010110111110. Na drugim koñcu toru

transmisyjnego odbiornik ma do wyboru

dwie mo¿liwoci:

1. Odseparowaæ wiadomoæ od sumy

kontrolnej. Obliczyæ sumê kontroln¹ po

wczeniejszym dopisaniu W zer na koñ-

cu wiadomoci, a nastêpnie porównaæ

obie sumy.

2. Obliczaæ sumê w biegu (bez dopi-

sywania zer) i sprawdziæ, czy obliczona

suma bêdzie równa zero.

Obie powy¿sze metody s¹ równowa¿-

ne. W dalszej czêci artyku³u skupimy

siê na metodzie 2, gdy¿ z matematycz-

nego punktu widzenia jest nieznacznie

prostsza.

Podczas gdy T mod G jest równe 0, to

(TÅE) mod G = E mod G. Tak wiêc roz-

miar wybranego przez nas generatora bê-

dzie mia³ istotny wp³yw na detekcjê b³ê-

dów. Przyjmijmy na wiarê, ¿e b³êdy bê-

d¹ce wielokrotnoci¹ generatora pozosta-

n¹ nie wykryte. Naszym zadaniem jest

znalezienie takiego wielomianu G, aby

jego stopieñ by³ jak najmniejszy, gwa-

rantuj¹c przy tym odpowiednio wysokie

prawdopodobieñstwo wykrycia b³êdu

w zaszumionym torze transmisyjnym. Po-

patrzmy teraz z jakimi rodzajami b³êdów

mo¿emy siê spotkaæ.

B³êdy pojedyncze

Mówi¹c o b³êdzie pojedynczym ma-

my na myli przyk³adowo

E=10000...0000. Taka klasa b³êdów bê-

dzie na pewno wykryta, gdy co najmniej

dwa bity generatora G bêd¹ równe 1.

Gdybymy wykonywali mno¿enie G po-

legaj¹ce (jak pamiêtamy) na operacji

przesuwania i dodawania pewnej sta³ej

wartoci z ustawionym w tym przypadku

tylko jednym bitem, nie by³o by wiêc

mo¿liwe skonstruowanie takiej liczby,

w której tylko jeden bit by³by ustawio-

ny. Zawsze pozostan¹ dwa ostatnie bity.

Wybór generatora

Wybór odpowiedniego generatora to

temat, który nadawa³by siê bardziej na

pracê doktorsk¹ ni¿ na krótki artyku³

w EP. Rozwi¹zanie pewnych zagadnieñ

wymagaj¹ stosowania nie³atwego aparatu

matematycznego. Nie bêdziemy wiêc

wnikaæ w szczegó³y.

Transmitowan¹ wiadomoæ oznaczy-

my liter¹ T. Za³ó¿my, ¿e T jest wielo-

krotnoci¹ generatora. Zauwa¿my, ¿e:

- W ostatnich bitów wiadomoci T to

reszta z dzielenia T przez generator,

- po drugie - dodawanie jest w arytme-

tyce CRC równowa¿ne odejmowaniu,

tak wiêc dodaj¹c resztê z dzielenia od-

k³adamy tê wartoæ do nastêpnego

mno¿enia. Jeli teraz przesy³ana wia-

domoæ ulegnie przek³amaniu w od-

biorniku otrzymamy TÅE, gdzie E jest

wektorem b³êdu. Zwróæmy uwagê na

to, ¿e sumowanie jest prowadzone

w arytmetyce CRC (odpowiada np.

operacji XOR).

Teraz odebrana informacja poddawa-

na jest operacji dzielenia T

Wykonajmy teraz dzielenie (kropki

u³atwiaj¹ podpisywanie cyfr):

B³êdy podwójne

Dla wykrycia wszystkich b³êdów ty-

pu 100...000100...000 (E posiada dwa bi-

ty o wartoci 1) wybieramy G, które nie

bêdzie wielokrotnoci¹ 11, 101, 1001,

10001, 1000001, itd. Przyjmijmy to na

wiarê.

1100001010

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

11010110110000:10011

10011.........

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

=10011........

10011........

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

=====10110...

10011...

-----.

E przez G.

B³êdy z nieparzyst¹ liczb¹

bitów

Wykrycie takich b³êdów jest mo¿li-

we przez wybranie G z parzyst¹ liczbê

bitów. Zauwa¿my, ¿e mno¿enie CRC jest

Bezpieczna wymiana danych w systemach mikroprocesorowych

Elektronika Praktyczna 2/2003

K U R S

Rys. 1

niczym innym, jak wielokrotnym XOR-

owaniem pewnej sta³ej z odpowiednimi

przesuniêciami. Pamiêtamy równie¿, ¿e

XOR-owanie to w gruncie rzeczy zwyk³e

prze³¹czanie bitów. Bior¹c to pod uwa-

gê, jeli bêdziemy XOR-owaæ liczbê z pa-

rzyst¹ liczb¹ jedynek zawsze w wyniku

obliczeñ zostanie nieparzysta liczba je-

dynek. Na przyk³ad wemy E=111 i spró-

bujmy prze³¹czyæ wszystkie trzy bity

przez powtarzanie XOR-owania z liczb¹

11, przesuwaj¹c j¹ po ka¿dym kroku.

Otrzymamy E=E XOR 011 (w pierwszym

kroku) i E=E XOR 110 (w drugim kro-

ku). Jak widaæ sztuka siê nie uda³a, jed-

na jedynka pozosta³a niezmieniona.

B³êdy typu burst

B³¹d burst to ci¹g jedynek poprze-

dzony i zakoñczony ci¹giem zer:

E=000...000111...11110000...000. Powy-

¿sz¹ zale¿noæ mo¿na zapisaæ inaczej:

E=(10000...00)(1111111...111), gdzie wy-

stêpuje z zer w lewej czêci i n jedynek

w prawej. Do wykrycia b³êdu tego typu

wystarczy ustawiæ najm³odszy bit G na

1. Lewa czêæ E nie mo¿e byæ czynni-

kiem G. Dopóty, dopóki G bêdzie d³u¿-

sze ni¿ prawa czêæ E, b³¹d bêdzie wy-

krywany. Wiêcej informacji na ten temat

mo¿na znaleæ w [1].

Bior¹c pod uwagê powy¿sze zale¿-

noci wybrano kilka generatorów, które

s¹ powszechnie stosowane w praktyce:

16-bitowe:

(16,12,5,0) - standard X25

(16,15,2,0) - tzw. CRC-16

32-bitowe:

(32,26,23,22,16,12,11,10,8,7,5,4,2,1,0)

- Ethernet

Rys. 2

rozpatrywaæ transmitowan¹ wiadomoæ

jako ci¹g bajtów. Najstarszy bit (MSB -

Most Significant Bit ) znajduje siê na po-

zycji 7 ka¿dego bajtu. Gdybymy potrak-

towali wiadomoæ jako ci¹g bitów, to

najstarszy bit wiadomoci odpowiada³by

pierwszemu bitowi ró¿nemu od zera

w pierwszym bajcie, licz¹c od najstarszej

pozycji. Teraz ju¿ mo¿emy naszkicowaæ

algorytm dzielenia CRC. Dla ustalenia

uwagi przyjmiemy, ¿e W=4, a jako gene-

rator wybierzemy G=10111. Do wykona-

nia dzielenia bêdziemy potrzebowaæ 4-

bitowego rejestru ( rys. 1 ). Pamiêtamy

oczywicie, ¿e wiadomoæ koñczy W ze-

rowych bitów.

Algorytm bêdzie wiêc nastêpuj¹cy

(zapiszemy go w postaci pseudoprogra-

mu):

Wyzeruj wszystkie bity rejestru.

Dopisz W zerowych bitów do

przesy³anej wiadomoci.

while(jest wiêcej bitów do pobrania)

{

Przesuñ rejestr w lewo o jedn¹

pozycjê, wczytuj¹c nastêpny bit

wiadomoci na pozycjê 0.

If(wychodz¹cy bit ma wartoæ 1)

{

Proponujê teraz samodzielne przeæwi-

czyæ algorytm na innym przyk³adzie.

Mo¿na przy tym zmieniæ generator

i wartoæ W, od której algorytm nie za-

le¿y.

Implementacja oparta na

tablicy

Przedstawiony powy¿ej algorytm

SIMPLE by³ doæ dobrym przyk³adem

bezporedniego prze³o¿enia teorii

w praktykê. Wykorzystuj¹c go mo¿na ju¿

bez trudu napisaæ program z przeznacze-

niem na konkretny procesor. Bêdzie on

oczywicie dzia³a³, ale nie zadowoli chy-

ba jego u¿ytkownika. Jego szybkoæ dzia-

³ania nie bêdzie najwiêksza - zauwa¿my,

¿e obróbka pojedynczego bitu wymaga

wykonania jednego obrotu pêtli. Ale

pierwsze koty za p³oty, dowiadczenie

ju¿ jakie mamy.

Pomylmy wiêc co zrobiæ, ¿eby

zwiêkszyæ wydajnoæ. Pierwszym pomys-

³em jaki sam siê nasuwa bêdzie przej-

cie z obróbki bitowej na - nazwijmy to

na razie - wiêcej ni¿ bitow¹. Naturalny-

mi mo¿liwociami s¹ tu: pó³bajt ( nibble )

(4 bity), bajt (8 bitów), s³owo (16 bi-

tów), d³ugie s³owo (32 bity) lub wiêcej

(jeli bêdziemy potrafili obs³u¿yæ). My

wybierzemy wariant 8-bitowy. Dla niego

istnieje ju¿ wiele opracowanych algoryt-

mów, ponadto bêdzie siê wietnie nada-

wa³ dla ma³ych mikroprocesorów (mik-

rokontrolerów). Na u¿ytek nastêpnych

rozwa¿añ zmienimy te¿ doæ drastycznie

stopieñ generatora z W=4, na W=32. Pa-

miêtamy, ¿e generator taki bêdzie mia³

d³ugoæ 33 bity (pierwszy bit zawsze

równy 1 i 32 bity aktywne). Wyd³u¿y

siê te¿ do 32 bitów rejestr stosowany do

obliczeñ ( rys. 3 ).

Nazwijmy teraz bity najstarszego baj-

tu (numer 3) naszego rejestru. Bêd¹ to

t7 (MSB) t6...t0 (LSB). Przyjmijmy te¿,

¿e 8 najstarszych aktywnych bitów ge-

neratora bêdzie mia³o oznaczenia: g7

Bezporednia implementacja

CRC

Ufff, podk³ad teoretyczny mamy ju¿

za sob¹, mo¿emy powoli przechodziæ do

praktyki. Zajmiemy siê teraz konkretny-

mi algorytmami obliczania CRC. Jak wy-

nika z konkluzji poprzedniego podroz-

dzia³u, CRC nie jest jednoznacznie wyli-

czan¹ sum¹ kontroln¹. W zale¿noci od

wymaganego stopnia ochrony danych,

stosowanego medium transmisyjnego,

mo¿liwoci obliczeniowych urz¹dzeñ na-

dawczo-odbiorczych stosuje siê ró¿ne al-

gorytmy. Na pocz¹tek zaczniemy od chy-

ba najprostszego z najprostszych, bez wy-

korzystywania ¿adnych trików, dzia³aj¹-

cego jednak bardzo wolno. W dalszej

czêci artyku³u bêdziemy go stopniowo

komplikowaæ i usprawniaæ. Pamiêtamy

o tym, ¿e obliczenia CRC opieraj¹ siê na

operacji dzielenia. Niektóre procesory

uwzglêdniaj¹ w swojej licie rozkazów to

dzia³anie. Nie bêdzie ono jednak wyko-

rzystywane, gdy¿ jak pamiêtamy nasze

dzielenie jest oparte nie na arytmetyce

klasycznej, lecz na arytmetyce CRC. Po-

nadto dzielna, któr¹ jest transmitowany

blok, mo¿e osi¹gaæ bardzo du¿e rozmia-

ry. W kolejnych przyk³adach bêdziemy

Bitwychodz¹cy_Rejestr=

Bitwychodz¹cy_Rejestr

XOR

Generator

}

gdzie: wyra¿enie Bitwychodz¹cy_Rejestr

to s³owo, w którym najstarszy bit ma

wartoæ bitu wychodz¹cego z rejestru,

a za nim nastêpuj¹ bity reprezentuj¹ce

wartoæ rejestru.

Po zakoñczeniu pêtli, rejestr zawiera

resztê z dzielenia. Uwaga praktyczna:

warunek w instrukcji IF mo¿na spraw-

dzaæ testuj¹c najstarszy bit rejestru przed

wykonaniem przesuniêcia. Powy¿szy al-

gorytm bêdziemy nazywaæ SIMPLE.

Graficzn¹ ilustracjê wykonania tego

algorytmu przedstawiono na rys. 2 . Da-

ne odpowiadaj¹ przyk³adowi przedsta-

wionemu na pocz¹tku artyku³u. Mamy

wiêc: T=11010110110000, G=10011, czy-

li W=4.

Rys. 3

Elektronika Praktyczna 2/2003

K U R S

g6...g0. Tak jak by³o w algorytmie SIMP-

LE, bit t7 (nazwijmy go bitem szczyto-

wym) bêdzie okrela³, czy generator ma

byæ XOR-owany z rejestrem w nastêpnej

iteracji. Nast¹pi to, gdy bit ten bêdzie

mia³ wartoæ 1. Mo¿na wiêc zapisaæ, ¿e

najstarszy bit w nastêpnej iteracji bêdzie

mia³ wartoæ: t6

rejestru sta³¹ wartoci¹ z ró¿nymi prze-

suniêciami. Na przyk³ad:

0100010 Rejestr

Å 0000110

Å 0001100

Å 0110000

-------

0011000

Wynik powy¿szego dzia³ania mo¿emy

uzyskaæ na drodze wielokrotnego XOR-

owania poszczególnych sk³adników z re-

jestrem, lub jednokrotnego wykonania tej

operacji z wartoci¹ sta³¹ równ¹ sumie

(XOR) poszczególnych sk³adników. £¹-

cz¹c ca³¹ zdobyt¹ powy¿ej wiedzê w ca-

³oæ mo¿emy napisaæ szkic algorytmu:

While(s¹ dane w ci¹gu wejciowym)

{

o W=32 jaki stosowalimy w przyk³a-

dzie).

3. XOR-uj dane z tablicy z rejestrem.

4. Id do pkt. 1, jeli nie wykorzys-

ta³e wszystkich bajtów wiadomoci.

Teraz ju¿ mo¿na zrobiæ pierwsz¹

przymiarkê do napisania programu w ja-

kim konkretnym jêzyku. Bêdzie nim

oczywicie C. Fragment takiego progra-

mu przedstawiono poni¿ej:

unsigned long r;

unsigned char t;

...

r=0;

while(len--)

{

Zauwa¿my, ¿e do obliczania nowej

wartoci bitu szczytowego (MSB) drugiej

iteracji, potrzebne s¹ dwa najstarsze bity

w najstarszym bajcie rejestru. Dla trze-

ciej iteracji bêd¹ to trzy bity (t7, t6 i t5),

itd. Ogólnie dla k-tej iteracji potrzebnych

jest k bitów rejestru. Wykorzystamy to

póniej. Rozwa¿my przypadek, w którym

bêdziemy wykorzystywaæ 8 bitów rejest-

ru do obliczania bitu szczytowego dla

nastêpnych 8 iteracji. Za³ó¿my, ¿e bê-

dziemy prowadziæ 8 nastêpnych iteracji

wykorzystuj¹c obliczone wartoci (które

mo¿emy zapisywaæ w pojedynczym rejes-

trze i obracaæ w celu wy³uskiwania ka¿-

dego bitu). Znowu musimy zauwa¿yæ

trzy sytuacje:

- Najstarszy bajt rejestru nie ma teraz

znaczenia. Nie jest istotne ile razy

i z jakim przesuniêciem generator jest

XOR-owany dla 8 bitów szczytowych,

wszystkie bêd¹ przesuniête na ze-

wn¹trz podczas nastêpnych 8 iteracji.

- Pozosta³e bity bêd¹ przesuniête o jed-

n¹ pozycjê w lewo, a bajty z prawej

strony bêd¹ przesuniête na nastêpn¹

pozycjê.

- Na czas operacji, rejestr bêdzie podle-

ga³ serii operacji XOR-owania z bitami

steruj¹cymi obliczonymi wczeniej.

Teraz rozpatrzmy efekt XOR-owania

t=(unsigned char)((r>>24) & 0xff);

r=(r<<8) | *pMsg++;

r^=tab[t];

Zapamiêtaj tymczasowo najstarszy

bajt rejestru (bêdzie to bajt

steruj¹cy)

Sumuj ca³y generator z ró¿nymi

przesuniêciami XOR-uj¹c z rejestrem

odpowiednio z rejestrem steruj¹cym

Przesuñ rejestr w lewo o jeden

bajt, wczytuj¹c na najm³odsz¹

pozycjê kolejny bajt wiadomoci

XOR-uj zsumowany generator

z rejestrem

}

Zmienna len okrela liczbê bajtów

wiadomoci, *Msg jest wskanikiem na

bajt wiadomoci, który bêdzie pobierany

do obliczeñ, r to nasz rejestr, t jest

zmienn¹ tymczasow¹, a tab obliczon¹

wczeniej tablic¹.

Moc jêzyka C polega na bardzo

zwiêz³ym zapisywaniu wyra¿eñ (co nie

zawsze jest wystarczaj¹co zrozumia³e

i przez co jêzyk ten nie cieszy siê popu-

larnoci¹ wród pocz¹tkuj¹cych progra-

mistów), mo¿na wiêc nasze obliczenia

uprociæ do jednej linijki:

r=0;

while(len--)

r=((r<<8) | *pMsg++)

^ tab[(unsigned char)((r>>24)

& 0xff)];

Zastosowany tu algorytm bêdziemy

nazywaæ TABLICOWYM. Charakteryzuje

siê on du¿¹ wydajnoci¹, nie wymaga

wielkich mocy obliczeniowych proceso-

ra. Jego najwiêksz¹ wad¹ jest zajmowa-

nie pamiêci przez tablice i to, ¿e dla

postronnego obserwatora mo¿e byæ zu-

pe³nie nieczytelny. Trudno znaleæ

w nim ca³¹, nie ma³¹ jak siê moglimy

przekonaæ teoriê. Ale to jeszcze nie ko-

niec. Wiêcej w nastêpnym odcinku.

Jaros³aw Doliñski, AVT

jaroslaw.dolinski@ep.com.pl

}

Jak na razie nie specjalnie widaæ, ¿e-

by algorytm ten by³ w czym lepszy ni¿

SIMPLE. Jeli jednak g³êboko go prze-

mylimy, dojdziemy do wniosku, ¿e

wiêkszoæ obliczeñ mo¿e byæ wykonana

wczeniej, a wyniki mog¹ byæ zapisane

w odpowiedniej tablicy. Jeli wykorzys-

tamy to b³yskotliwe spostrze¿enie, algo-

rytm mo¿na uprociæ do postaci:

While(s¹ dane w ci¹gu wejciowym)

{

Top = bajt szczytowy rejestru

Rejestr = (Rejestr << 8) |

nastêpny_bajt_wiadomoci

Rejestr = Rejestr XOR Tablica[Top]

}

Nie twierdzê, by powy¿sze rozwa¿a-

nia by³y proste. S¹ jednak wa¿ne, ich

zrozumienie pozwala bowiem poj¹æ ideê

konstruowania tablicowych algorytmów

obliczania CRC. Graficzn¹ interpretacjê

dzia³ania algorytmu przedstawiono na

rys. 4 . Mo¿emy jeszcze raz skomentowaæ

ten rysunek opisem s³ownym:

1. Przesuñ rejestr o jeden bajt w le-

wo, dopisuj¹c na najm³odszej pozycji ko-

lejny bajt wiadomoci

2. Wykorzystaj wychodz¹cy z rejest-

ru bajt do indeksowania tablicy (256

wartoci 32-bitowych (dla generatora

Rys. 4

[1] Artyku³ powsta³ na podstawie publi-

kacji A painless guide to CRC error

detection algorithms, Ross N. Wil-

liams. Mo¿na j¹ znaleæ pod adresem

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

[2] Tanenbaum, A.S., Computer Net-

works, Prentice Hall, 1981, ISBN: 0-

13-164699-0.

Elektronika Praktyczna 2/2003

t7 * g7, co wyjania

poni¿sza interpretacja pisemna:

t6 t5 t4 t3 t2 t1 t0 ??

Å t7 * (g7 g6 g5 g4 g3 g2 g1 g0)

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: