PL

Kody wykrywające i korygujące błędy

Parzystość, kod Hamminga, odległość Hamminga, sumy kontrolne i CRC

Systemy liczbowe: Dwójkowy i szesnastkowy Kod Graya Kody BCD Liczby zmienno- i stałoprzecinkowe Parzystość, Hamming i CRC

Bit parzystości

Dane

Kod Hamminga

Wpisz bity danych, a bity parzystości zostaną obliczone. Następnie kliknij dowolny bit słowa, aby go odwrócić, jakby był to błąd transmisji, i zobacz, co robi odbiornik: syndrom wskazuje pozycję błędnego bitu. Spróbuj z jednym i dwoma błędami, z bitem parzystości całkowitej i bez niego.

Dane

parzystość · dane · parzystość całkowita · zmieniony bit.

Odległość Hamminga między dwoma słowami

Słowa

Kalkulator CRC i sum kontrolnych

Wpisz ramkę jako bajty szesnastkowe (ze spacjami lub bez) albo jako tekst. Kolumna „w ramce” podaje bajty w kolejności wysyłania.

Ramka

CRC krok po kroku: dzielenie wielomianów

Dzielenie

Po co są potrzebne

Żaden kanał nie jest doskonały: ramka RS-485 biegnąca obok falownika, bit pamięci trafiony cząstką albo rysa na płycie mogą zamienić 0 w 1. Aby to zauważyć, nadajnik dodaje do danych kilka bitów nadmiarowych obliczonych na ich podstawie, a odbiornik powtarza obliczenie. Jeśli wynik się nie zgadza, są dwie strategie:

Odległość Hamminga

Odległość Hamminga między dwoma słowami tej samej długości to liczba bitów, którymi się różnią: między 1011101 a 1001001 wynosi 2. Odległość minimalna \(d\) kodu to najmniejsza odległość między dowolnymi dwoma poprawnymi słowami i określa, co kod potrafi:

\[ \text{wykrywa do } d - 1 \text{ błędów} \qquad \text{koryguje do } \left\lfloor \frac{d-1}{2} \right\rfloor \text{ błędów} \]
KodOdległość minimalnaWykrywaKoryguje
Dane bez nadmiaru1nicnic
Bit parzystości, 2 z 521 błądnic
Hamming32 błędy1 błąd
Hamming z parzystością całkowitą (SECDED)43 błędy1 błąd i wykrywa 2
Powtórzenie każdego bitu 3 razy32 błędy1 błąd (większością głosów)

Idea jest geometryczna: jeśli poprawne słowa są od siebie oddalone co najmniej o 3, słowo z jednym błędem nadal jest bliżej oryginału niż jakiegokolwiek innego.

Parzystość

To najprostszy kod: dodaje się jeden bit, aby łączna liczba jedynek była parzysta (parzystość parzysta) lub nieparzysta (parzystość nieparzysta). Wykrywa każdą nieparzystą liczbę błędów, ale nie dwa bity zmienione jednocześnie. To parzystość portów szeregowych (8E1 oznacza 8 bitów danych, parzystość parzystą i 1 bit stopu; Modbus RTU domyślnie używa parzystości parzystej) i niektórych starych pamięci. W układzie oblicza się ją łańcuchem bramek XOR.

Przy parzystości dwuwymiarowej dane układa się w tabelę i dodaje parzystość każdego wiersza i każdej kolumny. Błąd zmienia parzystość jednego wiersza i jednej kolumny, a ich przecięcie wskazuje bit do poprawienia.

Kod Hamminga

Richard Hamming wymyślił go w 1950 roku, zmęczony tym, że awarie maszyn przekaźnikowych psuły mu weekendowe obliczenia. Pozycje słowa numeruje się od 1; pozycje będące potęgami 2 (1, 2, 4, 8…) zawierają bity parzystości, a pozostałe dane. Każdy bit parzystości \(p_k\) obejmuje pozycje, których numer dwójkowy ma ustawiony bit o wadze \(k\): \(p_1\) obejmuje 1, 3, 5, 7…; \(p_2\) obejmuje 2, 3, 6, 7…; \(p_4\) obejmuje 4–7, 12–15… Przy \(r\) bitach parzystości chroni się \(m\) bitów danych, jeśli:

\[ 2^{r} \ge m + r + 1 \]
Przykład: Hamming (7, 4) z danymi 1011

Dane trafiają na pozycje 3, 5, 6 i 7. \(p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0\), \(p_2 = d_1 \oplus d_3 \oplus d_4 = 1\) i \(p_4 = d_2 \oplus d_3 \oplus d_4 = 0\). Wysłane słowo to \(0110011\). Jeśli dotrze \(0110111\) (błąd na pozycji 5), odbiornik ponownie oblicza trzy parzystości z tego, co otrzymał: \(s_1 = 1\), \(s_2 = 0\), \(s_4 = 1\). Syndrom \(s_4 s_2 s_1 = 101_2 = 5\) to dokładnie pozycja błędu i wystarczy odwrócić ten bit.

KodBity danychBity parzystościSprawność
Hamming (7, 4)4357 %
Hamming (15, 11)11473 %
Hamming (31, 26)26584 %
Hamming (63, 57)57690 %
SECDED (72, 64), pamięć ECC64889 %

SECDED: korygować jeden, wykrywać dwa

Przy dwóch błędach zwykły kod Hamminga daje syndrom różny od zera i „poprawia” bit, który był dobry, pogarszając słowo. Aby tego uniknąć, dodaje się bit parzystości całkowitej P dla całego słowa (single error correction, double error detection):

To schemat pamięci ECC w serwerach i w wielu mikrokontrolerach dla motoryzacji i bezpieczeństwa: 8 bitów kontrolnych na każde 64 bity danych.

Sumy kontrolne

Są szybkie i łatwe do zaprogramowania, ale wykrywają błędy znacznie gorzej niż CRC tej samej długości.

CRC (cykliczna kontrola nadmiarowa)

CRC traktuje wiadomość jak wielomian o współczynnikach 0 i 1 (\(1011 = x^3 + x + 1\)) i dzieli ją przez wielomian generujący stopnia \(r\). W tej arytmetyce (modulo 2) dodawanie i odejmowanie to to samo co XOR i nie ma przeniesień. Nadajnik dopisuje do wiadomości \(r\) zer, dzieli i wysyła resztę w ich miejsce; odbiornik dzieli całą ramkę i jeśli nie ma błędów, reszta wynosi 0.

Przykład: wiadomość 11010011101100 z generatorem 1011 (\(x^3 + x + 1\))

Dopisuje się 3 zera i dzieli, odejmując (XOR) generator pod każdą jedynką pozostałą po lewej. Reszta to 100, więc wysyła się 11010011101100100. To przykład wczytany w kalkulatorze powyżej.

Przy dobrym wielomianie stopnia \(r\) CRC wykrywa:

Dlaczego ten sam „CRC-16” daje różne liczby

Oprócz wielomianu każdy CRC określa wartość początkową rejestru, czy bity każdego bajtu wchodzą odwrócone (od najmłodszego, tak jak wychodzą z UART), czy wynik jest odwracany i z jaką wartością wykonuje się końcowy XOR. Dlatego CRC-16/MODBUS, CRC-16/ARC i CRC-16/CCITT dają różne wyniki dla tych samych danych. Aby sprawdzić, którego używa urządzenie, oblicza się CRC tekstu 123456789 i porównuje z jego wartością kontrolną: 4B37 dla Modbus, 29B1 dla CCITT-FALSE, CBF43926 dla CRC-32.

CRC w przemyśle

Inne kody korygujące

Zobacz też: konwerter dwójkowy i szesnastkowy, kod 2 z 5 i symulator bramek logicznych (XOR).