- introduktion på CRC beräkningar
- gratis CRC beräkningsrutiner för nedladdning
Inledning vid CRC-beräkningar
När digitala data lagras eller interfaced kan datakorruption inträffa. Sedan början av datavetenskap har människor tänkt på sätt att hantera denna typ av problem., För seriella data kom de fram till lösningen för att fästa en paritetsbit till varje skickad byte. Denna enkla detekteringsmekanism fungerar om ett udda antal bitar i en byte ändras, men ett jämnt antal falska bitar i en byte kommer inte att detekteras av paritetskontrollen. För att övervinna detta problem har människor sökt efter matematiska ljudmekanismer för att upptäcka flera falska bitar. CRC-beräkningen eller den cykliska redundanskontrollen var resultatet av detta. Numera används CRC-beräkningar i alla typer av kommunikation. Alla paket som skickas via en nätverksanslutning kontrolleras med en CRC., Även varje datablock på hårddisken har ett CRC-värde kopplat till det. Modern datorvärld kan inte göra utan dessa CRC beräkning. Så låt oss se varför de används så mycket. Svaret är enkelt, de är kraftfulla, upptäcker många typer av fel och är extremt snabba att beräkna speciellt när dedikerade hårdvaruchips används.
man kanske tror, att med ett kontrollsumma kan ersätta korrekta CRC-beräkningar. Det är säkert lättare att beräkna ett kontrollsumma, men kontrollsummor hittar inte alla fel. Låt oss ta ett exempel sträng och beräkna en byte kontrollsumma., Exempelsträngen är” Lammert ” som konverterar till ASCII-värdena . En byte kontrollsumma för denna array kan beräknas genom att lägga till alla värden, än att dela den med 256 och hålla resten. Den resulterande kontrollsumman är 210. Du kan använda räknaren ovan för att kontrollera detta resultat.
i det här exemplet har vi använt en byte lång kontrollsumma som ger oss 256 olika värden. Med hjälp av en två byte kontrollsumma kommer att resultera i 65,536 möjliga olika kontrollsumma värden och när en fyra byte Värde används finns det mer än fyra miljarder möjliga värden., Vi kan dra slutsatsen att med en fyra byte kontrollsumma är chansen att vi av misstag inte upptäcker ett fel mindre än 1 till 4 miljarder. Verkar ganska bra, men det här är bara teori. I praktiken ändras inte bitar rent slumpmässigt under kommunikationen. De misslyckas ofta i utbrott, eller på grund av elektriska spikar. Låt oss anta att i vårt exempel array är den lägsta signifikanta biten av tecknet ” L ”inställd, och den lägsta signifikanta biten av tecknet” a ” förloras under kommunikationen. Mottagaren kommer än att se matrisen som representerar strängen ” M ’mmert”., Kontrollsumman för den här nya strängen är fortfarande 210, men resultatet är uppenbarligen fel, först efter att två bitar ändrats. Även om vi hade använt en fyra byte lång kontrollsumma skulle vi inte ha upptäckt detta överföringsfel. Så att beräkna ett kontrollsumma kan vara en enkel metod för att upptäcka fel, men ger inte mycket mer skydd än paritetsbiten, oberoende av längden på kontrollsumman.
tanken bakom en kontrollvärdesberäkning är enkel. Använd en funktion F (bval,cval) som matar in en databyte och ett kontrollvärde och matar ut ett omberäknat kontrollvärde., I själva verket kan kontrollsumma beräkningar som beskrivits ovan definieras på detta sätt. Vårt exempel på en byte kontrollsumma kunde ha beräknats med följande funktion (i C-språk) som vi ringer upprepade gånger för varje byte i inmatningssträngen. Det ursprungliga värdet för cval är 0.
int F_chk_8( int bval, int cval ) { retun ( bval + cval ) % 256;}
tanken bakom CRC-beräkningen är att titta på data som ett stort binärt nummer. Detta nummer divideras med ett visst värde och resten av beräkningen kallas CRC., Att dela i CRC-beräkningen ser först ut att kosta mycket datorkraft, men det kan utföras mycket snabbt om vi använder en metod som liknar den som lärdes i skolan. Vi kommer som ett exempel att beräkna resten för tecknet ” m ” – vilket är 1101101 i binär notation – genom att dela den med 19 eller 10011. Observera att 19 är ett udda nummer. Detta är nödvändigt som vi kommer att se längre fram. Se dina skolböcker som den binära beräkningsmetoden här skiljer sig inte mycket från decimalmetoden du lärde dig när du var ung. Det kanske bara ser lite konstigt ut., Även notationer skiljer sig åt mellan länder, men metoden är liknande.
1 0 1 = 5 -------------1 0 0 1 1 / 1 1 0 1 1 0 1 1 0 0 1 1 | | --------- | | 1 0 0 0 0 | 0 0 0 0 0 | --------- | 1 0 0 0 0 1 1 0 0 1 1 --------- 1 1 1 0 = 14 = remainder
med decimalberäkningar kan du snabbt kontrollera att 109 dividerat med 19 ger en kvot på 5 med 14 som resten. Men vad vi också ser i systemet är att varje bit extra för att kontrollera endast kostar en binär jämförelse och i 50% av fallen en binär subtraktion., Du kan enkelt öka antalet bitar av testdatasträngen-till exempel till 56 bitar om vi använder vårt exempelvärde ”Lammert” – och resultatet kan beräknas med 56 binära jämförelser och i genomsnitt 28 binära subtraktioner. Detta kan implementeras i hårdvara direkt med endast mycket få transistorer inblandade. Även mjukvarualgoritmer kan vara mycket effektiva.
för CRC-beräkningar används ingen normal subtraktion, men alla beräkningar görs modulo 2. I den situationen ignorerar du bärbitar och i själva verket kommer subtraktionen att vara lika med en exklusiv eller operation., Det här ser konstigt ut, den resulterande återstoden har ett annat värde,men från en algebraisk synvinkel är funktionaliteten lika. En diskussion om detta skulle behöva universitetsnivå kunskap om algebraisk fältteori och jag antar att de flesta av läsarna inte är intresserade av detta. Vänligen titta i slutet av detta dokument för böcker som diskuterar detta i detalj.
nu har vi en CRC beräkningsmetod som är implementerbar i både hårdvara och mjukvara och har också en mer slumpmässig känsla än att beräkna en vanlig kontrollsumma. Men hur kommer det att fungera i praktiken när en Malm mer bitar är fel?, Om vi väljer divisor-19 i vårt exempel-för att vara ett udda nummer behöver du inte matematik på hög nivå för att se att varje enskilt bitfel kommer att upptäckas. Detta beror på att varje enskilt bitfel kommer att låta utdelningen förändras med en kraft på 2. Om till exempel bit n ändras från 0 till 1, kommer utdelningens värde att öka med 2n. om å andra sidan bit n ändras från 1 till 0, kommer utdelningens värde att minska med 2n. eftersom du inte kan dela upp någon kraft på två med ett udda nummer, kommer resten av CRC-beräkningen att förändras och felet kommer inte att gå obemärkt.,
den andra situationen vi vill upptäcka är när två enstaka bitar ändras i data. Detta kräver viss matematik som kan läsas i Tanenbaums bok som nämns nedan. Du måste välja din divisor mycket noga för att vara säker på att oberoende av avståndet mellan de två fel bitar du alltid kommer att upptäcka dem. Det är känt att de vanliga värdena 0x8005 och 0x1021 i CRC16 och CRC-CCITT-beräkningarna fungerar mycket bra i denna fråga., Observera att andra värden kan eller kanske inte, och du kan inte enkelt beräkna vilket divisor-värde som är lämpligt för att upptäcka två bitfel och som inte är. Lita på omfattande matematisk forskning om denna fråga som gjordes för några decennier sedan av högkvalificerade matematiker och använd de värden som dessa personer erhöll.
dessutom vill vi med vår CRC-beräkning upptäcka alla fel där ett udda antal bitändringar. Detta kan uppnås genom att använda en divisor med ett jämnt antal bitar. Med modulo 2 matematik kan du visa att alla fel med ett udda antal bitar upptäcks., Som jag har sagt tidigare, i modulo 2 Matematik subtraktionsfunktionen ersätts av den exklusiva eller. Det finns fyra möjliga xor-operationer.
0 XOR 0 => 0 even => even0 XOR 1 => 1 odd => odd1 XOR 0 => 1 odd => odd1 XOR 1 => 0 even => even
Vi ser att för alla kombinationer av bitvärden är uttryckets oddhet densamma. När du väljer en divisor med ett jämnt antal bitar som är inställda, är oddheten hos resten lika med utdelningens luddhet. Om utdelningens oddhet ändras på grund av att ett udda antal bitar ändras kommer resten också att förändras., Så alla fel som ändrar ett udda antal bitar kommer att upptäckas av en CRC-beräkning som utförs med en sådan divisor. Du kanske har sett att de vanliga divisorvärdena 0x8005 och 0x1021 faktiskt har ett udda antal bitar, och inte ens som anges här. Detta beror på att inuti algoritmen finns en ”dold” extra bit 216 vilket gör det faktiska använda divisorvärdet 0x18005 och 0x11021 inuti algoritmen.,
sist men inte minst vill vi upptäcka alla sprängfel med vår CRC-beräkning med en maximal längd som ska detekteras och alla längre sprängfel som ska upptäckas med stor sannolikhet. Ett sprängfel är ganska vanligt i kommunikation. Det är den typ av fel som uppstår på grund av blixtnedslag, reläbyte etc. var under en liten period är alla bitar inställda på en., För att verkligen förstå detta måste du också ha viss kunskap om modulo 2 algebra, så vänligen acceptera att med en 16 bit divisor kommer du att kunna upptäcka alla skurar med en maximal längd på 16 bitar, och alla längre skurar med minst 99.997% säkerhet.
i ett rent matematiskt tillvägagångssätt skrivs CRC-beräkningen som polynomberäkningar. Divisorvärdet beskrivs oftast inte som ett binärt tal, men ett polynom av viss ordning. I det normala livet används vissa polynom oftare än andra., De tre som används i online CRC-beräkning på denna sida är 16-bitars bred CRC16 och CRC-CCITT och 32 bitar stort CRC32. Den senare används förmodligen mest nu, för bland annat är det CRC-generatorn för all nätverkstrafikverifiering och validering.
för alla tre typerna av CRC-beräkningar har jag ett gratis programbibliotek tillgängligt. Testprogrammet kan användas direkt för att testa filer eller strängar. Du kan också titta på källkoderna och integrera dessa CRC rutiner i ditt eget program., Var medveten om initieringsvärdena för CRC-beräkningen och eventuell nödvändig efterbehandling som att vända bitar. Om du inte gör det kan du få olika resultat än andra CRC-implementeringar. Allt detta före och efterbearbetning görs i exemplet programmet så det bör inte vara svårt att göra din egen implementering fungerar. Ett vanligt använt test är att beräkna CRC-värdet för ASCII-strängen ”123456789”., Om resultatet av din rutin matchar resultatet av testprogrammet eller resultatet på denna webbplats fungerar implementeringen och är kompatibel med de flesta andra implementeringar.
precis som referens fungerar polynom för de vanligaste CRC-beräkningarna. Kom ihåg att polynomets högsta orderperiod (x16 eller x32) inte är närvarande i binärnummerrepresentationen, men underförstått av algoritmen själv.,
| litteratur | ||
| 2002 | datanätverk, som beskriver vanliga nätverkssystem och teorin och algoritmerna bakom deras genomförande. | Andrew S. Tanenbaum |
| olika | konsten att datorprogrammering är den viktigaste referensen för semi-numeriska algoritmer. Polynomberäkningar beskrivs på djupet. En viss nivå av matematik är nödvändig för att fullt ut förstå det. | Donald E. Knuth |
| – | DNP 3.,0, eller distributed network protocol är ett kommunikationsprotokoll som är utformat för användning mellan understationsdatorer, rtus remote terminal-enheter, IEDs intelligenta elektroniska enheter och masterstationer för elverktygsindustrin. Det används nu också i välbekanta industrier som avloppsvattenrening, transport och olje-och gasindustrin. | DNP användargrupp |
Lämna ett svar