数据通信与网络09-错误检测与纠正-3

第九章错误检测与纠正Chapter9ERRORDETECTIONANDCORRECTION9.1Typesoferrors9.2Errordetection9.3Errorcorrection9.4SummaryContentsIntroductionAnytimedataaretransmittedfromonenodetothenext,theycanbecomecorruptedinpassage.Someapplicationsrequirethaterrorsbedetectedandcorrected.Errordetectionandcorrectionareimplementedeitheratthe

datalinklayer

orthe

transportlayer

oftheOSImodel.9.1TypesofErrorsWheneverbitsflowfromonepointtoanother,theyaresubjecttounpredictablechangesbecauseofinterference.9.1.1Single-biterrorAsingle-biterroriswhenonlyonebitinthedataunithaschanged.Inasingle-biterror,a0ischangedtoa1ora1toaMultiple-BitErrorAmultiple-biterroriswhentwoormore

nonconsecutive(不连续的)

bitsinthedataunithavechanged.9.1.3BursterrorAbursterrormeansthattwoormore

consecutive(连续的)

bitsinthedataunithavechanged.突发差错大多发生在串行传输时。～通常噪声持续时间比位持续时间长，这就是说当噪声影响数据时就会影响一组比特。 影响的位数依赖于数据速率和噪声持续时间。例如，如果发送数据速率是1Kbps,1/100s的噪声将影响10个比特;如果速率是1Mbps，同样的噪声影响10000个比特。9.1.3Bursterror9.2ErrorDetection(错误检测)Inerrordetection,wearelookingonlytoseeifanyerrorhasoccurred.Theanswerisasimpleyesorno.Wearenoteveninterestedinthenumberoferrors.

Asingle-biterroristhesameforusasabursterror.9.2.1RedundancyThecentralconceptindetectingorcorrectingerrorsisredundancy.Tobeabletodetectorcorrecterrors,weneedtosendsomeextrabitswithourdata.

Theseredundantbitsareaddedbythesenderandremovedbythereceiver.

Theirpresenceallowsthereceivertodetectorcorrectcorruptedbits.Usingredundantbitstochecktheaccuracyofadataunit9.2.1RedundancyFourtypesofredundancychecksareusedindatacommunications.VRC(VerticalRedundancyCheck,垂直冗余校验)LRC(LongitudinalRedundancy,纵向冗余校验)CRC(CyclicalRedundancyCheck,循环冗余校验)Checksum(校验和)VRC、LRC、CRC在物理层实现，数据链路层使用；校验和应用于更高的OSI层次。9.2.1Redundancy9.2.2VRC(VerticalRedundancyCheck)VRC(垂直冗余校验)oftencalledparitycheck(奇偶校验):

oddparityorevenparityInthistechnique,aredundantbit,calledaparitybit(校验位),isappendedtoeverydataunitsothatthetotalnumberof1sintheunitbecomeeitherevenorodd.VRCcandetectall

single-biterrors. Itcandetectmultiple-bitorbursterroronlyifthetotalnumberoferrorsisodd.EvenparityVRCconcept9.2.2VRC(VerticalRedundancyCheck)9.2.3LRC(LongitudinalRedundancyCheck)Abetterapproachisthe

two-dimensional

paritycheck.

Inthismethod,thedatawordisorganizedinatable(rowsandcolumns).在纵向冗余校验中，将一个数据块划分成几行，并将校验位组成的冗余行添加到整个数据块中。LRC(LongitudinalRedundancy)9.2.3LRC(LongitudinalRedundancy)(纵向冗余校验码)(dataunit)9.2.3LRC(LongitudinalRedundancy)LRCenormouslyincreasesthelikelihoodofdetectingmultiple-bitandbursterrors.However,thereisonepatternoferrorsthatremainselusive.

Iftwobitsinonedataunitaredamagedandtwobitsinexactlythesamepositionsinanotherdataunitarealsodamaged,theLRCcheckerwillnotdetectanerror.

例如有两个数据单元11110000以及11000011。如果在每个数据单元的第一个和最后一个位置的比特被改变，将数据单元变成01110001和01000010，那么LRC就无法检测出这些差错。ThethirdandmostpowerfuloftheredundancycheckingtechniquesistheCRC.UnlikeVRCandLRCwhichbasedonaddition,CRCisbasedon

binarydivision.在CRC中，在数据单元末尾附加一串冗余比特，称作循环冗余校验码或循环冗余校验余数，使得整个数据单元可以被另一个预定的二进制数所整除。到达目的地后，用同一个数去除整个数据单元。如果不产生余数，则认为数据单元是完整正确的，从而接受该数据单元；有余数意味着数据单元被破坏，因此拒绝接受该数据单元。9.2.4CyclicRedundancyCheck(CRC)9.2.4CyclicRedundancyCheck(CRC)CRCgeneratorandchecker在循环冗余校验中使用的冗余比特是将数据单元除以一个预定的除数后产生的，余数就是循环冗余校验码(CRC码)。只有以下两个特性的CRC码才是合法的:

必须比除数至少少一位；在附加到数据串末尾后必须形成可以被除数整除的比特序列。9.2.4CyclicRedundancyCheck(CRC)TheprocessofderivingtheCRC:Step1:astringofnbits0sisappendedtotheendofthedataunit.

(Thenumbernisonelessthanthenumberofbitsinthepredetermineddivisor,whichisn+1bits.)Step2:thenewlyelongateddataunitisdividedbythedivisorusingaprocesscalledbinarydivision.

(TheremainderresultingfromthisdivisionisCRC.)Step3:TheCRCofnbitsderivedinstep2replacestheappended0sattheendofthedataunit.9.2.4CyclicRedundancyCheck(CRC)CRCwilldetectallpossibleerrorsexceptthosethatchangethebitvalueofablockofcodebyexactlythevalueofthedivisor.PopularCRCdivisorsuse13,17,and33bits,bringingthelikelihoodofanundetectederroralmosttozero.ReliabilityACRCgeneratorusesmodlo-2division.TheCRCGeneratorCRCCheckerPolynomials(多项式)TheCRCgenerator(thedivisor)ismostoftenrepresentedasanalgebraicpolynomial(代数多项式).多项式所需具备的(基本)性质：

1、不被x除尽；

2、可被x+1除尽。第一个条件保证检测出所有长度等于多项式阶数的突发差错；第二个条件保证检测出所有影响奇数位的突发差错。Polynomials(多项式)高性能多项式所需具备的特性：

1、至少包含两项；

2、x0项的系数应该是1；

3、应该不能整除xt+1(t为2到n-1之间)；4、应该有因子x+1。※ApolynomialrepresentingadivisorPolynomials(多项式)Therelationshipofapolynomialtoitscorrespondingbinaryrepresentation:Polynomials(多项式)ThestandardpolynomialusedbypopularprotocolforCRCgenerationareshownbelow.Thenumbers12,16and32refertothesizeoftheCRCremainder.TheCRCdivisorare13,17and33bits,respectively.Polynomials(多项式)StandardpolynomialsusedbypopularprotocolsCRC性能可检测出所有影响奇数位的突发差错；可以检测出所有长度小于或等于多项式阶数的突发差错；可以以非常高的概率检测出长度大于多项式阶数的突发差错。Theerrordetectionmethodusedbythe

higherlayerprotocols

iscalledchecksum.Checksumisbasedontheconceptofredundancyalso.9.2.5Checksum(校验和)ChecksumGeneratorThechecksumgeneratorsubdividesthedataintoequalsegmentsofnbits.Thesesegmentsareaddedtogetherusingone’scomplementarithmetic(反码算法).

结果仍然为n比特。Thatsumisthencomplemented(取反)andappendedtotheendoftheoriginaldataunitasredundancybits,calledthechecksumfiled.

正数的反码与其原码相同；

负数的反码是对其原码逐位取反(符号位除外)。ChecksumGeneratorTocreatethechecksumthesenderdoesthefollowing1、Theunitisdividedintoksections,eachofnbits.2、Sections1and2areaddedtogetherusingone'scomplement.Section3isaddedtotheresultofthepreviousstep.Section4isaddedtotheresultofthepreviousstep.……Theprocessrepeatsuntilsectionkisaddedtotheresultofthepreviousstep.3、Thefinalresultiscomplementedtomakethechecksum.ChecksumGeneratorChecksumGeneratorIfthesumofthedatasegmentisT,thechecksumwillbe–T.(111111111)(000000000)反码有两个零：+0-〉000000000 -0-〉1111111ChecksumCheckerThereceiversubdividesthedataunitassenderandaddsallsegmentstogether.Iftheextendeddataunitisintactthetotalvalueshouldbezero(Tplus–Tiszero).Iftheresultisnotzero,thepacketcontainsanerrorandthereceiverrejectsit.Theactualresultoftheadditionwillben1s(-0)ifthedataunitisundamaged.发送16位数据，采用8位校验和。-----1010100100111001使用反码算法相加数据得：10101001

+00111001和11100010校验和(反码)00011101

------10101001001110010001110Example–Checksumgenerator假定接收方接收到上例所发送的比特模式101010010011100100011101

1010100100111001+00011101和11111111求反00000000接收方将三段数据相加得到全1，求反后，变成0，表示没有差错。Example-ChecksumCheckerChecksumdetectsallerrorsinvolvingoddnumbersofbits,aswellasmosterrorsinvolvingevennumbersofbits.如果在某一分段中的一个或多个比特被破坏，并且在下一个分段中具有相反值的对应位也被破坏，这些列的和将不变，因此接收方将检测不出差错。Performance9.3ErrorCorrection(纠错)Errorcorrectioncanbehandledintwoways:Thereceivercanhavethesenderretransmittheentiredataunit.Thereceivercanuseanerror-correctingcode,whichautomaticallycorrectscertainerrors.Intheory,itispossibletocorrectanybinarycodeerrorsautomatically.

纠错码比检错码复杂，并且需要占据更多的冗余比特。纠正多比特差错和突发差错所需要的比特数十分巨大，以致在大多数情况下这样做是十分低效的。因此，大多数纠错技术都局限于一个、两个或者三个比特的差错。9.3.1Single-BitErrorCorrection(单比特纠错)Forcorrecttheerror,wemustknowwhichbitisinerror.So,Thecoreissuesoferrorcorrectionistolocatetheinvalidbitorbits.为纠正一个ASCII字符中的单比特差错，纠错码必须确定7个比特中的哪一个发生了改变。即必须在8个状态之间进行区分：无错，位置1错，直到位置7错。为实现这一点，需要足够的冗余比特来表示所有8个状态。初看起来，三比特的冗余码即足够(三比特可以代表8种不同状态(000-111)并且为8种不同的可能定位)。但是差错还可能发生在冗余位，即七位数据(ASCII字符)加上三位冗余共是10位。因此，为覆盖所有的差错，必须有足够的附加比特。DataandredundancybitsRedundancyBitsmbitsofdataRbitsofredundancyThelengthoftheresultingcodeism+rIfthetotalnumberofbitsinatransmittableunitism+r,thenrmustbeabletoindicateatleastm+r+1differentstates.So,m+r+1statesmustbediscoverablebyrbits;andrbitscanindicate2rdifferentstates.Therefore,2rmustbeequaltoorgreaterthanm+r+1:

2r

m+r+1Therefore,Thevalueofrcanbedeterminedbym.RedundancyBitsRedundancyBitsIfthevalueofmis7,thereforethesmallestrvaluethancansatisfyequation2r

m+r+1is4:

24

7+4+1Relationshipbetweendataandredundancybits:

2r

m+r+1NumberofDataBits(m)NumberofRedundancyBits(r)TotalBits(m+r)123456723334443567910119.3.1Single-BitErrorCorrection(单比特纠错)SUMMARYTransmissionerrorsareusuallydetectedatthephysicallayeroftheOSImodel.TransmissionerrorsareusuallycorrectedatthedatalinklayeroftheOSImodel.Errorscanbecategorizedasfollows:a.Single-bit:onebiterrorperdataunit.b.Multiple-bit:twoormorenonconsecutivebiterrorsperdataunit.c.Burst:twoormoreconsecutivebiterrorsperdataunit.Redundancyistheconceptofsendingextrabitsforuseinerrordetection.SUMMARYFourcommonmethodsoferrordetectionarethefollowing:a.Verticalredundancycheck(VRC).b.Longitudinalredundancycheck(LRC),c.Cyclicredundancycheck(CRC).d.Checksum.InVRCanextrabit(paritybit)isaddedtothedataunit.VRCcandetectonlyanoddnumberoferrors;itcannotdetectanevennumberoferrors.SUMMARYInLRCaredundantdataunitfollowsndataunits.ThehitsaredeterminedbycalculatingtheVRCofeachbitofthedataunits.CRC,themostpowerfulofredundancycheckingtechniques,isbasedonbinarydivision.Checksumisusedbythehigherlayerprotocols(TCP/IP)forerrordetection.Tocalculateachecksum:a.Dividethedataintosections.b.Addthesectionstogetherusingone'scomplementarithmetic.c.Takethecomplementofthefinalsum;thisisthechecksum.