Parzystość, kod Hamminga, odległość Hamminga, sumy kontrolne i CRC
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.
parzystość · dane · parzystość całkowita · zmieniony bit.
Wpisz ramkę jako bajty szesnastkowe (ze spacjami lub bez) albo jako tekst. Kolumna „w ramce” podaje bajty w kolejności wysyłania.
Ż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 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:
| Kod | Odległość minimalna | Wykrywa | Koryguje |
|---|---|---|---|
| Dane bez nadmiaru | 1 | nic | nic |
| Bit parzystości, 2 z 5 | 2 | 1 błąd | nic |
| Hamming | 3 | 2 błędy | 1 błąd |
| Hamming z parzystością całkowitą (SECDED) | 4 | 3 błędy | 1 błąd i wykrywa 2 |
| Powtórzenie każdego bitu 3 razy | 3 | 2 błędy | 1 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.
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.
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:
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.
| Kod | Bity danych | Bity parzystości | Sprawność |
|---|---|---|---|
| Hamming (7, 4) | 4 | 3 | 57 % |
| Hamming (15, 11) | 11 | 4 | 73 % |
| Hamming (31, 26) | 26 | 5 | 84 % |
| Hamming (63, 57) | 57 | 6 | 90 % |
| SECDED (72, 64), pamięć ECC | 64 | 8 | 89 % |
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.
Są szybkie i łatwe do zaprogramowania, ale wykrywają błędy znacznie gorzej niż CRC tej samej długości.
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.
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:
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.
Zobacz też: konwerter dwójkowy i szesnastkowy, kod 2 z 5 i symulator bramek logicznych (XOR).