Jaka jest szybsza alternatywa dla CRC?

27

Robię transmisję danych z dsPIC do komputera i robię 8-bitowy CRC do każdego bloku 512 bajtów, aby upewnić się, że nie ma błędów. Po włączeniu mojego kodu CRC uzyskuję około 33 KB / s, bez niego otrzymuję 67 KB / s.

Jakie są alternatywne algorytmy wykrywania błędów, aby sprawdzić, które byłyby szybsze?

FigBug
źródło
5
Jak wdrażana jest sama CRC? Bitowy? Następnie przejdź do metody opartej na tabeli. Bytewise? Rozważmy przestrzeń, złożoność i kompromis czasowy związany ze zwiększeniem wielkości tabeli do, powiedzmy, 16 bitów (co działałoby na dwóch bajtach jednocześnie, ale zajmowałoby 64 KB pamięci na stole).
Aidan Cully,
Mam tylko 16 KB na pamięci RAM i 128 KB pamięci ROM, więc tabela 64 KB nie wchodzi w grę.
FigBug
1
Więc używasz 256-bajtowej tabeli? lub bitowe CRC? Jeśli grasz bitowo, bajtewise (z 256-bajtową tabelą) byłby 8 razy szybszy.
Aidan Cully,
Obecnie
bitowo
1
67kb / s do 33kb / s? Nie jestem pewien, na czym polega twoje inne przetwarzanie, ale to brzmi jak narzut, nawet w przypadku PIC. Może są jakieś inne problemy, które utrudniają wydajność?
Rei Miyasaka,

Odpowiedzi:

41

Chociaż mogą istnieć szybsze opcje niż CRC, jeśli ich użyjesz, prawdopodobnie poświęcisz w pewnym stopniu zdolność wykrywania błędów. W zależności od wymagań dotyczących wykrywania błędów alternatywą może być użycie zoptymalizowanego dla aplikacji kodu CRC.

Aby porównać CRC z innymi opcjami, zobacz doskonałą odpowiedź Martina Thompsona .

Jedną z opcji, która może w tym pomóc, jest pycrc, które jest narzędziem (napisanym w Pythonie 1 ), które może generować kod źródłowy C dla wielu kombinacji modelu CRC i algorytmu . Pozwala to zoptymalizować szybkość i rozmiar dla własnej aplikacji, wybierając i porównując różne kombinacje. 1: Wymaga języka Python 2.6 lub nowszego.

Wspiera crc-8 modelu , ale również obsługuje crc-5, crc-16a crc-32między innymi. Co do algorytmów , obsługuje bit-by-bit, bit-by-bit-fasti table-driven.

Na przykład (pobieranie archiwum):

$ wget --quiet http://sourceforge.net/projects/pycrc/files/pycrc/pycrc-0.8/pycrc-0.8.tar.gz/download
$ tar -xf pycrc-0.8.tar.gz
$ cd pycrc-0.8
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit      --generate c -o crc8-byb.c
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit-fast --generate c -o crc8-bybf.c
$ ./pycrc.py --model=crc-8 --algorithm=table-driven    --generate c -o crc8-table.c
$ ./pycrc.py --model=crc-16 --algorithm=table-driven   --generate c -o crc16-table.c
$ wc *.c
   72   256  1790 crc8-byb.c
   54   190  1392 crc8-bybf.c
   66   433  2966 crc8-table.c
  101   515  4094 crc16-table.c
  293  1394 10242 total

Możesz nawet wykonywać funky, takie jak określanie, używając podwójnych odnośników (z 16-bajtową tablicą przeglądową) zamiast wyszukiwania jednobajtowego z 256-bajtową tablicą przeglądową.

Na przykład (klonowanie repozytorium git):

$ git clone http://github.com/tpircher/pycrc.git
$ cd pycrc
$ git branch
* master
$ git describe
v0.8-3-g7a041cd
$ ./pycrc.py --model=crc-8 --algorithm=table-driven --table-idx-width=4 --generate c -o crc8-table4.c
$ wc crc8-table4.c
  53  211 1562 crc8-table4.c

Biorąc pod uwagę pamięć i ograniczenia prędkości, ta opcja może być najlepszym kompromisem między prędkością a rozmiarem kodu. Jedynym sposobem, aby się upewnić, byłaby analiza porównawcza.


Pycrc repozytorium git jest github , jak jest jego tracker problem , ale można go również pobrać z SourceForge .

Mark Booth
źródło
Nie wierzę, że większość ludzi piszących dla PIC używa C, ale może to zadziałać, jeśli tak.
Billy ONeal
4
@Billy - Naprawdę? Nie sądzę, że spotkałem komercyjnego programistę do PIC, który nie używałby C. Z pewnością nie mam teraz cierpliwości do asemblera, a dobrze zbudowane C może być dość kompaktowe.
Mark Booth,
Używam dsPIC i używam C.
FigBug
@FigBug - Dzięki, cieszę się, że podoba ci się moja odpowiedź. Jeśli przeprowadzisz testy porównawcze, możesz edytować moją odpowiedź wraz z wynikami. Chciałbym wiedzieć, jak duża jest różnica każdego z algorytmów pod względem przepustowości aplikacji i wielkości pamięci.
Mark Booth
1
Kolejny głos na pyCrc tutaj. używanie go w różnych projektach z różnymi ograniczeniami i jest po prostu świetne.
Vicky
11

Prosta jednobitowa parzystość (w zasadzie XOR powtarzanie danych w kółko) jest tak szybka, jak to tylko możliwe. Jednak tracisz dużo kontroli błędów CRC.

W pseudokodzie:

char checksum = 0;
for each (char c in buffer)
{
    checksum ^= c;
    SendToPC(c);
}
SendToPc(checksum);
Billy ONeal
źródło
1
Przyglądałem się temu jakiś czas temu. I wierzę , że zsumowanie zamiast xor faktycznie działa trochę lepiej. (normalnie sumuje wszystko, a następnie przekazuje uzupełnienie 2 sumy jako sumy kontrolnej. Na odbiorniku sumuje wszystko, łącznie z tą otrzymaną sumą kontrolną. Wynik wynosi 0, jeśli wszystko jest dobre, a poza nią 0).
szybko_now
1
@ szybko: Nie sądzę, aby istniała znacząca różnica między tymi dwoma - żadna metoda nie zapewnia tak dobrego zapewnienia, że ​​nic nie zostało zepsute. Jeśli dodawanie jest szybsze w architekturze docelowej, użyj go zamiast tego.
Billy ONeal
7
Pamiętałem: główna różnica między ADD a XOR polega na tym, że wykrywalność błędów wielu bitów jest mniejsza. W przypadku strumienia bajtów błędy w tej samej pozycji bitowej są kasowane za pomocą XOR. Podczas korzystania z ADD propagacja bitów w górę przez bajt sumy kontrolnej oznacza, że ​​ten przypadek jest bardziej wykrywalny. (Jednak błędy wielu bitów w różnych bitach rozproszonych w strumieniu bajtów prawdopodobnie będą mniej wykrywalne - w zależności od okoliczności w danym czasie). Każde takie ustawienie sumy kontrolnej jest POTRZEBNE dla błędów wielu bitów, więc jest to dość niewielki argument.
szybko_now
XOR jest o wiele mniej pomocny niż CRC.
3
@ Thorbjørn: Wierzę, że potwierdziłem to w mojej odpowiedzi. :)
Billy ONeal
10

Naprawdę dobry artykuł porównujący wydajność różnych sum kontrolnych i CRC w osadzonym kontekście:

Skuteczność sum kontrolnych dla sieci osadzonych

Niektóre cytaty z wniosków (oparte na ich badaniach niewykrywalnych prawdopodobieństw błędów):

Kiedy dominują błędy serii

XOR, suma dwóch uzupełnień i sumy kontrolne CRC zapewniają lepszą wydajność wykrywania błędów niż suma uzupełnień jednej osoby, sumy kontrolne Fletchera i Adlera.

W innych aplikacjach

„dobry” wielomian CRC, o ile to możliwe, powinien być wykorzystywany do wykrywania błędów

Jeśli koszt obliczeń jest bardzo ograniczony

(jak w twoim przypadku), użyj (w kolejności skuteczności):

Inne cytaty:

Suma kontrolna Fletchera ma niższy koszt obliczeniowy niż suma kontrolna Adlera i, wbrew powszechnemu przekonaniu, jest również bardziej skuteczna w większości sytuacji.

i

Zasadniczo nie ma powodu, aby kontynuować powszechną praktykę stosowania sumy kontrolnej XOR w nowych projektach, ponieważ ma ona taki sam koszt obliczeniowy oprogramowania jak suma kontrolna oparta na dodatkach, ale jest tylko w połowie tak skuteczna w wykrywaniu błędów.

Martin Thompson
źródło
1
Jako bonus, suma kontrolna Fletchera jest bardzo łatwa do wdrożenia.
RubberDuck,
6

Sumy kontrolnej Adler powinny być wystarczające do sprawdzania zakłócenia transmisji. Jest używany przez bibliotekę kompresji Zlib i został przyjęty przez Java 3D Mobile Graphics Standard w celu zapewnienia szybkiego, ale skutecznego sprawdzania integralności danych.

Ze strony wikipedii :

Suma kontrolna Adler-32 jest uzyskiwana przez obliczenie dwóch 16-bitowych sum kontrolnych A i B i połączenie ich bitów w 32-bitową liczbę całkowitą. A jest sumą wszystkich bajtów w ciągu plus jeden, a B jest sumą poszczególnych wartości A z każdego kroku.

Na początku przebiegu Adler-32 A jest inicjowane na 1, B na 0. Sumy są wykonywane modulo 65521 (największa liczba pierwsza mniejsza niż 2 ^ 16 lub 65536). Bajty są przechowywane w kolejności sieci (big endian), B zajmuje dwa najbardziej znaczące bajty.

Funkcja może być wyrażona jako

 A = 1 + D1 + D2 + ... + Dn (mod 65521)
 B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

 Adler-32(D) = B × 65536 + A

gdzie D jest łańcuchem bajtów, dla którego ma zostać obliczona suma kontrolna, a n jest długością D.

Gryźć
źródło
Należy pamiętać, że Adler32 jest prawie bezużyteczny w przypadku krótkich serii danych. Do około 180 bajtów powoduje liczne kolizje.
greyfade
+1 - rozsądny środek między CRC a zwykłą parzystością bitów.
Billy ONeal
@greyfade - FigBug wspomniał o użyciu bloków 512-bajtowych, więc nie powinno to stanowić problemu dla OP. Dobrze jest jednak pamiętać o osobach o innych wymaganiach.
Mark Booth
5

Nie znam niczego, co byłoby tak skuteczne w wykrywaniu błędów jak CRC i szybsze - gdyby tak było, ludzie używaliby go zamiast tego.

Możesz wypróbować prostą sumę kontrolną, ale znacznie mniej prawdopodobne jest wykrycie błędów.

Bob Murphy
źródło
2
Jestem gotów zrezygnować z prędkości.
FigBug
3

Cóż, sama logika sumy kontrolnej jest dobra i ludzie mogą pomóc w szybszych algorytmach.

Jeśli chcesz poprawić szybkość swojego komponentu, być może trzeba będzie zmienić ogólną technikę, aby oddzielić komponent transferu od komponentu sprawdzania poprawności.

Jeśli masz je jako dwa niezależne elementy (w różnych wątkach), możesz uzyskać pełną prędkość transferu i ponownie wysyłać tylko nieudane pakiety.

Algorytm wyglądałby mniej więcej tak:

  • Serwer rozpada się na znane rozmiary pakietów (powiedzmy 1K). Umieszcza je w kolejce „do wysłania”.
  • Każdy pakiet jest wysyłany z 16 lub 32-bitowym ID ORAZ sumą kontrolną.
  • Klient odbiera każdy pakiet i umieszcza go w kolejce do przetworzenia.
  • W osobnym wątku klient pobiera pakiet na raz, sprawdza poprawność.
    • Po sukcesie dodaje go do ostatecznego zbioru pakietów (w kolejności ID)
    • W przypadku awarii raportuje z powrotem identyfikator do serwera, który kolejkuje ten pakiet, aby go wysłać.
  • Po otrzymaniu i sprawdzeniu poprawności pakietów i posiadaniu identyfikatorów w odpowiedniej kolejności (od 1) możesz zacząć zapisywać je na dysku (lub robić to, co jest wymagane).

Umożliwi to przesyłanie z najwyższą możliwą prędkością, a jeśli grasz z rozmiarem swojego pakietu, możesz obliczyć współczynnik awaryjności optymium VS sprawdzania poprawności / ponownego wysyłania.

Robin Vessey
źródło
2

Sumy kontrolne są tradycyjne

(zmniejsz # '+ strumień)

XOR, jak podano powyżej, również działałoby

(zmniejsz # 'strumień XOR)

Nieco bardziej skomplikowanym (wolniejszym) schematem jest standardowa kontrola parzystości dla połączeń szeregowych.

Na tym poziomie handlujesz poprawnością prędkości. Czasami się to nie powiedzie.

Na następnym najbardziej wyrafinowanym poziomie możesz użyć pewnych rzeczy typu crc / hash.

Innym rozwiązaniem byłoby zwiększenie rozmiaru bloku używanego dla strumienia.

Powinieneś mieć oszacowanie rzeczywistego poziomu błędu, aby dostroić wybór algorytmu i parametry wielkości bloku.

Paul Nathan
źródło