Efektywność wykrywania błędów (CRC, suma kontrolna itp.)

Question

Mam hipotetyczną sytuację wysyłania jednostek danych, każdy z tysiąca bajtów. Częstość awarii jest rzadkością, ale gdy wystąpi błąd, jest mniej prawdopodobne, że będzie to błąd jednobitowy i częściej będzie to błąd w kilku bitach z rzędu.

Najpierw pomyślałem o użyciu sumy kontrolnej, ale najwyraźniej można pominąć błędy bitowe większe niż pojedynczy bit. Kontrola parzystości nie będzie działać, więc CRC może być najlepszą opcją.

Czy efektywna jest cykliczna kontrola nadmiarowości na tysiąc bajtów? Czy istnieją inne metody, które mogłyby działać lepiej?

Answer 1

Cykliczne kontrole nadmiarowe (CRC) są popularne specyficznie ze względu na ich skuteczność w wykrywaniu wielu błędów bitowych z gwarantowaną dokładnością.

Istnieją różne projekty generowania wielomianów CRC, gdzie kompromis jest dokładnością w porównaniu do złożoności obliczeniowej. W twoim przypadku możesz wybrać "najszybszy", który spełnia twoje wymagania dotyczące dokładności.

Możesz zacząć od tego artykułu w Wikipedii pod numerem Cyclic Redundancy Check.

Answer 2

Używanie CRC jest normalne. Nie jestem pewien, co rozumiesz przez "wydajność", ale myślę, że czasami CRC jest zaimplementowany sprzętowo (np. Na karcie Ethernet). W przeciwnym razie możesz znaleźć "zoptymalizowane" implementacje (korzystając z tabeli odnośników).

Answer 3

CRC jest pokryta w innym pytanie tutaj
When is CRC more appropriate to use than MD5/SHA1?
Jest odpowiedni do wykrywania błędów losowych i łatwe do wdrożenia.

Answer 4

Jak duże są sektory dysku? Prawdopodobnie co najmniej 512 bajtów. A CRC to uhonorowany czasowo schemat dla dysku ECC na poziomie sprzętu.

Zapasowe algorytmy wielomianu CRC są dość skuteczne w przypadku niewielkiej liczby błędów bitowych. Dokładna precyzja jest matematycznie obliczalna. CRC jest również bardzo wydajny w sprzęcie, w którym stosunkowo mała liczba bram i rejestrów przesuwnych może zarządzać pracą w locie.