Kalkulator CRC / XOR / Modulo-2 dzielenia pisemnego

Jak korzystać z kalkulatora CRC / XOR / Modulo-2

Aby obliczyć CRC przez dzielenie modulo-2, wykonaj te 4 kroki:

• Wpisz binarną wiadomość (bity danych) w pierwszym polu.
• Wpisz wielomian generatora jako bity binarne w drugim polu.
• Kalkulator dołącza (n − 1) bitów zerowych, gdzie n to długość generatora.
• Kliknij Oblicz, aby XOR-ować w dół wiadomość i odczytać resztę jako CRC.

Iloraz zwykle odrzuca się w pracy z CRC — reszta to suma kontrolna dołączana do wiadomości przed transmisją.

CRC i arytmetyka modulo-2

Cykliczny kod nadmiarowy wykrywa błędy transmisji, traktując wiadomość jako duży wielomian binarny i dzieląc go przez uzgodniony wielomian generatora. Dzielenie wykonuje się w arytmetyce modulo-2 (GF(2)), gdzie dodawanie i odejmowanie są identyczne i równają się XOR — bez przeniesień i pożyczeń. Reszta z tego dzielenia to CRC. Gdy odbiorca dzieli wiadomość plus CRC przez ten sam generator, reszta 0 oznacza brak wykrytego błędu. Ten kalkulator odtwarza dokładnie ten proces bitowy.

Jak działa dzielenie CRC modulo-2

Kalkulator oblicza CRC przez pięć wewnętrznych czynności:

• Dołącza (n − 1) bitów zerowych do wiadomości, gdzie n to liczba bitów generatora.
• Wyrównuje generator pod najbardziej lewą 1 bieżącej reszty.
• XOR-uje generator w te bity (odejmowanie modulo-2 bez pożyczki).
• Przesuwa do następnej wiodącej 1 i powtarza wyrównanie XOR.
• Zatrzymuje się, gdy pozostałe bity są krótsze od generatora; to jest CRC.

Każdy bit ilorazu to 1, gdzie generator jest XOR-owany, i 0 w pozostałych miejscach, ale dla CRC liczy się tylko końcowa reszta.

Wzór na dzielenie CRC

Kalkulator CRC / XOR / Modulo-2 oblicza CRC = (M(x) · xⁿ⁻¹) mod G(x) w GF(2), gdzie M(x) to wiadomość, G(x) to generator o n bitach, a wszystkie dodawania to XOR. Ramka transmisji to M(x)·xⁿ⁻¹ + CRC, którą G(x) dzieli dokładnie. Po stronie odbiorcy reszta zero potwierdza integralność.

Przykładowe zadania CRC / XOR

Te przykłady pokazują dzielenie modulo-2 z XOR na każdym kroku.

Przykład 1 — Wiadomość 1101, generator 101

1. Długość generatora 3, więc dołącz 2 zera: 1101 staje się 110100.
2. XOR-uj 101 w wiodących bitach wielokrotnie: 110100 → 011100 → 001000 → 000010.
3. Ostatnie 2 bity, 10, to reszta CRC.

Przykład 2 — Dlaczego odejmowanie to XOR

1. W modulo-2: 1 + 1 = 0 i 1 − 1 = 0, więc dodawanie i odejmowanie to ta sama operacja.
2. Ta operacja to dokładnie bitowe XOR, bez przeniesienia i pożyczki.
3. Każdy krok dzielenia to jedno XOR generatora w bieżących bitach.

Przykład 3 — Kontrola odbiorcy

1. Dołącz CRC do wiadomości i podziel przez ten sam generator.
2. XOR-uj w dół dokładnie jak wcześniej.
3. Reszta 0 oznacza brak wykrytego błędu.

Długość generatora 3, więc dołącz 2 zera: 1101 staje się 110100.
XOR-uj 101 w wiodących bitach wielokrotnie: 110100 → 011100 → 001000 → 000010.
Ostatnie 2 bity, 10, to reszta CRC.

W modulo-2: 1 + 1 = 0 i 1 − 1 = 0, więc dodawanie i odejmowanie to ta sama operacja.
Ta operacja to dokładnie bitowe XOR, bez przeniesienia i pożyczki.
Każdy krok dzielenia to jedno XOR generatora w bieżących bitach.

Dołącz CRC do wiadomości i podziel przez ten sam generator.
XOR-uj w dół dokładnie jak wcześniej.
Reszta 0 oznacza brak wykrytego błędu.

Rozwiązane zadania CRC

Jak obliczyć CRC dla 10110 z generatorem 1011?

Dołącz 3 zera (długość generatora 4), aby uzyskać 10110000, następnie XOR w dół. Wyrównaj 1011 pod każdą wiodącą 1 i XOR: 10110000 → 00100000 → po kolejnych XOR ostatnie 3 bity tworzą resztę CRC. Resztę dołącza się do 10110, więc cała ramka dzieli się przez 1011 bez reszty.

Dlaczego reszta zero oznacza nienaruszone dane?

Nadawca wybiera CRC tak, aby ramka transmisji była dokładną wielokrotnością generatora. Każda wielokrotność G(x) podzielona przez G(x) daje resztę 0. Jeśli bity zmienią się w trakcie, ramka zwykle nie jest już wielokrotnością, więc dzielenie odbiorcy daje niezerową resztę, sygnalizując błąd.

Typowe błędy CRC / modulo-2

Dzielenie CRC modulo-2 prowadzi do 5 częstych błędów:

• Używanie zwykłego odejmowania binarnego z pożyczkami zamiast XOR.
• Dołączenie złej liczby bitów zerowych (musi być długość generatora minus jeden).
• Wyrównanie generatora pod bitem 0 zamiast pod wiodącą 1.
• Traktowanie przeniesień, jakby istniały w arytmetyce GF(2).
• Podawanie ilorazu jako CRC zamiast reszty.

Kalkulator CRC / XOR / Modulo-2 XOR-uje na każdym kroku, dołącza poprawne zera i zwraca resztę jako sumę kontrolną.

Czeste pytania