Suma kontrolna Fletchera

Suma kontrolna Fletchera to algorytm obliczania sumy kontrolnej zależnej od pozycji, opracowany przez Johna G. Fletchera (1934–2012) w Lawrence Livermore Labs pod koniec lat siedemdziesiątych. Celem sumy kontrolnej Fletchera było zapewnienie właściwości wykrywania błędów zbliżonych do właściwości cyklicznej kontroli redundancji, ale przy mniejszym wysiłku obliczeniowym związanym z technikami sumowania.

Algorytm

Przegląd prostych sum kontrolnych

Podobnie jak w przypadku prostszych algorytmów sumy kontrolnej, suma kontrolna Fletchera obejmuje podzielenie słowa danych binarnych , które ma być chronione przed błędami, na krótkie „bloki” bitów i obliczenie sumy modułowej tych bloków. (Należy pamiętać, że terminologia używana w tej dziedzinie może być myląca. Dane, które mają być chronione, w całości określane są jako „słowo”, a części, na które są podzielone, nazywane są „blokami”.)

Na przykład dane mogą być wiadomością do przesłania składającą się ze 136 znaków, z których każdy jest przechowywany jako 8-bitowy bajt , co daje w sumie słowo danych o długości 1088 bitów. Wygodnym rozmiarem bloku byłoby 8 bitów, chociaż nie jest to wymagane. Podobnie, wygodnym modułem byłoby 255, chociaż znowu można by wybrać inne. Tak więc prosta suma kontrolna jest obliczana przez dodanie wszystkich 8-bitowych bajtów wiadomości, podzielenie przez 255 i zachowanie tylko reszty. (W praktyce operacja modulo jest wykonywana podczas sumowania, aby kontrolować rozmiar wyniku.) Wartość sumy kontrolnej jest przesyłana wraz z komunikatem, zwiększając jego długość do 137 bajtów, czyli 1096 bitów. Odbiorca wiadomości może ponownie obliczyć sumę kontrolną i porównać ją z odebraną wartością, aby określić, czy wiadomość została zmieniona przez proces transmisji.

Słabości prostych sum kontrolnych

Pierwszą słabością prostej sumy kontrolnej jest to, że jest ona niewrażliwa na kolejność bloków (bajtów) w słowie danych (komunikacie). Jeśli kolejność zostanie zmieniona, wartość sumy kontrolnej będzie taka sama, a zmiana nie zostanie wykryta. Drugą słabością jest to, że wszechświat wartości sum kontrolnych jest mały, równy wybranemu modułowi. W naszym przykładzie jest tylko 255 możliwych wartości sumy kontrolnej, więc łatwo zauważyć, że nawet przypadkowe dane mają około 0,4% prawdopodobieństwa posiadania tej samej sumy kontrolnej, co nasza wiadomość.

Suma kontrolna Fletchera

Fletcher rozwiązuje obie te słabości, obliczając drugą wartość wraz z prostą sumą kontrolną. Jest to modułowa suma wartości przyjmowanych przez prostą sumę kontrolną, gdy każdy blok słowa danych jest do niej dodawany. Zastosowany moduł jest taki sam. Tak więc dla każdego bloku słowa danych, wziętego w sekwencji, wartość bloku jest dodawana do pierwszej sumy, a nowa wartość pierwszej sumy jest następnie dodawana do drugiej sumy. Obie sumy zaczynają się od wartości zero (lub innej znanej wartości). Na końcu słowa danych stosowany jest operator modułu i dwie wartości są łączone w celu utworzenia wartości sumy kontrolnej Fletchera.

Wprowadzono wrażliwość na kolejność bloków, ponieważ po dodaniu bloku do pierwszej sumy, jest on następnie wielokrotnie dodawany do drugiej sumy wraz z każdym kolejnym blokiem. Jeśli na przykład dwa sąsiednie bloki zostaną zamienione, ten, który był pierwotnie pierwszy, zostanie dodany do drugiej sumy o jeden mniej razy, a ten, który pierwotnie był drugi, zostanie dodany do drugiej sumy jeszcze raz. Ostateczna wartość pierwszej sumy będzie taka sama, ale druga suma będzie inna, wykrywając zmianę w wiadomości.

Wszechświat możliwych wartości sum kontrolnych jest teraz kwadratem wartości prostej sumy kontrolnej. W naszym przykładzie dwie sumy, każda z 255 możliwymi wartościami, dają 65025 możliwych wartości dla połączonej sumy kontrolnej.

Przegląd różnych parametrów algorytmu

Chociaż istnieje nieskończona liczba parametrów, oryginalny artykuł bada tylko przypadek K=8 (długość słowa) z modułem 255 i 256.

Wersje 16- i 32-bitowe (Fletcher-32 i -64) zostały wyprowadzone z oryginalnego przypadku i zbadane w kolejnych specyfikacjach lub artykułach.

Fletcher-16

     Kiedy słowo danych jest dzielone na 8-bitowe bloki, jak w powyższym przykładzie, powstają dwie 8-bitowe sumy, które są łączone w 16-bitową sumę kontrolną Fletchera. Zwykle druga suma zostanie pomnożona przez 256 i dodana do prostej sumy kontrolnej, skutecznie układając sumy obok siebie w 16-bitowym słowie z prostą sumą kontrolną na najmniej znaczącym końcu. Algorytm ten jest następnie nazywany sumą kontrolną Fletchera-16. użycie modułu 2 8 − 1 = 255.

Fletcher-32

     Kiedy słowo danych jest dzielone na 16-bitowe bloki, powstają dwie 16-bitowe sumy, które są łączone w 32-bitową sumę kontrolną Fletchera. Zwykle druga suma zostanie pomnożona przez 2 16 i dodana do prostej sumy kontrolnej, skutecznie układając sumy obok siebie w 32-bitowym słowie z prostą sumą kontrolną na najmniej znaczącym końcu. Algorytm ten jest następnie nazywany sumą kontrolną Fletchera-32. Ogólnie sugeruje się również użycie modułu 2 16 − 1 = 65 535. Uzasadnienie tego wyboru jest takie samo jak w przypadku Fletchera-16.

Fletcher-64

     Kiedy słowo danych jest dzielone na 32-bitowe bloki, powstają dwie 32-bitowe sumy, które są łączone w 64-bitową sumę kontrolną Fletchera. Zwykle druga suma zostanie pomnożona przez 2 32 i dodana do prostej sumy kontrolnej, skutecznie układając sumy obok siebie w 64-bitowym słowie z prostą sumą kontrolną na najmniej znaczącym końcu. Algorytm ten jest następnie nazywany sumą kontrolną Fletchera-64. użycie modułu 2 32 − 1 = 4 294 967 295. Uzasadnienie tego wyboru jest takie samo jak w przypadku Fletchera-16 i Fletchera-32.

Porównanie z sumą kontrolną Adlera

Adler -32 jest specjalizacją sumy kontrolnej Fletcher-32 opracowanej przez Marka Adlera . Wybrany moduł (dla obu sum) to liczba pierwsza 65 521 (65 535 jest podzielne przez 3, 5, 17 i 257). Pierwsza suma również zaczyna się od wartości 1. Wybór pierwszego modułu powoduje lepsze „mieszanie” (wzorce błędów są wykrywane z bardziej jednolitym prawdopodobieństwem, co zwiększa prawdopodobieństwo wykrycia najmniej wykrywalnych wzorców, co zwykle dominuje nad ogólną wydajnością ). Jednak zmniejszenie rozmiaru wszechświata możliwych wartości sum kontrolnych działa przeciwko temu i nieznacznie zmniejsza wydajność. Jedno z badań wykazało, że Fletcher-32 przewyższa Adler-32 zarówno pod względem wydajności, jak i zdolności do wykrywania błędów. Ponieważ dodawanie modulo-65,535 jest znacznie prostsze i szybsze do wdrożenia niż dodawanie modulo-65,521, suma kontrolna Fletchera-32 jest generalnie szybszym algorytmem.

Uwaga na moduł

Moduł 255 jest używany powyżej i w poniższych przykładach dla Fletchera-16, jednak niektóre rzeczywiste implementacje używają 256. Alternatywna suma kontrolna protokołu TCP ma moduł Fletcher-16 z modułem 256, podobnie jak sumy kontrolne wiadomości UBX-* z Ublox GPS. To, którego modułu potrzebujesz, zależy od implementacji drugiej strony. Dokładnie sprawdź dokumentację swoich protokołów!

Przykładowe obliczenie sumy kontrolnej Fletchera-16

Na przykład suma kontrolna Fletchera-16 zostanie obliczona i zweryfikowana dla strumienia bajtów 0x01 0x02.

  • C0_początkowe = 0
  • C1_początkowy = 0
Bajt (B) C0 = (C0 poprzedni + B) mod 255 C1 = (C1 poprzedni + C0) mod 255 Opis
0x01 0x01 0x01 Wprowadzono pierwszy bajt
0x02 0x03 0x04 Dostarczono drugi bajt

Suma kontrolna wynosi zatem 0x0403. Może być przesyłany ze strumieniem bajtów i jako taki weryfikowany po stronie odbierającej. Inną opcją jest obliczenie w drugim kroku pary bajtów kontrolnych, które można dołączyć do strumienia bajtów, tak aby wynikowy strumień miał globalną wartość sumy kontrolnej Fletchera-16 równą 0.

Wartości bajtów kontrolnych są obliczane w następujący sposób:

  • CB0 = 255 − ((C0 + C1) mod 255),
  • CB1 = 255 − ((C0 + CB0) mod 255),

gdzie C0 i C1 są wynikiem ostatniego kroku obliczeń Fletchera-16.

W naszym przypadku bajty sumy kontrolnej to CB0 = 0xF8 i CB1 = 0x04. Przesyłany strumień bajtów to 0x01 0x02 0xF8 0x04. Odbiornik sprawdza sumę kontrolną na wszystkich czterech bajtach i oblicza sumę kontrolną 0x00 0x00, jak pokazano poniżej:

Bajt (B) C0 = (C0 poprzedni + B) mod 255 C1 = (C1 poprzedni + C0) mod 255 Opis
0x01 0x01 0x01 Wprowadzono pierwszy bajt
0x02 0x03 0x04 Dostarczono drugi bajt
CB0 = 0xF8 (0x03 + 0xF8) % 0xFF = 0xFB (0x04 + 0xFB) % 0xFF = 0x00 Obliczanie sumy kontrolnej – bajt 1
CB1 = 0x04 (0xFB + 0x04) % 0xFF = 0x00 (0x00 + 0x00) % 0xFF = 0x00 Obliczanie sumy kontrolnej – bajt 2

Słabości

Suma kontrolna Fletchera nie rozróżnia bloków składających się wyłącznie z 0 bitów i bloków składających się wyłącznie z 1 bitów. Na przykład, jeśli 16-bitowy blok w słowie danych zmieni się z 0x0000 na 0xFFFF, suma kontrolna Fletcher-32 pozostanie taka sama. Oznacza to również, że sekwencja wszystkich bajtów 00 ma taką samą sumę kontrolną jak sekwencja (tego samego rozmiaru) wszystkich bajtów FF.

Realizacja

W tych przykładach założono arytmetykę dopełnienia do dwóch , ponieważ algorytm Fletchera będzie niepoprawny na maszynach dopełniających .

Prosty

Poniżej przedstawiono sposób obliczania sumy kontrolnej, w tym bajtów kontrolnych; tj. końcowy wynik powinien być równy 0, przy prawidłowo obliczonych bajtach kontrolnych. Sam kod nie obliczy jednak bajtów kontrolnych.

Niewydajna, ale prosta implementacja funkcji języka C do obliczania sumy kontrolnej Fletchera-16 tablicy 8 -bitowych elementów danych jest następująca: 

      

      0
      0
    

       0     
   
            
            
   

        
 uint16_t  Fletcher16  (  uint8_t  *  dane  ,  liczba  int  )  {  uint16_t  sum1  =  ;  uint16_t  suma2  =  ;  indeks  int  ;  for  (  indeks  =  ;  indeks  <  liczba  ;  ++  indeks  )  {  sum1  =  (  suma1  +  dane  [  indeks  ])  %  255  ;  suma2  =  (  suma2  +  suma1  )  %  255  ;  }  powrót  (  suma2  <<  8  )  |  suma1  ;  }

W wierszach 3 i 4 sumy są zmiennymi 16-bitowymi , więc dodania w wierszach 9 i 10 nie przepełnią się . Operacja modulo jest stosowana do pierwszej sumy w wierszu 9 i do drugiej sumy w wierszu 10. Tutaj jest to wykonywane po każdym dodaniu, tak że na końcu pętli for sumy są zawsze redukowane do 8 bitów. Na końcu danych wejściowych te dwie sumy są łączone w 16-bitową wartość sumy kontrolnej Fletchera i zwracane przez funkcję w linii 13.

Każda suma jest obliczana modulo 255, a zatem przez cały czas pozostaje mniejsza niż 0xFF. W związku z tym ta implementacja nigdy nie wygeneruje wyników sumy kontrolnej 0x??FF, 0xFF?? lub 0xFFFF (tj. 511 z wszystkich 65536 możliwych wartości 16-bitowych nigdy nie jest używanych). Może dać wynik sumy kontrolnej 0x0000, co może być niepożądane w pewnych okolicznościach (np. gdy ta wartość została zarezerwowana jako oznaczająca „żadna suma kontrolna nie została obliczona”).

Sprawdź bajty

Przykładowy kod źródłowy do obliczania bajtów kontrolnych przy użyciu powyższej funkcji jest następujący. Bajty kontrolne mogą być dołączone na końcu strumienia danych, przy czym c0 znajduje się przed c1.

 
 

   
    
      
        
         uint16_t  csum  ;  uint16_t  c0  ,  c1  ,  f0  ,  f1  ;  csum  =  Fletcher16  (  dane  ,  długość  );  f0  =  csum  &  0xff  ;  f1  =  (  csum  >>  8  )  &  0xff  ;  c0  =  0xff  -  ((  f0  +  f1  )  %  0xff  );  c1  =  0xff  -  ((  f0  +  c0  )  %  0xff  );

optymalizacje

W artykule z 1988 roku Anastase Nakassis omówił i porównał różne sposoby optymalizacji algorytmu. Najważniejsza optymalizacja polega na zastosowaniu większych akumulatorów i opóźnieniu stosunkowo kosztownej operacji modulo tak długo, jak można udowodnić, że nie nastąpi przepełnienie. Dalsze korzyści można uzyskać z zastąpienia operatora modulo równoważną funkcją dostosowaną do tego konkretnego przypadku — na przykład prostym porównaniem i odejmowaniem, ponieważ iloraz nigdy nie przekracza 1.

Oto implementacja C , która stosuje pierwszą optymalizację, ale nie drugą: 

 
 

      
	  

	
	
	     0   0  
		   
		    
			  
		
		  
		 
			    
			    
		  
		    
		    
   
        


      
	  
	            

	
	
	     0   0  
		   
		    
			  
		
		  
		 
			    
			    
		    
		    
		    
	
	     


 #include  <stdlib.h>  /* dla size_t */  #include  <stdint.h>  /* dla uint8_t, uint16_t & uint32_t */  uint16_t  fletcher16  (  const  uint8_t  *  data  ,  size_t  len  )  {  uint32_t  c0  ,  c1  ;  /* Znalezione przez rozwiązanie dla przepełnienia c1: */  /* n > 0 i n * (n+1) / 2 * (2^8-1) < (2^32-1). */   for  (  c0  =  c1  =  ;  dł  >  ;  )  {  size_t  blocklen  =  dł  ;  if  (  liczba bloków  >  5802  )  {  liczba bloków  =  5802  ;  }  len  -=  zablokuj  ;  zrobić  {  c0  =  c0  +  *  dane  ++  ;  c1  =  c1  +  c0  ;  }  while  (  -blocklen  )  ;  c0  =  c0  %  255  ;  c1  =  c1  %  255  ;  }  powrót  (  c1  <<  8  |  c0  );  }  uint32_t  fletcher32  (  const  uint16_t  *  dane  ,  size_t  len  )  {  uint32_t  c0  ,  c1  ;  dł  =  (  dł  +  1  )  &  ~  1  ;  /* Zaokrąglij len do słów */  /* Podobnie rozwiązujemy tutaj dla n > 0 i n * (n+1) / 2 * (2^16-1) < (2^32-1). */   /* Na nowoczesnych komputerach użycie 64-bitowego c0/c1 pozwoliłoby na utworzenie grupy o rozmiarze 23726746. */  for  (  c0  =  c1  =  ;  len  >  ;  )  {  size_t  blocklen  =  len  ;  if  (  liczba bloków  >  360  *  2  )  {  długość bloków  =  360  *  2  ;  }  len  -=  zablokuj  ;  zrobić  {  c0  =  c0  +  *  dane  ++  ;  c1  =  c1  +  c0  ;  }  while  ((  blocklen  -=  2  ));  c0  =  c0  %  65535  ;  c1  =  c1  %  65535  ;  }  powrót  (  c1  <<  16  |  c0  );  }  // Podobną procedurę można napisać dla programu Fletcher64. Wielkość grupy wynosiłaby 92681.

Druga optymalizacja nie jest używana, ponieważ założenie „nigdy nie przekracza 1” ma zastosowanie tylko wtedy, gdy modulo jest obliczane naiwnie; zastosowanie pierwszej optymalizacji zepsułoby to. Z drugiej strony numery modulo Mersenne'a , takie jak 255 i 65535, i tak są szybką operacją na komputerach, ponieważ dostępne są sztuczki umożliwiające ich wykonanie bez kosztownej operacji dzielenia.

Wektory testowe

Implementacja 8-bitowa (16-bitowa suma kontrolna)

"abcde" -> 51440 (0xC8F0) "abcdef" -> 8279 (0x2057) "abcdefgh" -> 1575 (0x0627)

16-bitowa implementacja (32-bitowa suma kontrolna), z 8-bitowymi wartościami ASCII słowa wejściowego złożonymi w 16-bitowe bloki w kolejności little-endian , słowo uzupełnione zerami w razie potrzeby do następnego całego bloku, przy użyciu modułu 65535 i z wynikiem przedstawionym jako suma sum przesunięta w lewo o 16 bitów (pomnożona przez 65536) plus suma prosta 

"abcde" -> 4031760169 (0xF04FC729) "abcdef" -> 1448095018 (0x56502D2A) "abcdefgh" -> 3957429649 (0xEBE19591)

Implementacja 32-bitowa (64-bitowa suma kontrolna)

"abcde" -> 14467467625952928454 (0xC8C6C527646362C6) "abcdef" -> 14467579776138987718 (0xC8C72B276463C8C6) "abcdefgh" -> 3543817411021686982 ( 0x312E2B28CCCAC8C6)

Kolejność bitów i bajtów ( endianowość / kolejność sieci)

Podobnie jak w przypadku każdego obliczenia, które dzieli słowo danych binarnych na krótkie bloki i traktuje bloki jako liczby, dowolne dwa systemy oczekujące uzyskania tego samego wyniku powinny zachować kolejność bitów w słowie danych. Pod tym względem suma kontrolna Fletchera nie różni się od innych algorytmów sum kontrolnych i CRC i nie wymaga specjalnego wyjaśnienia.

Łatwy do wyobrażenia problem z uporządkowaniem pojawia się, gdy słowo danych jest przesyłane bajt po bajcie między systemem big-endian a systemem little-endian i obliczana jest suma kontrolna Fletchera-32. Jeśli bloki zostaną wyodrębnione ze słowa danych w pamięci przez prosty odczyt 16-bitowej liczby całkowitej bez znaku, wówczas wartości bloków będą różne w obu systemach z powodu odwrócenia kolejności bajtów 16-bitowych elementów danych w pamięci, a wynik sumy kontrolnej będzie w konsekwencji inny. Powyższe przykłady implementacji nie dotyczą problemów z porządkowaniem, aby nie zaciemniać algorytmu sumy kontrolnej. Ponieważ suma kontrolna Fletchera-16 wykorzystuje 8-bitowe bloki, nie ma na nią wpływu endianowość bajtów .

  1. ^ Fletcher, JG (styczeń 1982). „Arytmetyczna suma kontrolna dla transmisji szeregowych”. Transakcje IEEE w komunikacji . COM-30 (1): 247–252. doi : 10.1109/tcom.1982.1095369 .
  2. ^ Theresa C. Maxino, Philip J. Koopman (styczeń 2009). „Skuteczność sum kontrolnych dla wbudowanych sieci kontrolnych” (PDF) . Transakcje IEEE dotyczące niezawodnego i bezpiecznego przetwarzania danych.
  3. ^ J.Zweig, UIUC, C.Partridge, BBN (luty 1990). "Opcje alternatywnej sumy kontrolnej TCP" . Sieciowa Grupa Robocza. {{ cite web }} : CS1 maint: wiele nazw: lista autorów ( link )
  4. ^ Sartek, Różne (czerwiec 2018). „Prawidłowe obliczanie sumy kontrolnej UBX w Pythonie” . Portal wsparcia uBlox.
  5. ^   Anastase Nakassis (październik 1988). „Algorytm wykrywania błędów Fletchera: jak skutecznie go wdrożyć i jak uniknąć najczęstszych pułapek”. Biuletyn ACM SIGCOMM Przegląd komunikacji komputerowej Strona główna Archiwum . 18 (5): 63–88. doi : 10.1145/53644.53648 . S2CID 17356816 .
  6. ^ Jones, Douglas W. „Moduł bez podziału, samouczek” . UNIWERSYTET IOWA Wydział Informatyki . Źródło 9 września 2019 r .

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Fletcher%27s_checksum&oldid=1139370264 ”