Cykliczny kod nadmiarowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Cykliczny kod nadmiarowy, inaczej: cykliczna kontrola nadmiarowa (ang.) Cyclic Redundancy Check, CRC – jest to system sum kontrolnych wykorzystywany do wykrywania przypadkowych błędów pojawiających się podczas przesyłania i magazynowania danych binarnych.

Obliczanie[edytuj | edytuj kod]

n-bitowy cykliczny kod nadmiarowy (n-bitowy CRC) definiuje się jako resztę z dzielenia ciągu danych przez (n+1)-bitowy dzielnik CRC, zwany również wielomianem CRC.

Przykład

Załóżmy n = 3.

Ustalmy (n+1)-bitowy dzielnik w postaci liczby 1011.

Weźmy 14-bitowy ciąg danych: 11010011101110.

Algorytm postępowania w celu obliczenia 3-bitowego CRC jest następujący:

  1. dodajemy do ciągu danych 3 wyzerowane bity,
  2. w linii poniżej wpisujemy 4-bitowy dzielnik CRC,
  3. jeżeli mamy 0 nad najstarszą pozycją dzielnika, to przesuwamy dzielnik w prawo o jedną pozycję, aż do napotkania 1,
  4. wykonujemy operację XOR pomiędzy bitami dzielnika i odpowiednimi bitami ciągu danych, uwzględniając dopisane 3 bity
  5. wynik zapisujemy w nowej linii poniżej,
  6. jeżeli liczba bitów danych jest większa lub równa 4, przechodzimy do kroku 2,
  7. 3 najmłodsze bity stanowią szukane CRC, czyli cykliczny kod nadmiarowy:
11010011101110 000 <--- 14 bitów danych + 3 wyzerowane bity
1011               <--- 4-bitowy dzielnik CRC
01100011101110 000 <--- wynik operacji XOR
 1011
00111011101110 000
  1011
00010111101110 000
   1011
00000001101110 000
       1011
00000000110110 000
        1011
00000000011010 000
         1011
00000000001100 000
          1011
00000000000111 000 
           101 1
00000000000010 100
            10 11 
------------------
00000000000000 010 <--- CRC

Po stronie odbiorczej wykonywane jest sprawdzenie poprawności otrzymanych danych, przy wykorzystaniu, utworzonego po stronie nadawczej, kodu nadmiarowego CRC. Jeżeli w przesłanych danych nie ma przekłamań, to po wykonaniu powyższej procedury reszta z dzielenia przez dany dzielnik CRC wynosi 0:

11010011101110 010 <--- przesłany bez przekłamań ciąg 14 bitów danych + CRC
1011               <--- ustalony uprzednio, 4-bitowy dzielnik
01100011101110 010 <--- wynik operacji XOR
 1011
00111011101110 010
  1011
00010111101110 010
   1011
00000001101110 010
       1011
00000000110110 010
        1011
00000000011010 010
         1011
00000000001100 010
          1011
00000000000111 010 
           101 1
00000000000010 110
            10 11 
------------------
00000000000000 000 <--- wynik operacji równy 0 oznacza poprawną transmisję

Zastosowanie[edytuj | edytuj kod]

Metoda ta jest szeroko wykorzystywana do wykrywania błędów przypadkowych, powstających np. podczas transmisji danych cyfrowych przez łącza telekomunikacyjne. Nie nadaje się jednak do ochrony integralności danych w zastosowaniach kryptograficznych, ponieważ CRC nie chroni przed celowym sfałszowaniem, tzn. można tak zmodyfikować przesyłany ciąg bitów, aby dawał on poprawny wynik, mimo kontroli CRC. Jest to jednak algorytm wykrywania błędów lepszy od prostej sumy kontrolnej, gdzie wiele jednoczesnych błędów może nie zmienić jej wartości.

W rzeczywistych realizacjach CRC, wykorzystuje się najczęściej dzielnik CRC o długości 17 lub 33 bity, co daje odpowiednio: 16-bitowy lub 32-bitowy cykliczny kod nadmiarowy. CRC jest szeroko wykorzystywany w technice komputerowej, np. dodawany jest do danych każdego sektora dysku lub pakietu telekomunikacyjnego cyfrowej sieci telekomunikacyjnej, w celu ciągłego sprawdzania integralności danych.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]