Jaka jest odległość Hamminga i jak określić to dla schematu CRC?

Question

Studiując dla klasy w sieciach komputerowych, prof. Mówił o odległości Hamminga pomiędzy 2 ważnymi słowami kodowymi w przykładowym kodzie. Czytałem o dystansie Hamminga i ma to sens z punktu widzenia odróżnienia odległości między 2 strunami. Na przykład:

Code Word 1 = 10110 

Nadawca wysyła kod słowo 1, a tam jest błąd wprowadziły, a odbiornik odbiera 10100. Tak więc widać, że 4. bit został uszkodzony. Spowodowałoby oddali Hamminga 1, ponieważ:

Valid Code Word: 10110 
Error Code Word: 10100 
       ----- 
XOR    00010 

XOR wyników 2 smyczki w jednym 1, więc odległość Hamminga jest 1. Rozumiem go do tej pory. Ale wtedy prof pyta:

• Jaka jest odległość Hamminga od standardowego protokołu CRC-16 bit?
• Jaka jest odległość Hamminga od standardowego protokołu CRC-32 bit?

Jestem trochę zdezorientowany i zastanawiałem się, czy ktoś może pomóc. Dzięki.

Answer 1

Prawdopodobnie już to wymyśliłeś, ale to, o co prosił, to najprawdopodobniej minimalna liczba błędów bitowych, których kod CRC nie wykryłby. Odpowiedź zależy od szerokości, wielomianu i długości wiadomości. Na przykład najbardziej znany wielomian CRC-32 (0x1EDC6F41) ma odległość Hamminga równą 6 lub lepszą dla komunikatów o długości do 5 275 bitów (Castaglioni, Bräuer, Herrmann: Optymalizacja kodów sprawdzania cyklicznego nadmiarowości z 24 i 32 bitami parzystości, IEEE Transactions on Communications, t. 41 nr 6, czerwiec 1993), co oznacza, że ​​jest gwarantowane wykrywanie do 5 przewróconych bitów w jednym komunikacie o wartości 5 275 bitów lub mniej.

BTW, słowo kodowe zawiera sumę kontrolną, więc Twój przykład jest niepoprawny.