Cykliczny kod nadmiarowy: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m robot dodaje: ro:Cyclic redundancy check |
Dodano opis oraz algorytm obliczania CRC, dwie nowe sekcje: obliczanie oraz zastosowanie |
||
Linia 5:
CRC jest resztą z binarnego dzielenia ciągu danych przez relatywnie krótki dzielnik, zwany generatorem lub wielomianem CRC. W praktyce stosuje się najczęściej wielomiany o długości 17 lub 33 bitów, dające odpowiednio wyniki 16- (CRC-16) i 32-bitowe (CRC-32).
== Obliczanie ==
Aby obliczyć n-bitowy kod CRC, bity danych należy traktować jak współczynniki wielomianu, który następnie należy podzielić przez (n+1)-bitowy wielomian CRC. Współczynniki wielomianu będącego resztą z dzielenia to suma kontrolna CRC. W praktyce wykorzystać można następujący algorytm:
#W jednej linii umieść binarny ciąg danych.
#W następnej linii wypisz współczynniki wielomianu CRC, zaczynając od pozycji nad którą znajduje się 1.
#Wykonaj operację [[XOR]] "pod kreską", pozostałe cyfry przepisz.
#Jeżeli stopień wielomianu wynikowego nie jest mniejszy niż stopień wielomianu CRC, przejdź do kroku 2.
#Najmłodsze n bitów stanowi sumę kontrolną.
Poniżej zamieszczono przykładowe obliczenia 3-bitowego kodu CRC.
<pre>
11010011101100 <--- dane
1011 <--- wielomian CRC
01100011101100 <--- wynik
1011 <--- wielomian CRC
00111011101100
1011
00010111101100
1011
00000001101100
1011
00000000110100
1011
00000000011000
1011
00000000001110
1011
--------------
00000000000101 <---reszta z dzielenia (3 bity)
</pre>
== Zastosowanie ==
Metoda ta jest szeroko wykorzystywana do wykrywania błędów przypadkowych, ale nie nadaje się do ochrony integralności w zastosowaniach kryptograficznych. CRC jest relatywnie łatwe do sfałszowania, tj. jest możliwe takie poprawienie ciągu bitów, by dawał on poprawne CRC.
| |||