您好,欢迎访问三七文档
APAINLESSGUIDETOCRCERRORDETECTIONALGORITHMS[DocumentVersion:3.00][LastUpdated:9/24/96]Chapter1)Preface1.1)AbouttheAuthor&CopyrightEverythingyouwantedtoknowaboutCRCalgorithms,butwereafraidtoaskforfearthaterrorsinyourunderstandingmightbedetected.Author:RossN.WilliamsE-Mail:ross@guest.adelaide.edu.auDate:19August1993Version:3.00FTP:ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt://Company:Rocksoft(tm)PtyLtdSnail:16LerwickAvenue,HazelwoodPark5066,AustraliaFax:+618373-4911(c/-InternodeSystemsPtyLtd)Phone:+618379-9217(10amto10pmAdelaideAustraliatime)Note:RocksoftisatrademarkofRocksoftPtyLtd,AustraliaStatus:Copyright(C)RossWilliams,1993,1994,1995,1996.However,permissionisgrantedtomakeanddistributeverbatimcopiesofthisdocumentprovidedthatthisinformationblockandcopyrightnoticeisincluded.Also,theCcodemodulesincludedinthisdocumentarefullyPUBLICDOMAIN(PD).Thanks:ThankstoJean-loupGailly(jloup@chorus.fr)andMarkAdler(me@quest.jpl.nasa.gov)whobothproofreadthisdocumentandpickedoutlotsofnitsaswellassomebigfatbugs.Csourcestoarereferencedinthisdocument:crcmodel.h(0KB)crcmodel.c(0KB)crctable.c(0KB)1.2)AbstractThisdocumentexplainsCRCs(CyclicRedundancyCodes)andtheirtable-drivenimplementationsinfull,precisedetail.MuchoftheliteratureonCRCs,andinparticularontheirtable-drivenimplementations,isalittleobscure(oratleastseemssotome).Thisdocumentisanattempttoprovideaclearandsimpleno-nonsenseexplanationofCRCsandtoabsolutelynaildowneverydetailoftheoperationoftheirhigh-speedimplementations.Inadditiontothis,thisdocumentpresentsaparameterizedmodelCRCalgorithmcalledtheRocksoft^tmModelCRCAlgorithm.ThemodelalgorithmcanbeparameterizedtobehavelikemostoftheCRCimplementationsaround,andsoactsasagoodreferencefordescribingparticularalgorithms.Alow-speedimplementationofthemodelCRCalgorithmisprovidedintheCprogramminglanguage.Lastlythereisasectiongivingtwoformsofhigh-speedtabledrivenimplementations,andprovidingaprogramthatgeneratesCRClookuptables.Chapter2)Introduction:ErrorDetectionTheaimofanerrordetectiontechniqueistoenablethereceiverofamessagetransmittedthroughanoisy(error-introducing)channeltodeterminewhetherthemessagehasbeencorrupted.Todothis,thetransmitterconstructsavalue(calledachecksum)thatisafunctionofthemessage,andappendsittothemessage.Thereceivercanthenusethesamefunctiontocalculatethechecksumofthereceivedmessageandcompareitwiththeappendedchecksumtoseeifthemessagewascorrectlyreceived.Forexample,ifwechoseachecksumfunctionwhichwassimplythesumofthebytesinthemessagemod256(i.e.modulo256),thenitmightgosomethingasfollows.Allnumbersareindecimal.Message:6234Messagewithchecksum:623433Messageaftertransmission:627433Intheabove,thesecondbyteofthemessagewascorruptedfrom23to27bythecommunicationschannel.However,thereceivercandetectthisbycomparingthetransmittedchecksum(33)withthecomputerchecksumof37(6+27+4).Ifthechecksumitselfiscorrupted,acorrectlytransmittedmessagemightbeincorrectlyidentifiedasacorruptedone.However,thisisasafe-sidefailure.Adangerous-sidefailureoccurswherethemessageand/orchecksumiscorruptedinamannerthatresultsinatransmissionthatisinternallyconsistent.Unfortunately,thispossibilityiscompletelyunavoidableandthebestthatcanbedoneistominimizeitsprobabilitybyincreasingtheamountofinformationinthechecksum(e.g.wideningthechecksumfromonebytetotwobytes).Othererrordetectiontechniquesexistthatinvolveperformingcomplextransformationsonthemessagetoinjectitwithredundantinformation.However,thisdocumentaddressesonlyCRCalgorithms,whichfallintotheclassoferrordetectionalgorithmsthatleavethedataintactandappendachecksumontheend.i.e.:originalintactmessagechecksumChapter3)TheNeedForComplexityInthechecksumexampleintheprevioussection,wesawhowacorruptedmessagewasdetectedusingachecksumalgorithmthatsimplysumsthebytesinthemessagemod256:Message:6234Messagewithchecksum:623433Messageaftertransmission:627433Aproblemwiththisalgorithmisthatitistoosimple.Ifanumberofrandomcorruptionsoccur,thereisa1in256chancethattheywillnotbedetected.Forexample:Message:6234Messagewithchecksum:623433Messageaftertransmission:820533Tostrengthenthechecksum,wecouldchangefroman8-bitregistertoa16-bitregister(i.e.sumthebytesmod65536insteadofmod256)soastoapparentlyreducetheprobabilityoffailurefrom1/256to1/65536.Whilebasicallyagoodidea,itfailsinthiscasebecausetheformulausedisnotsufficientlyrandom;withasimplesummingformula,eachincomingbyteaffectsroughlyonlyonebyteofthesummingregisternomatterhowwideitis.Forexample,inthesecondexampleabove,thesummingregistercouldbeaMegabytewide,andtheerrorwouldstillgoundetected.Thisproblemcanonlybesolvedbyreplacingthesimplesummingformulawithamoresophisticatedformulathatcauseseachincomingbytetohaveaneffectontheentirechecksumregister.Thus,weseethatatleasttwoaspectsarerequiredtoformastrongchecksumfunction:WIDTHAregisterwidthwideenoughtoprovidealowa-prioriprobabilityoffailure(e.g.32-bitsgivesa1/2^32chanceoffailure).CHAOSAformulathatgiveseachinputbytethepotentialtochangeanynumberofbitsintheregister.Note:Thetermchecksumwaspresumabl
本文标题:A-PAINLESS-GUIDE-TO-CRC-ERROR-DETECTION-ALGORITHMS
链接地址:https://www.777doc.com/doc-7010908 .html