Fletcherin tarkistussumma

Fletcherin tarkistus summa (käännetty "Fletcherin tarkistussummaksi", myös Fletcherin tarkistussummaksi tai Fletcherin algoritmiksi ) on virheiden havaitsemismenetelmä John G. Fletcherin (1934–2012) vuonna 1982 käyttöön ottaman tarkistussumman muodossa . Menetelmää voidaan käyttää virheiden havaitsemiseen esimerkiksi digitaalisessa tiedonsiirrossa . Se perustuu siihen, että viestin yksittäiset bitit paitsi lasketaan yhteen, myös painotetaan niiden sijainnista riippuen. Algoritmi edustaa siis kompromissia hitaamman, mutta herkemman syklisen redundanssitarkistuksen (CRC) ja virhealttiiden menettelyjen, kuten yksinkertaisen tarkistussumman tai vertikaalisen redundanssitarkistuksen, välillä.Fletcherin tarkistussummaa käytetään erilaisissa verkkoprotokollissa ja tiedostojärjestelmissä .

Algoritmi

Binaarinen lähetetty sanoma on jaettu osiin pituus , kukin bitti muodostaen lohko . Viimeinen lohko täytetään algoritmin ajaksi ja jokainen lohko tulkitaan allekirjoittamattomana kokonaislukuna . Olkoon lohkojen lukumäärä . Tarkastusarvo koostuu kahdesta eri summasta: Ensimmäinen ( ) tiivistää kaikki lohkot askel askeleelta, toinen ( ) on kaikkien ensimmäisen summan välitulosten summa. Ensimmäinen lohko syötetään useita kertoja , viimeinen lohko vain kerran. Jos bittiä käännetään ylösalaisin tai kaksi eri arvolohkoa vaihdetaan lähetyshäiriön takia, testiarvo muuttuu normaalisti: Virhe havaitaan. ${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle {\ text {length}}}$${\ displaystyle {\ text {sum}} _ {1}}$${\ displaystyle {\ text {sum}} _ {2}}$${\ displaystyle {\ text {length}}}$${\ displaystyle {\ text {sum}} _ {2}}$

Koska testiarvon pitäisi voida lähettää kiinteänä määränä bittejä (yleensä ) sanoman pituudesta riippumatta , molemmat summat lasketaan viimeisenä moduulina ja integroidaan sitten viestiin. Yleensä tai valitaan. Jälkimmäinen on parempi, huolimatta hieman monimutkaisemmasta laskutoimituksesta, koska se on kooltaan vertailukelpoinen, toisin kuin 2 - binäärisen järjestelmän perusta - jaettava . Tuloksen kannalta ei ole merkitystä, käytetäänkö modulo-operaatiota jokaisen lisäyksen jälkeen vai lopussa. Jotta voidaan välttää ylivuoto , se tapahtuu yhdessä toteutuksessa laskennan aikana. ${\ displaystyle 2 \ cdot K}$ ${\ displaystyle M}$${\ displaystyle M = 2 ^ {K}}$${\ displaystyle M = 2 ^ {K} -1}$${\ displaystyle 2 ^ {K} -1}$${\ displaystyle 2 ^ {K}}$

Fletcherin tarkistussumman mahdollisten testiarvojen määrä on . Jos oletetaan, että viesti on riittävän pitkä, todennäköisyys sorretun viestin tarkistusarvolle pienenee . Periaatteessa voidaan valita mikä tahansa luonnollinen luku ; algoritmia kutsutaan vastaavasti Fletcher- . Fletcher-16 ja Fletcher-32 ovat yleisiä, joissakin tapauksissa myös Fletcher-8.${\ displaystyle M ^ {2}}$${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle 2 \ cdot K}$

Näytelaskenta

Jos sanoma "Wikipedia" lähetetään binäärisenä ASCII-muodossa , taulukossa esitetty laskelma suoritetaan Fletcher-16: lle . Jos summan välitulos on suurempi tai yhtä suuri kuin 255, käytetään moduulia, joka on esitetty tässä muodossa . ${\ displaystyle M = 255}$${\ displaystyle \ equiv}$

viesti	W.	i	k	i	s	e	d	i	a	Tulos
binaarinen edustus	01010111	01101001	01101011	01101001	01110000	01100101	01100100	01101001	01100001
desimaaliarvo	87	105	107	105	112	101	100	105	97
${\ displaystyle {\ text {sum}} _ {1}}$	87	192	299 44${\ displaystyle \ equiv}$	149	261 6${\ displaystyle \ equiv}$	107	207	312 57${\ displaystyle \ equiv}$	154	154
${\ displaystyle {\ text {sum}} _ {2}}$	87	279 24${\ displaystyle \ equiv}$	68	217	223	330 75${\ displaystyle \ equiv}$	282 27${\ displaystyle \ equiv}$	84	238	238

Pseudokoodi

Alla on Fletcher-16: n pseudokoodi ilman optimointia. Molemmat summat palautetaan peräkkäin testiarvona. ${\ displaystyle M = 255}$

Fletcher_16 (data)
Input: Array data von 8-Bit-Integern
Output: 16-Bit-Prüfsumme zu data

sum1 := 0
sum2 := 0
for i := 0 to length (data) do
    sum1 := (sum1 + data[i]) modulo 255
    sum2 := (sum2 + sum1) modulo 255
endfor
checksum := sum1 gefolgt von sum2
return checksum

vaihtoehtoja

Vaihtoehdossa, joka on lähempänä Fletcherin alkuperäistä algoritmia, sanoman loppuun liitetään kaksi pituista testilohkoa, jotka valitaan siten, että uuden, laajennetun viestin testi-arvon molemmat summat ovat nollia. Tätä varten kahden summan ja on alustavasti laskenut kuin ennenkin. Arvo määritetään sitten ensimmäiselle testilohkolle ja toiselle . Pian Fletcherin julkaisun jälkeen Betty Salzberg osoitti, että kahden peräkkäisen testilohkon sijainti voidaan valita halutuksi sanomassa testausominaisuuksia heikentämättä. Jos lohkojen on oltava paikoillaan tai , niiden arvo on valittava ja , kussakin tapauksessa modulo . Lohkojen lukumäärä vastaa alkuperäistä viestiä. Itse asiassa nämä kaksi lohkoa voivat olla vapaasti valittavissa olevissa paikoissa ja niin kauan kuin määrä ja ovat suhteellisen alkuluokan .${\ displaystyle K}$${\ displaystyle {\ text {sum}} _ {1}}$${\ displaystyle {\ text {sum}} _ {2}}$${\ displaystyle - {\ text {sum}} _ {1} - {\ text {sum}} _ {2} {\ pmod {M}}}$${\ displaystyle {\ text {sum}} _ {2}}$${\ displaystyle n}$${\ displaystyle n + 1}$${\ displaystyle ({\ text {length}} - n) \ cdot {\ text {sum}} _ {1} - {\ text {sum}} _ {2}}$${\ displaystyle ({\ text {length}} - (n-1)) \ cdot (- {\ text {sum}} _ {1}) + {\ text {sum}} _ {2}}$${\ displaystyle M}$${\ displaystyle {\ text {length}}}$${\ displaystyle i}$${\ displaystyle j}$ ${\ displaystyle | ij |}$${\ displaystyle M}$

Keith Sklower kehitti rekursio, joka käsittelee kaksi lohkoa kerralla ja tuottaa saman tarkistusarvon kuin Fletcherin tarkistussumma. Lisäksi voi tietyissä vika malleissa olla edullista tarkistaa arvo perävaunun sijaan, kuten useimmissa verkkoprotokollia , että otsikossa mahtuu.

optimointi

Jos summat tallennetaan enemmän kuin bittiä, moduulitoimintaa ei tarvitse suorittaa jokaisen lisäyksen jälkeen, vaan vain silloin, kun muuttuja uhkaa ylivuotoa. Pahimmassa tapauksessa on oletettu, eli viestin, jossa kussakin lohkossa on suurin mahdollinen arvo, jotta voidaan määrittää ylemmän sidottu lukumäärälle lisäyksiä ilman ylivuotoa. Jos molemmilla summilla on sama tietotyyppi , tämä tehdään ensin . Täytäntöönpanossa Fletcher-16 ja ja käyttämällä unsigned 16-bittisiä kokonaislukuja .${\ displaystyle K}$ ${\ displaystyle B_ {u}}$${\ displaystyle {\ text {sum}} _ {2}}$${\ displaystyle K = 8}$${\ displaystyle M = 255}$${\ displaystyle B_ {u} = 21}$

Lisäksi modulo-operaatio voidaan korvata bittiviisaisilla operaattoreilla . Jos , sen sijaan että (huomattava, että ohjelmointikieli C ) , on riittävä , yhden komplementti aritmeettinen voitaisiin käyttää, jossa lisäksi on carry (end-around carry) vaadita tässä aritmeettinen tuottaa sopivan tuloksen. Nykypäivän laitteisto käyttää kuitenkin melkein yksinomaan kahden komplementtiaritmeettistä ; tässä tapauksessa voidaan jäljitellä siirtämisen lisäystä edellyttäen, että käytettyyn tietotyyppiin mahtuu enemmän kuin bittiä. Tarkistussummia koskevassa kirjallisuudessa yleensä ja myös Fletcher, vastaavasti usein viitataan yhden ja kahden täydennysversioon.${\ displaystyle M = 2 ^ {K}}$x & (M-1)x % M${\ displaystyle M = 2 ^ {K} -1}$(x & (M-1)) + (x >> K)${\ displaystyle K}$${\ displaystyle M = 2 ^ {K} -1}$${\ displaystyle M = 2 ^ {K}}$

Fletcherin tarkistussumma voidaan rinnastaa sekä vektoroida . Algoritmia voidaan myös nopeuttaa yleisillä optimointimenetelmillä , erityisesti silmukan purkamisella .

tarina

John Fletcher kehitti algoritmin Lawrence Livermoren kansallisessa laboratoriossa 1970-luvun lopulla . Tammikuussa 1982 IEEE Communications Society julkaisi Fletcherin artikkelin tarkistussummasta ja sen ominaisuuksista IEEE Transactions on Communications -sovelluksessa . Tässä hän perustelee kehittäminen aritmeettinen tarkistussumma siihen, että tietokoneet on suunniteltu laskutoimituksia pikemminkin kuin polynomi jako , kuten vaaditaan syklisen redundanssitarkistuksen. Fletcher kuvasi testiarvoa ei kahden, vaan minkä tahansa määrän summien koostumuksena, jolloin ensimmäinen lasketaan ja kukin lisäsumma laskee yhteen edellisen välitulokset. Useamman kuin kahden summan käyttö ei kuitenkaan paranna algoritmia riittävästi hidastuksen takaamiseksi.${\ displaystyle {\ text {sum}} _ {1}}$

Fletcherin algoritmin mukautettuja muunnelmia käytetään mm . ISO- verkkoprotokollastandardin neljännessä kerroksessa (kuljetus) ja IS-IS- protokollassa. J. Zweig ja C. Partridge ehdottivat vuonna 1990 TCP: n laajentamista, jotta Fletcherin tarkistussummaa voitaisiin käyttää. Tällä laajennuksella on ollut historiallinen asema vuodesta 2011 lähtien . Tarkistussummaa käytetään sekä vuonna 2006 käyttöönotetussa ZFS- tiedostojärjestelmässä että vuonna 2016 käyttöönotetussa Apple File System -järjestelmässä .

Vuonna 1995, Mark Adler ja Adler-32 on muunnelma Fletcher-32 ennen, modulo 65521 (suurimmista prime alle 2 ¹⁶ ) odotetaan.

Ominaisuudet ja vertailu muihin menetelmiin

Jos tarkistusarvon tavujen lukumäärä on sama, Fletcherin tarkistussummalle suoritetaan virheiden havaitsemisessa hyvin toteutettu syklinen redundanssitarkistus (CRC). Laskenta voidaan aloittaa ennen kuin viesti on valmis, koska suoria riippuvuuksia ei ole . Jos yksittäisiä lohkoja muutetaan sen jälkeen, kun tarkistussumma on jo laskettu, se voidaan päivittää pääsemättä muuttumattomiin lohkoihin.${\ displaystyle {\ text {length}}}$

Seuraavat ominaisuudet liittyvät aina algoritmiin . Fletcherin tarkistus summa havaitsee kaikki purskevirheet pituuteen saakka ; se on altis purskevirheille, jotka kääntävät vain yhden lohkon yhdeksi ainoasta nollasta tai päinvastoin, koska modulo nämä kaksi lohkoa ovat vastaavia. Jos tämä erityinen virhetyyppi jätetään huomioimatta, kaikki nippuvirheet tunnistetaan pituuteen saakka . Enintään bittipituisille viesteille menetelmän Hamming-etäisyys on pidemmille viesteille . Fletcher-16 ei enää tunnista kaikkia kaksibittisiä virheitä viestin pituudesta 2056 bittiä, kun taas kahden virheen välinen, enintään 65 535 bitin etäisyys riittää sopivalle CRC: lle, jonka tarkistusarvo on yhtä pitkä. Fletcher-16: n toteutuksen heikkous paljastuu tässä, koska etäisyyden on tässä oltava pienempi tai yhtä suuri kuin 16 bittiä.${\ displaystyle M = 2 ^ {K} -1}$${\ displaystyle K}$${\ displaystyle 2 ^ {K} -1}$${\ displaystyle 2 \ cdot K}$${\ displaystyle K \ cdot M = K \ cdot (2 ^ {K} -1)}$${\ displaystyle h = 3}$${\ displaystyle h = 2}$${\ displaystyle M = 256}$

Fletcherin tarkistussumma ei tunnista viestiin liitettyjä vääriä nollia, koska tämä tarkoittaa, että summat eivät enää muutu. Tämä voidaan estää joko tietämällä viestin pituus etukäteen tai ilmoittamalla vastaanottajalle siinä.

Vaikka Adler-32: n kanssa alkuluvun miehitys jakaa mahdolliset testiarvot paremmin, niitä on kokonaisuudessaan vähemmän, joten monimutkaisempi laskelma testaa melkein aina huonommin kuin Fletcher-32.${\ displaystyle M}$

Koska tarkistusarvossa on sama määrä bittejä, Fletcherin tarkistussumma on siten parempi kuin yksinkertaiset algoritmit, kuten pystysuora redundanssitarkistus , yksinkertainen summa tai XOR- tarkistussumma ja Adlerin tarkistussumma. Jos CRC voidaan toteuttaa, se on suositeltava.

kirjallisuus

• John G.Fletcher: Aritmeettinen tarkistussumma sarjaliikenteelle . Julkaisussa: IEEE Transactions on Communications . Osa 30, 1. painos, 1982, doi: 10.1109 / TCOM.1982.1095369 , s. 247-252.
• Anastase Nakassis: Fletcherin virheenhavaitsemisalgoritmi: Kuinka toteuttaa se tehokkaasti ja kuinka välttää yleisimmät karhut. Julkaisussa: Computer Communication Review . Osa 18, 5. painos, 1988, doi: 10.1145 / 53644.53648 , s. 63-88.
• John Kodis: Fletcherin tarkistussumma: Virheenkorjaus murto-osalla kustannuksista . Julkaisussa: Dr. Dobb's Journal . Osa 17, numero 5, 1992, s.32.
• Theresa C.Maxino, Philip J.Koopman: Tarkistussummien tehokkuus sulautetuille ohjausverkoille . Julkaisussa: IEEE Transactions on Luotettava ja Suojattu tietojenkäsittely . Osa 6, painos 1, 2009, doi: 10.1109 / TDSC.2007.70216 , erityisesti luku 3.4 (PDF; 676 kB).

nettilinkit

• J. Zweig, C.Partridge: TCP Alternate Checksum Options . RFC 1146, 1990.
• Fletcher-16: n käyttöönotto useilla ohjelmointikielillä (englanti)
• Peter Kankowski: Hash-toiminnot: Empiirinen vertailu . 2009.

Yksittäiset todisteet

1. ↑ Muistoissa John Fletcher . Lawrence Livermoren kansallinen laboratorio, käyty 16. maaliskuuta 2017.
2. B ^{a b c d e} John G.Fletcher: Sarjalähetysten aritmeettinen tarkistus summa . 1982, s. 248.
3. ↑ Anastase Nakassis: Fletcherin virheenhavaitsemisalgoritmi: Kuinka se voidaan toteuttaa tehokkaasti ja kuinka välttää yleisimmät sudenkuopat. 1988, s. 71f.
4. ↑ Anastase Nakassis: Fletcherin virheenhavaitsemisalgoritmi: Kuinka se voidaan toteuttaa tehokkaasti ja miten voidaan välttää yleisimmät sudenkuopat. 1988, s. 76f.
5. ^ ^{A b c} Theresa C. Maxino, Philip J. Koopman: Tarkistussummien tehokkuus sulautetuille ohjausverkoille . 2009, s.69.
6. ^ Betty Salzberg: Muutos Fletcherin tarkistussummasta . Julkaisussa: IEEE Transactions on Communications . Osa 31, 2. painos, 1983, doi: 10.1109 / TCOM.1983.1095789 , s.296 .
7. ↑ ^{a b} Anastase Nakassis: Fletcherin virheenhavaitsemisalgoritmi: Kuinka se voidaan toteuttaa tehokkaasti ja miten voidaan välttää yleisimmät sudenkuopat. 1988, s. 65.
8. ^ Keith Sklower: OSI-tarkistussumman laskennan tehokkuuden parantaminen . Julkaisussa: Computer Communication Review . Osa 19, 5. painos, 1989, doi: 10.1145 / 74681.74684 , s. 32–43 (PDF; 524 kB).
9. ↑ Jonathan Stone, Michael Greenwald, Craig Partridge, James Hughes: Tarkistussummien ja CRC: n suorituskyky yli todellisen datan . Julkaisussa: IEEE / ACM Transactions on Networking . Osa 6, painos 5, 1998, doi: 10.1109 / 90.731187 .
10. ↑ Anastase Nakassis: Fletcherin virheenhavaitsemisalgoritmi: Kuinka se voidaan toteuttaa tehokkaasti ja kuinka välttää yleisimmät sudenkuopat. 1988, s. 68, johdannaisten osalta katso liite A, s. 76 jj.
11. ^ Douglas W. Jones: Moduuli ilman jakoa, opetusohjelma . 2001.
12. ↑ Anastase Nakassis: Fletcherin virheenhavaitsemisalgoritmi: Kuinka se voidaan toteuttaa tehokkaasti ja kuinka välttää yleisimmät sudenkuopat. 1988, liite D, s. 84 j.
13. ↑ John Kodis: Fletcherin tarkistussumma: Virheenkorjaus murto-osalla kustannuksista . 1992, kirjoita Fletcherin luku.
14. ↑ Anastase Nakassis: Fletcherin virheenhavaitsemisalgoritmi: Kuinka se voidaan toteuttaa tehokkaasti ja kuinka välttää yleisimmät sudenkuopat. 1988, s. 70, s. 72.
15. ↑ Katso käytettävä koodi Gerard J.Holzmannista: Tietokoneprotokollien suunnittelu ja validointi . Prentice Hall, 1991, ISBN 0-13-539925-4 , s.63 .
16. ^ Adrian Farrel: Internet ja sen protokollat: vertaileva lähestymistapa . Morgan Kaufmann, San Francisco 2004, ISBN 155860913X , s.181 ( rajoitettu esikatselu Google- teoshaulla ).
17. ^ J. Zweig, C.Partridge: TCP Alternate Checksum Options . RFC 1146, 1990.
18. ^ L. Eggert: Siirtämättömien TCP-laajennusten RFC 1072, RFC 1106, RFC 1110, RFC 1145, RFC 1146, RFC 1379, RFC 1644 ja RFC 1693 siirtäminen historialliseen tilaan . RFC 6247, 2011.
19. ↑ James Guilford, Vinodh Gopal: Fletcherin tarkistussummien nopea laskenta . Intel Data Center Group, 14. tammikuuta 2016, Johdanto.
20. ↑ Katso käytettävä koodi Matthias Luft: ERNW Whitepaper 65 - APFS Internals for Forensic Analysis . 16. huhtikuuta 2018, s. 7f.
21. ↑ Theresa C.Maxino, Philip J.Koopman: Tarkistussummien tehokkuus sulautetuille ohjausverkoille . 2009, s.67.
22. ↑ Anastase Nakassis: Fletcherin virheenhavaitsemisalgoritmi: Kuinka se voidaan toteuttaa tehokkaasti ja miten voidaan välttää yleisimmät sudenkuopat. 1988, s. 65, kaavojen ja niiden johdannaisten osalta katso liite B, s. 80 jj.
23. ↑ Theresa C.Maxino, Philip J.Koopman: Tarkistussummien tehokkuus sulautetuille ohjausverkoille . 2009, s. 64f.
24. ↑ Theresa C.Maxino, Philip J.Koopman: Tarkistussummien tehokkuus sulautetuille ohjausverkoille . 2009, s.65.
25. ^ John G.Fletcher: Aritmeettinen tarkistus summa sarjaliikenteelle . 1982, s. 251.
26. ↑ Anastase Nakassis: Fletcherin virheenhavaitsemisalgoritmi: Kuinka se voidaan toteuttaa tehokkaasti ja kuinka välttää yleisimmät sudenkuopat. 1988, s. 73.
27. ↑ Theresa C.Maxino, Philip J.Koopman: Tarkistussummien tehokkuus sulautetuille ohjausverkoille . 2009, s. 70.

Tämä artikkeli lisättiin tässä versiossa loistavien artikkelien luetteloon 1. heinäkuuta 2017 .