Cykliczny kod nadmiarowy: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m →Zastosowanie: drobne redakcyjne |
→Obliczanie: Poprawiono błąd merytoryczny. Źródła: Angielska Wikipedia, Wykłady z przedmiotu Podstawy Telekomunikacji (EiTI PW) |
||
Linia 3:
== Obliczanie ==
Cykliczny kod nadmiarowy, krótko: 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). Aby obliczyć n-bitowy 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. Dopisz na koniec ciągu n zer, gdzie n jest stopniem wielomianu CRC.
#W następnej linii wypisz współczynniki wielomianu CRC, zaczynając od pozycji nad którą znajduje się 1.
#Wykonaj operację [[Alternatywa wykluczająca|XOR]] "pod kreską", pozostałe cyfry przepisz.
Linia 11:
Poniżej zamieszczono przykładowe obliczenia 3-bitowego kodu CRC.
<pre>
11010011101100 000 <--- dane z dopisanymi zerami na 3 najmłodszych bitach
1011 <--- wielomian CRC
01100011101100 000 <---
1011 <--- wielomian CRC
00111011101100 000
1011
00010111101100 000
1011
00000001101100 000
1011
00000000110100 000
1011
00000000011000 000
1011
00000000001110 000
1011
00000000000101 000
--------------▼
101 1
00000000000101 <---reszta z dzielenia (3 bity)▼
▲-----------------
</pre>
|