algorytm.org

Cykliczna Kontrola Nadmiarowa

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Cykliczna Kontrola Nadmiarowa
Ocena użytkowników:***** / 12
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 28 lipca 2005 17:56

Wszędzie, gdzie przesyłane są dane pojawia się ryzyko wystąpienia błędów, przesyłane informacje mogą dotrzeć zmienione lub zostać zagubione. W takich przypadkach z pomocą przychodzą nam różne sumy kontrolne, najprostszym przykładem jest choćby kontrola parzystości. Istnieje jednak dużo lepsza metoda sprawdzania poprawności danych, jest nią CRC (ang. Cyclic Redundancy Check: Cykliczna Kontrola Nadmiarowa). Jest ona bardzo powszechnie stosowana np: Ethernet, archiwizatory (ZIP, RAR), programy do dzielenia plików itp. Dodatkową zaletą metody CRC jest możliwość zaimplementowania jej w postaci układu składającego się z rejestrów.
Pozwolę sobie pominąć całą teorię (czysta matematyka) i skupić się na implementacji, na końcu strony umieszczam dokument Texas Instruments, w którym teoria została dokładnie wyłożona. Zawiera ona również kilka implementacji w assemblerze.

Warto wspomnieć, że istnieje wiele odmian CRC, różnią się one między sobą postacią wielomianu P, który służy do dzielenia ciągu bitów. Oto kilka z nich:
NazwaWielomian P
CRC-12x12+x11+x3x2+x+1
CRC-16x16+x15+x2+1
CRC-CCITTx16+x12+x5+1
CRC-32x32+x26+x23+ x22+x16+x12+x11+x10+x8+x7+ x5+x4+x2+x+1

Zajmiemy się ostatnią odmianą, która jest stosowana w Ethernecie.

Wielomian P jest zapisywany jako liczba całkowita w następujący sposób:
  • jeśli współczynnik przy x w k-tej potędze jest równy 1, wówczas ustawiamy bit k-ty na 1
  • jeśli współczynnik przy x w k-tej potędze jest równy 0, wówczas ustawiamy bit k-ty na 0
np. jeśli wielomian ma postać x4+x2+x, co można zapisać inaczej: 1*x4+0*x3+1*x2+1*x+0*x0, czyli wielomian P=101102=1616

Kluczową czynnością w wyznaczaniu wartości CRC jest obliczanie dla każdego znaku pewnych wartości. Ponieważ znaki w kodowanej informacji powtarzają się bardzo wiele razy, dobrze jest zapisać te wartości w tablicy, przyspieszając w ten sposób działanie algorytmu. Nie będzie trzeba obliczać wielokrotnie tych samych wartości, zamiast tego odczytamy je z tablicy.

Aby zapisać wartości wszystkich możliwych znaków ASCII potrzebujemy tablicy o długości 256. Dla każdego znaku (czyli od 0 do 255) postępujemy w następujący sposób:
  1. KOD<-kod ASCII kolejnego znaku
  2. Zamieniamy starsze bity z młodszymi, czyli robimy coś w rodzaju lustrzanego odbicia kodu, np. dla kodu 11001001 jego odbicie ma postać 10010011
  3. Uzupełniamy kod 24 zerami, czyli przesuwamy go w lewo o 24
  4. for (int j = 0; j < 8; j++)
  5.    {
  6.    if ((KOD & (1 << 31))!=0)
  7.    KOD = (KOD << 1) XOR P;
  8.    else
  9.    KOD = (KOD << 1);
  10.    }
  11. Ponownie zamieniamy starsze bity z młodszymi
gdzie P jest wielomianem stopnia 32 (patrz tabelka), czyli w zapisie liczbowym P=04C11DB716

Postępując tak iteracyjnie dla wartości KOD od 0 do 255 uzupełnimy całą tablicę.
Wyjaśnienia wymaga instrukcja warunkowa: w punkcie 6. sprawdzamy na ilu bitach zapisana jest liczba KOD (robimy to sprawdzając wartość iloczynu binarnego tej liczby oraz liczby 1032). Jeśli KOD ma 32 bity (wartość iloczynu jest różny od 0) wówczas przesuwamy KOD w lewo o 1 pozycję i wykonujemy operację alternatywy wyłączającej z wielomianem, w przeciwnym wypadku tylko przesuwamy.

Gdy mamy już gotową tablicę, możemy przystąpić do obliczania CRC (tekst wejściowy znajduje się w zmiennej tekst (wskaźnik):
  1. ustaw wartość początkową crc=232-1
  2. for (i=0;i< długość_tekstu; i++)
  3.    crc=(crc>>8) XOR tablica[(crc&255) XOR *tekst++];
  4. podstaw crc=crc XOR (232-1)
Dokument Texas Instruments

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał KnasieckiC/C++
.cpp
.cpp
***** / 14
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 lipca 2012 17:52
Komentarze
photo
0 # Patryk W 2013-03-11 10:51
Witam, mam dwa pytania odnośnie artykułu: dlaczego dla obliczania CRC32 używamy wielomianu od długości 32 bitów? Na wikipedii jest napisane że aby policzyć CRC dla n bitów potrzebujemy wielomian n + 1 stopnia. Natomiast w punkcie drugim obliczania tabeli zamieniamy starsze bity z młodszymi, jakie jest tego uzasadnienie?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Łukasz P 2013-05-28 17:06
1. Z tego co widzę dla CRC32 jest tu podany wielomian o 33 bitach, czyli wszystko się zgadza (CRC 32 ->n=32 -> n+1 = 33, czyli 33 bity i tyle jest), masz bity od x^n do x^0 więc n+1, np. od x^32 do x^0, z tym że x^0 masz zapisane jako 1. masz bity od 0 do 32 numerowane.

2. Niestety nie jestem w stanie odpowiedzieć, w tym algorytmie nie ma to większego znaczenia. Nawet jakby był inny bitorder to zawsze w danej implementacji wykorzystywany jest ten sam, czyli tak samo w niej będzie liczone, chyba że chcemy by dana implementacja mogła współdziałać z innymi, wówczas trzeba się dowiedzieć jaki bitorder jest w jakiej (jak zapisywane są dane) i wówczas ewentualnie zamienić, by bity były przetwarzane w tej samej kolejności.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Filips 2015-02-17 22:02
"gdzie P jest wielomianem stopnia 32 (patrz tabelka), czyli w zapisie liczbowym P=04C11DB716"

A dlaczego najstarszy bit x32 nie jest brany pod uwagę w tym wielomianie? Zawsze się go odrzuca?
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz