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?

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 ¹ ), 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 .

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);

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):

• Suma kontrolna Fletchera
• uzupełnienie uzupełnienia
• uzupełnienie do dwóch

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.

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.

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.

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.

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.