Czy to właściwy sposób na znalezienie sumy kontrolnej?

Question

Próbuję obliczyć sumę kontrolną dla niektórych danych. Jest to kod:

#include <stdio.h> 
#include <string.h> 

int main() 
{ 
    char MyArray[] = "my secret data"; 
    char checksum = 0; 
    int SizeOfArray = strlen(MyArray); 

    for(int x = 0; x < SizeOfArray; x++) 
    { 
      checksum += MyArray[x]; 
    } 
    printf("Sum of the bytes for MyArray is: %d\n", checksum); 

    printf("The checksum: \n"); 
    checksum = (checksum^0xFF); 
    printf("%d\n",checksum); 
} 

wyjściowa:

Sum of the bytes for MyArray is: 70 
The checksum: 
-71 

modyfikacji w kodzie:

#include <stdio.h> 
#include <string.h> 

int main() 
{ 
    char MyArray[] = "my secret data"; 
    char checksum = 0; // could be an int if preferred 
    int SizeOfArray = strlen(MyArray); 

    for(int x = 0; x < SizeOfArray; x++) 
    { 
      checksum += MyArray[x]; 
    } 
    printf("Sum of the bytes for MyArray is: %d\n", checksum); 

    //Perform bitwise inversion 
    checksum=~checksum; 
    //Increment 
    checksum++; 
    printf("Checksum for MyArray is: %d\n", checksum); 
    } 

wyjściowa:

Sum of the bytes for MyArray is: 70 
Checksum for MyArray is: -70 

Dlaczego zmiana wartości sumy kontrolnej? Czy różne algorytmy dostarczają różne sumy kontrolne?

Jak będzie przydatna wartość końcowa? Właściwie nie mam jasności co do sumy kontrolnej i jej wykorzystania w sprawdzaniu poprawności danych. Przeszukałem sieć, znalazłem wiele artykułów, ale wciąż nie było to jasne. Mam nadzieję, że zrozumiem tutaj dzisiaj sumę kontrolną.

Answer 1

To urody algorytmu sumy kontrolnej: sprawdzenie sposób można produkować sumę kontrolną i droga jest jakoś symetryczny!

1. O kontrolna

kontrolna jest zazwyczaj używany do weryfikacji integralności danych, szczególnie w hałaśliwym/niewiarygodny kanału komunikacyjnego. Dlatego jest używany głównie do wykrywania błędów . To znaczy, aby wiedzieć, czy otrzymane dane są poprawne czy nie czy nie.

Jest to zupełnie inna sytuacja, na przykład z korektą błędu. Ponieważ jego użycie jest nie tylko w celu sprawdzenia, czy nie ma błędów, ale także do ich poprawiania, zazwyczaj dane z korekcją błędów napowietrznych rośnie w rozmiarze raczej proporcjonalnie z oryginalnych danych (ponieważ Im więcej danych, tym bardziej narzut, aby go przywrócić).

Zatem w tym sensie algorytm sumy kontrolnej dobry jest zazwyczaj taka, która użyć najmniejszy ilości danych napowietrznych do wykryć błąd ale z wielką solidności wobec fałszywego rezultatu.

A z tym zrozumieniu problemu leży, ponieważ solidność kontrolnej naprawdę, zależy nie tylko od algorytmu, ale również zależy od kanałowych cechach. Niektóre kanały mogą być podatne na pewien rodzaj błędu, podczas gdy inne kanały inne. Ogólnie rzecz biorąc, istnieją pewne sumy kontrolne, które są znane jako bardziej niezawodne i bardziej popularne niż inne (jednym z moich ulubionych jest CRC - Cykliczna kontrola nadmiarowa). Ale nie ma idealnej sumy kontrolnej dla każdego scenariusza, to naprawdę zależy od zastosowania i scenariusza.

Ale nadal można mierzyć robustness algorytmu sumy kontrolnej. Jest matematyczny sposób, aby to zrobić, co moim zdaniem wykracza poza zakres tej dyskusji.W związku z tym niektóre sumy kontrolne w tych znaczeniach można uznać za słabsze od pozostałych. Sumy kontrolne, które pokazałeś w swoim pytaniu, są również słabe.

1. o kodzie

XOR 0xff 8-bitowych jest całkowicie równoważna z binarnym odwrócenie wartości i nie jest zbyt trudno zobaczyć .

XOR z 0xFF

1110 0010 
1111 1111 
--------- XOR 
0001 1101 //notice that this is exactly the same as binary inverting! 

Tak więc, gdy robisz XOR z 0xFF i ~checksum, można uzyskać ten sam rezultat -71 (a ponieważ twój typ danych jest char, ma wartość ujemną). Następnie zwiększasz go o 1, dzięki czemu otrzymujesz -70.

1. O 2' Uzupełnienie

uzupełnienie dwójkowe jest matematycznym operacji na liczbach binarnych, jak również binarny podpisany liczba reprezentacja na podstawie tej operacji. Jego szerokie zastosowanie w komputerach sprawia, że ​​jest to najważniejszy przykład dopełnienia radix. (wikipedia)

Innymi słowy, 2' uzupełnieniem jest znalezienie negatywny reprezentację wartości (w Computer binarny), a jego metoda jest, jak słusznie zrobił, przez odwrócenie wszystkich bitów, a następnie dodasz do to. Dlatego otrzymujesz -70 od 2 'uzupełnienia 70. Ale to oznacza, że ​​nie oznacza, że ​​2 'dopełnienie i XOR przez 0xFF to to samo, a jak widać na przykładzie, to naprawdę nie jest to samo.

Co XOR przez 0xFF w 8-bitowych danych jest po prostu równoważne odwróceniu wszystkich bitów. Nie dodaje do niej.

1. o sposobie czytania dodać/odczytu sumy kontrolnej

Ponieważ suma kontrolna służy znać integralności danych (czy jest on zmieniony lub nie), ludzie próbują znaleźć najlepszą praktykę, aby to zrobić. To, co robisz, to uzyskać sumę kontrolną przez 2 'uzupełnienie lub przez XOR z 0xFF.

A to, co robią:

• Dla 2' uzupełniać kontrolną. Powiedzmy, że twoja długość wiadomości to N. Od tego, co otrzymujesz przez sumowanie liczb N, powiedzmy 70. Następnie dodając sumę kontrolną 2'complement (czyli -70), Po stronie odbiorcy, po prostu musisz zsumować wszystkie wiadomości N + 1 łącznie z sumą kontrolną i powinieneś otrzymać 0, jeśli komunikat jest niezmieniony. W ten sposób poprawnie używa się sumy kontrolnej uzupełnienia 2 '.
• Dla XOR z 0xFF Powtórz, z tym samym przykładem co poprzedni, powinieneś otrzymać -1, jeśli podsumujesz wszystkie wiadomości N + 1, łącznie z sumą kontrolną.A ponieważ reprezentacja hex -1 0xFF jest w 8-bitowe podpisane, więc przez XOR ing wynik (-1) z 0xFF, należy uzyskać 0xFF^0xFF = 0 jeśli wiadomość nie zawiera błędu

Dlatego w obu przypadkach wystarczy sprawdzić, czy komunikat zawiera błąd, czy nie, sprawdzając, czy wynik końcowy wynosi 0 (brak błędu), czy też nie! Jest to zazwyczaj prawda dla algorytmów sum kontrolnych!

To urody algorytmu sumy kontrolnej: sprawdzenie sposób można produkować sumę kontrolną i droga jest jakoś symetryczny!

Answer 2

Musisz zrozumieć, co to jest suma kontrolna, zanim zastanowisz się, jak ją wygenerować. Załóżmy, że problem przesyłania danych przez niewiarygodny kanał komunikacji, na przykład połączenie sieciowe. Musisz upewnić się, że nie wystąpiły zakłócenia, które wpłynęły na twoją wiadomość.

Jednym ze sposobów, aby to zrobić, jest wysłanie wiadomości dwukrotnie i sprawdzenie różnic (w rzeczywistości istnieje niewielka szansa, że ​​dokładnie taki sam błąd wystąpi podczas przesyłania obu wiadomości). Wymaga to jednak dość dużej przepustowości (wysyłanie wiadomości dwukrotnie).

Bardziej wydajnym sposobem jest obliczenie wartości na podstawie wiadomości i dołączenie jej do wiadomości. Odbiorca stosuje tę samą funkcję i sprawdza, czy wartość jest taka sama.

Aby uzyskać bardziej intuicyjny przykład, suma kontrolna książki może być liczba stron. Kupujesz książkę z biblioteki i liczysz jej strony. Jeśli liczba stron nie jest zgodna z oczekiwaniami, wystąpił problem.

zaimplementować specyficzną funkcję kontrolną (LSB sumy), które jest w porządku. Wszystkie funkcje kontrolna mają pewne właściwości, które powinny być świadomy, ale chodzi o to, że nie jest to dobry sposób, aby obliczyć sumę kontrolną. Istnieje wiele funkcji, które można wykorzystać do tego celu.

Answer 3

Suma kontrolna jest zwykle wykorzystywane do wykrywania zmian w danych. Komunikacja, szyfrowanie/podpis itp. Sumy kontrolne są używane wszędzie.

Jak kontrolna może być przydatne?

• wykryje zmianę na 1 bit na przykład
• nawet wykrywa zmiany, gdy zmieniane są więcej niż 1 bit

To może wydawać się paradoksalne, ale gdy tylko 1 bit zmienia Twój kontrolna będzie praca. Jednak wziąć

(A) checksum += 0x11 instead of 0x10 

a później

(B) checksum += 0x30 instead of 0x31 

w punkcie (a) sumy kontrolnej będzie -1 ... i (B) będzie +1. Plus i minus 1 == 0.Dwa błędy zostaną wykryte przez twoją sumę kontrolną przez , a nie.

Zasadniczo jakość sumy kontrolnej zależy

• na długości kontrolnej (im większa suma kontrolna, tym bardziej będzie to obejmować większe dane, bez „zapętlenie” (jeden bajt ma tylko 256 sum kontrolnych możliwe 2 bajty ma 65536; pamiętać, że w przypadku wyżej z algorytmu, który nie zmieni wynik)

• jakości obliczania sumy kontrolnej, w celu zapobieżenia w jak największym stopniu, że dwie różnice anulować wzajemnie

  .

Dostępnych jest wiele algorytmów. This answer on SO to dobry początek.