- Wprowadzenie do obliczeń CRC
- darmowe procedury obliczeń CRC do pobrania
Wprowadzenie do obliczeń CRC
za każdym razem, gdy dane cyfrowe są przechowywane lub powiązane, może dojść do uszkodzenia danych. Od początku informatyki ludzie zastanawiali się nad sposobami radzenia sobie z tego typu problemami., W przypadku danych szeregowych wymyślili rozwiązanie, aby dołączyć bit parzystości do każdego wysyłanego bajtu. Ten prosty mechanizm wykrywania działa, jeśli Nieparzysta liczba bitów w bajcie ulegnie zmianie, ale parzysta liczba fałszywych bitów w jednym bajcie nie zostanie wykryta przez sprawdzanie parzystości. Aby przezwyciężyć ten problem, ludzie poszukiwali matematycznych mechanizmów dźwiękowych do wykrywania wielu fałszywych bitów. Wynikało to z obliczeń CRC lub cyklicznej kontroli nadmiarowości. Obecnie obliczenia CRC są wykorzystywane we wszystkich rodzajach komunikacji. Wszystkie pakiety wysyłane przez połączenie sieciowe są sprawdzane za pomocą CRC., Również każdy blok danych na dysku twardym ma dołączoną wartość CRC. Współczesny komputer świat nie może obejść się bez tych obliczeń CRC. Zobaczmy więc, dlaczego są one tak szeroko stosowane. Odpowiedź jest prosta, są potężne, wykrywają wiele rodzajów błędów i są niezwykle szybkie do obliczenia, zwłaszcza gdy używane są dedykowane układy sprzętowe.
można by pomyśleć, że użycie sumy kontrolnej może zastąpić odpowiednie obliczenia CRC. Z pewnością łatwiej jest obliczyć sumę kontrolną, ale sumy kontrolne nie znajdują wszystkich błędów. Weźmy przykładowy ciąg znaków i obliczmy sumę kontrolną jednego bajtu., Przykładowym łańcuchem znaków jest „Lammert”, który konwertuje wartości ASCII . Sumę kontrolną jednego bajtu tej tablicy można obliczyć dodając wszystkie wartości, a następnie dzieląc ją przez 256 i zachowując resztę. Uzyskana suma kontrolna wynosi 210. Możesz użyć kalkulatora powyżej, aby sprawdzić ten wynik.
w tym przykładzie użyliśmy sumy kontrolnej o długości jednego bajtu, która daje nam 256 różnych wartości. Użycie dwubajtowej sumy kontrolnej spowoduje uzyskanie 65 536 możliwych różnych wartości sumy kontrolnej, a gdy używana jest wartość czterobajtowa, istnieje ponad cztery miliardy możliwych wartości., Możemy wywnioskować, że z czterobajtową sumą kontrolną szansa, że przypadkowo nie wykryjemy błędu jest mniejsza niż 1 do 4 miliardów. Wydaje się całkiem dobre, ale to tylko teoria. W praktyce bity nie zmieniają się w sposób czysto przypadkowy podczas komunikacji. Często zawodzą w wybuchach lub z powodu skoków elektrycznych. Załóżmy, że w naszej przykładowej tablicy ustawiony jest najniższy znaczący bit znaku 'L', a najniższy znaczący bit znaku 'a' jest tracony podczas komunikacji. Odbiorca zobaczy tablicę przedstawiającą łańcuch ” M 'mmert”., Suma kontrolna dla tego nowego ciągu nadal wynosi 210, ale wynik jest oczywiście błędny, dopiero po zmianie dwóch bitów. Nawet gdybyśmy użyli sumy kontrolnej o długości czterech bajtów, nie wykrylibyśmy tego błędu transmisji. Tak więc obliczanie sumy kontrolnej może być prostą metodą wykrywania błędów, ale nie daje znacznie większej ochrony niż bit parzystości, niezależnie od długości sumy kontrolnej.
idea obliczania wartości kontrolnej jest prosta. Użyj funkcji F (bval,cval), która wprowadza jeden bajt danych i wartość kontrolną i wyprowadza przeliczoną wartość kontrolną., W rzeczywistości obliczenia sumy kontrolnej, jak opisano powyżej, można zdefiniować w ten sposób. Nasz przykład sumy kontrolnej jednego bajtu mógł być obliczony za pomocą następującej funkcji (w języku C), którą wywołujemy wielokrotnie dla każdego bajtu w ciągu wejściowym. Wartość początkowa dla cval wynosi 0.
int F_chk_8( int bval, int cval ) { retun ( bval + cval ) % 256;}
ideą obliczeń CRC jest spojrzenie na dane jako jedną dużą liczbę binarną. Liczba ta jest dzielona przez pewną wartość, a pozostała część obliczeń nazywa się CRC., Dzielenie w obliczeniach CRC na początku wydaje się kosztować dużo mocy obliczeniowej, ale można to wykonać bardzo szybko, jeśli użyjemy metody podobnej do tej, której nauczyliśmy się w szkole. Jako przykład obliczymy resztę dla znaku ” m ” – czyli 1101101 w notacji binarnej-dzieląc ją przez 19 lub 10011. 19 jest liczbą nieparzystą. Jest to konieczne, co zobaczymy dalej. Proszę odnieść się do podręczników szkolnych, ponieważ metoda obliczania binarnego nie różni się zbytnio od metody dziesiętnej, której nauczyłeś się w młodości. To może wyglądać trochę dziwnie., Również notacje różnią się między krajami, ale metoda jest podobna.
1 0 1 = 5 -------------1 0 0 1 1 / 1 1 0 1 1 0 1 1 0 0 1 1 | | --------- | | 1 0 0 0 0 | 0 0 0 0 0 | --------- | 1 0 0 0 0 1 1 0 0 1 1 --------- 1 1 1 0 = 14 = remainder
dzięki obliczeniom dziesiętnym możesz szybko sprawdzić, czy 109 podzielone przez 19 daje iloraz 5, a 14 jako resztę. Ale widzimy również w schemacie, że każdy dodatkowy bit do sprawdzenia kosztuje tylko jedno porównanie binarne, a w 50% przypadków jedno odejmowanie binarne., Możesz łatwo zwiększyć liczbę bitów ciągu danych testowych—na przykład do 56 bitów, jeśli użyjemy naszej przykładowej wartości „Lammert” —a wynik można obliczyć za pomocą 56 porównań binarnych i średnio 28 odejmowań binarnych. Może to być zaimplementowane w sprzęcie bezpośrednio z udziałem tylko niewielu tranzystorów. Również algorytmy programowe mogą być bardzo wydajne.
dla obliczeń CRC nie stosuje się normalnego odejmowania, ale wszystkie obliczenia są wykonywane modulo 2. W takiej sytuacji ignoruje się bity nośne i w efekcie odejmowanie będzie równe operacji exclusive or., Wygląda to dziwnie, otrzymana reszta ma inną wartość, ale z algebraicznego punktu widzenia funkcjonalność jest równa. Dyskusja na ten temat wymaga znajomości algebraicznej teorii pola na poziomie uniwersyteckim i myślę, że większość czytelników nie jest tym zainteresowana. Proszę spojrzeć na końcu tego dokumentu dla książek, które omawiają to szczegółowo.
teraz mamy metodę obliczania CRC, która jest implementowana zarówno w sprzęcie, jak i w oprogramowaniu, a także ma bardziej losowe odczucie niż obliczanie zwykłej sumy kontrolnej. Ale jak to będzie działać w praktyce, gdy jeden lub więcej bitów jest źle?, Jeśli w naszym przykładzie wybierzemy dzielnik—19 – jako liczbę nieparzystą, nie potrzebujesz matematyki na wysokim poziomie, aby zobaczyć, że każdy pojedynczy błąd bitowy zostanie wykryty. Dzieje się tak, ponieważ każdy pojedynczy błąd bitowy pozwoli na zmianę dywidendy z mocą 2. Jeśli na przykład bit n zmieni się z 0 Na 1, wartość dywidendy wzrośnie z 2n. jeśli z drugiej strony bit n zmieni się z 1 na 0, wartość dywidendy zmniejszy się z 2N. ponieważ nie można podzielić żadnej potęgi dwójki przez nieparzystą liczbę, reszta obliczeń CRC ulegnie zmianie I błąd nie pozostanie niezauważony.,
druga sytuacja, którą chcemy wykryć, to zmiana dwóch pojedynczych bitów w danych. Wymaga to pewnej matematyki, którą można przeczytać w książce Tanenbauma wymienionej poniżej. Musisz bardzo starannie wybrać dzielnik, aby mieć pewność, że niezależnie od odległości między dwoma niewłaściwymi bitami zawsze je wykryjesz. Wiadomo, że powszechnie stosowane wartości 0x8005 i 0x1021 z obliczeń CRC16 i CRC-CCITT sprawdzają się w tej kwestii bardzo dobrze., Należy pamiętać, że inne wartości mogą, ale nie mogą, i nie można łatwo obliczyć, która wartość dzielnika jest odpowiednia do wykrywania dwóch błędów bitowych, a która nie. polegaj na rozległych badaniach matematycznych na ten temat, przeprowadzonych kilka dekad temu przez wysoko wykwalifikowanych matematyków i wykorzystaj wartości uzyskane przez te osoby.
Ponadto, dzięki naszym obliczeniom CRC chcemy wykryć wszystkie błędy, w których zmienia się Nieparzysta liczba bitów. Można to osiągnąć za pomocą dzielnika o ustawionej parzystej liczbie bitów. Za pomocą matematyki modulo 2 można pokazać, że wykryto wszystkie Błędy o nieparzystej liczbie bitów., Jak już wcześniej powiedziałem, w matematyce modulo 2 funkcja odejmowania jest zastępowana przez wyłączną or. Możliwe są cztery operacje XOR.
0 XOR 0 => 0 even => even0 XOR 1 => 1 odd => odd1 XOR 0 => 1 odd => odd1 XOR 1 => 0 even => even
widzimy, że dla wszystkich kombinacji wartości bitowych dziwność wyrażenia pozostaje taka sama. Przy wyborze dzielnika o ustalonej parzystej liczbie bitów, dziwność reszty jest równa dziwności dywidendy. W związku z tym, jeśli zmienia się dziwność dywidendy, ponieważ zmienia się Nieparzysta liczba bitów, reszta również się zmieni., Tak więc wszystkie błędy, które zmieniają nieparzystą liczbę bitów, zostaną wykryte przez obliczenia CRC, które są wykonywane z takim dzielnikiem. Być może zauważyłeś, że powszechnie używane wartości dzielników 0x8005 i 0x1021 rzeczywiście mają nieparzystą liczbę bitów, a nie parzystą, jak podano tutaj. Dzieje się tak dlatego, że wewnątrz algorytmu znajduje się „Ukryty” dodatkowy bit 216, który sprawia, że faktycznie używana wartość dzielnika 0x18005 i 0x11021 wewnątrz algorytmu.,
chcemy wykryć wszystkie błędy serii za pomocą naszych obliczeń CRC o maksymalnej długości do wykrycia, a wszystkie dłuższe błędy serii zostaną wykryte z dużym prawdopodobieństwem. Błąd typu burst jest dość powszechny w komunikacji. Jest to rodzaj błędu, który występuje z powodu wyładowań atmosferycznych, przełączania przekaźników itp. gdzie w małym okresie wszystkie bity są ustawione na jeden., Aby to naprawdę zrozumieć, musisz również mieć pewną wiedzę o algebrze modulo 2, więc przyjmij, że z dzielnikiem 16 bitowym będziesz w stanie wykryć wszystkie wybuchy o maksymalnej długości 16 bitów, a wszystkie dłuższe wybuchy z co najmniej 99,997% pewnością.
w czysto matematycznym podejściu obliczenia CRC zapisywane są jako obliczenia wielomianowe. Wartość dzielnika najczęściej nie jest opisywana jako liczba binarna, ale wielomian pewnego rzędu. W normalnym życiu niektóre wielomiany są używane częściej niż inne., Trzy używane w obliczeniach on-line CRC na tej stronie to 16-bitowe wide CRC16 i CRC-CCITT oraz 32-bitowe wide CRC32. Ten ostatni jest obecnie prawdopodobnie najczęściej używany, ponieważ m.in. jest generatorem CRC do weryfikacji i walidacji całego ruchu sieciowego.
dla wszystkich trzech typów obliczeń CRC mam dostępną bibliotekę wolnego oprogramowania. Program testowy może być używany bezpośrednio do testowania plików lub ciągów. Możesz również spojrzeć na kody źródłowe i zintegrować te procedury CRC w swoim własnym programie., Należy pamiętać o wartościach inicjalizacji obliczeń CRC i ewentualnych niezbędnych przetwarzaniach końcowych, takich jak przerzucanie bitów. Jeśli tego nie zrobisz, możesz uzyskać inne wyniki niż inne implementacje CRC. Wszystko to pre i post-processing odbywa się w programie przykładowym, więc nie powinno być trudne, aby Twoja własna implementacja działała. Często stosowanym testem jest obliczanie wartości CRC Dla ciągu ASCII „123456789”., Jeśli wynik Twojej procedury odpowiada wynikowi programu testowego lub wynikowi na tej stronie internetowej, twoja implementacja działa i jest kompatybilna z większością innych implementacji.
tylko jako odniesienie do funkcji wielomianowych dla najczęstszych obliczeń CRC. Proszę pamiętać, że termin najwyższego rzędu wielomianu (x16 lub x32) nie jest obecny w reprezentacji liczb binarnych, ale implikowany przez sam algorytm.,
| Literatura | ||
| 2002 | Sieci Komputerowe, opisujące wspólne systemy sieciowe oraz teorię i algorytmy stojące za ich implementacją. | Andrew S. Tanenbaum |
| various | Sztuka programowania komputerowego jest głównym punktem odniesienia dla algorytmów semi-numerycznych. Obliczenia wielomianowe są szczegółowo opisane. Pewien poziom matematyki jest niezbędny, aby w pełni go zrozumieć. | Donald E. Knuth |
| – | DNP 3.,0, lub distributed network protocol to protokół komunikacyjny przeznaczony do użytku między komputerami podstacji, zdalnymi terminalami rtus, inteligentnymi urządzeniami elektronicznymi IED i stacjami nadrzędnymi dla przemysłu elektroenergetycznego. Obecnie jest również stosowany w znanych branżach, takich jak oczyszczanie ścieków, transport oraz przemysł naftowy i gazowy. | grupa użytkowników DNP |
Dodaj komentarz