數(shù)據(jù)通信與網(wǎng)絡(luò)09-錯(cuò)誤檢測(cè)與糾正-3

第九章錯(cuò)誤檢測(cè)與糾正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(不連續(xù)的)

bitsinthedataunithavechanged.9.1.3BursterrorAbursterrormeansthattwoormore

consecutive(連續(xù)的)

bitsinthedataunithavechanged.突發(fā)差錯(cuò)大多發(fā)生在串行傳輸時(shí)。～通常噪聲持續(xù)時(shí)間比位持續(xù)時(shí)間長(zhǎng)，這就是說(shuō)當(dāng)噪聲影響數(shù)據(jù)時(shí)就會(huì)影響一組比特。 影響的位數(shù)依賴于數(shù)據(jù)速率和噪聲持續(xù)時(shí)間。例如，如果發(fā)送數(shù)據(jù)速率是1Kbps,1/100s的噪聲將影響10個(gè)比特;如果速率是1Mbps，同樣的噪聲影響10000個(gè)比特。9.1.3Bursterror9.2ErrorDetection(錯(cuò)誤檢測(cè))Inerrordetection,wearelookingonlytoseeifanyerrorhasoccurred.Theanswerisasimpleyesorno.Wearenoteveninterestedinthenumberoferrors.

Asingle-biterroristhesameforusasabursterror.9.2.1RedundancyThecentralconceptindetectingorcorrectingerrorsisredundancy.Tobeabletodetectorcorrecterrors,weneedtosendsomeextrabitswithourdata.

Theseredundantbitsareaddedbythesenderandremovedbythereceiver.

Theirpresenceallowsthereceivertodetectorcorrectcorruptedbits.Usingredundantbitstochecktheaccuracyofadataunit9.2.1RedundancyFourtypesofredundancychecksareusedindatacommunications.VRC(VerticalRedundancyCheck,垂直冗余校驗(yàn))LRC(LongitudinalRedundancy,縱向冗余校驗(yàn))CRC(CyclicalRedundancyCheck,循環(huán)冗余校驗(yàn))Checksum(校驗(yàn)和)VRC、LRC、CRC在物理層實(shí)現(xiàn)，數(shù)據(jù)鏈路層使用；校驗(yàn)和應(yīng)用于更高的OSI層次。9.2.1Redundancy9.2.2VRC(VerticalRedundancyCheck)VRC(垂直冗余校驗(yàn))oftencalledparitycheck(奇偶校驗(yàn)):

oddparityorevenparityInthistechnique,aredundantbit,calledaparitybit(校驗(yàn)位),isappendedtoeverydataunitsothatthetotalnumberof1sintheunitbecomeeitherevenorodd.VRCcandetectall

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

two-dimensional

paritycheck.

Inthismethod,thedatawordisorganizedinatable(rowsandcolumns).在縱向冗余校驗(yàn)中，將一個(gè)數(shù)據(jù)塊劃分成幾行，并將校驗(yàn)位組成的冗余行添加到整個(gè)數(shù)據(jù)塊中。LRC(LongitudinalRedundancy)9.2.3LRC(LongitudinalRedundancy)(縱向冗余校驗(yàn)碼)(dataunit)9.2.3LRC(LongitudinalRedundancy)LRCenormouslyincreasesthelikelihoodofdetectingmultiple-bitandbursterrors.However,thereisonepatternoferrorsthatremainselusive.

Iftwobitsinonedataunitaredamagedandtwobitsinexactlythesamepositionsinanotherdataunitarealsodamaged,theLRCcheckerwillnotdetectanerror.

例如有兩個(gè)數(shù)據(jù)單元11110000以及11000011。如果在每個(gè)數(shù)據(jù)單元的第一個(gè)和最后一個(gè)位置的比特被改變，將數(shù)據(jù)單元變成01110001和01000010，那么LRC就無(wú)法檢測(cè)出這些差錯(cuò)。ThethirdandmostpowerfuloftheredundancycheckingtechniquesistheCRC.UnlikeVRCandLRCwhichbasedonaddition,CRCisbasedon

binarydivision.在CRC中，在數(shù)據(jù)單元末尾附加一串冗余比特，稱作循環(huán)冗余校驗(yàn)碼或循環(huán)冗余校驗(yàn)余數(shù)，使得整個(gè)數(shù)據(jù)單元可以被另一個(gè)預(yù)定的二進(jìn)制數(shù)所整除。到達(dá)目的地后，用同一個(gè)數(shù)去除整個(gè)數(shù)據(jù)單元。如果不產(chǎn)生余數(shù)，則認(rèn)為數(shù)據(jù)單元是完整正確的，從而接受該數(shù)據(jù)單元；有余數(shù)意味著數(shù)據(jù)單元被破壞，因此拒絕接受該數(shù)據(jù)單元。9.2.4CyclicRedundancyCheck(CRC)9.2.4CyclicRedundancyCheck(CRC)CRCgeneratorandchecker在循環(huán)冗余校驗(yàn)中使用的冗余比特是將數(shù)據(jù)單元除以一個(gè)預(yù)定的除數(shù)后產(chǎn)生的，余數(shù)就是循環(huán)冗余校驗(yàn)碼(CRC碼)。只有以下兩個(gè)特性的CRC碼才是合法的:

必須比除數(shù)至少少一位；在附加到數(shù)據(jù)串末尾后必須形成可以被除數(shù)整除的比特序列。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(多項(xiàng)式)TheCRCgenerator(thedivisor)ismostoftenrepresentedasanalgebraicpolynomial(代數(shù)多項(xiàng)式).多項(xiàng)式所需具備的(基本)性質(zhì)：

1、不被x除盡；

2、可被x+1除盡。第一個(gè)條件保證檢測(cè)出所有長(zhǎng)度等于多項(xiàng)式階數(shù)的突發(fā)差錯(cuò)；第二個(gè)條件保證檢測(cè)出所有影響奇數(shù)位的突發(fā)差錯(cuò)。Polynomials(多項(xiàng)式)高性能多項(xiàng)式所需具備的特性：

1、至少包含兩項(xiàng)；

2、x0項(xiàng)的系數(shù)應(yīng)該是1；

3、應(yīng)該不能整除xt+1(t為2到n-1之間)；4、應(yīng)該有因子x+1?！鵄polynomialrepresentingadivisorPolynomials(多項(xiàng)式)Therelationshipofapolynomialtoitscorrespondingbinaryrepresentation:Polynomials(多項(xiàng)式)ThestandardpolynomialusedbypopularprotocolforCRCgenerationareshownbelow.Thenumbers12,16and32refertothesizeoftheCRCremainder.TheCRCdivisorare13,17and33bits,respectively.Polynomials(多項(xiàng)式)StandardpolynomialsusedbypopularprotocolsCRC性能可檢測(cè)出所有影響奇數(shù)位的突發(fā)差錯(cuò)；可以檢測(cè)出所有長(zhǎng)度小于或等于多項(xiàng)式階數(shù)的突發(fā)差錯(cuò)；可以以非常高的概率檢測(cè)出長(zhǎng)度大于多項(xiàng)式階數(shù)的突發(fā)差錯(cuò)。Theerrordetectionmethodusedbythe

higherlayerprotocols

iscalledchecksum.Checksumisbasedontheconceptofredundancyalso.9.2.5Checksum(校驗(yàn)和)ChecksumGeneratorThechecksumgeneratorsubdividesthedataintoequalsegmentsofnbits.Thesesegmentsareaddedtogetherusingone’scomplementarithmetic(反碼算法).

結(jié)果仍然為n比特。Thatsumisthencomplemented(取反)andappendedtotheendoftheoriginaldataunitasredundancybits,calledthechecksumfiled.

正數(shù)的反碼與其原碼相同；

負(fù)數(shù)的反碼是對(duì)其原碼逐位取反(符號(hào)位除外)。ChecksumGeneratorTocreatethechecksumthesenderdoesthefollowing1、Theunitisdividedintoksections,eachofnbits.2、Sections1and2areaddedtogetherusingone'scomplement.Section3isaddedtotheresultofthepreviousstep.Section4isaddedtotheresultofthepreviousstep.……Theprocessrepeatsuntilsectionkisaddedtotheresultofthepreviousstep.3、Thefinalresultiscomplementedtomakethechecksum.ChecksumGeneratorChecksumGeneratorIfthesumofthedatasegmentisT,thechecksumwillbe–T.(111111111)(000000000)反碼有兩個(gè)零：+0-〉000000000 -0-〉1111111ChecksumCheckerThereceiversubdividesthedataunitassenderandaddsallsegmentstogether.Iftheextendeddataunitisintactthetotalvalueshouldbezero(Tplus–Tiszero).Iftheresultisnotzero,thepacketcontainsanerrorandthereceiverrejectsit.Theactualresultoftheadditionwillben1s(-0)ifthedataunitisundamaged.發(fā)送16位數(shù)據(jù)，采用8位校驗(yàn)和。-----1010100100111001使用反碼算法相加數(shù)據(jù)得：10101001

+00111001和11100010校驗(yàn)和(反碼)00011101

------10101001001110010001110Example–Checksumgenerator假定接收方接收到上例所發(fā)送的比特模式101010010011100100011101

1010100100111001+00011101和11111111求反00000000接收方將三段數(shù)據(jù)相加得到全1，求反后，變成0，表示沒(méi)有差錯(cuò)。Example-ChecksumCheckerChecksumdetectsallerrorsinvolvingoddnumbersofbits,aswellasmosterrorsinvolvingevennumbersofbits.如果在某一分段中的一個(gè)或多個(gè)比特被破壞，并且在下一個(gè)分段中具有相反值的對(duì)應(yīng)位也被破壞，這些列的和將不變，因此接收方將檢測(cè)不出差錯(cuò)。Performance9.3ErrorCorrection(糾錯(cuò))Errorcorrectioncanbehandledintwoways:Thereceivercanhavethesenderretransmittheentiredataunit.Thereceivercanuseanerror-correctingcode,whichautomaticallycorrectscertainerrors.Intheory,itispossibletocorrectanybinarycodeerrorsautomatically.

糾錯(cuò)碼比檢錯(cuò)碼復(fù)雜，并且需要占據(jù)更多的冗余比特。糾正多比特差錯(cuò)和突發(fā)差錯(cuò)所需要的比特?cái)?shù)十分巨大，以致在大多數(shù)情況下這樣做是十分低效的。因此，大多數(shù)糾錯(cuò)技術(shù)都局限于一個(gè)、兩個(gè)或者三個(gè)比特的差錯(cuò)。9.3.1Single-BitErrorCorrection(單比特糾錯(cuò))Forcorrecttheerror,wemustknowwhichbitisinerror.So,Thecoreissuesoferrorcorrectionistolocatetheinvalidbitorbits.為糾正一個(gè)ASCII字符中的單比特差錯(cuò)，糾錯(cuò)碼必須確定7個(gè)比特中的哪一個(gè)發(fā)生了改變。即必須在8個(gè)狀態(tài)之間進(jìn)行區(qū)分：無(wú)錯(cuò)，位置1錯(cuò)，直到位置7錯(cuò)。為實(shí)現(xiàn)這一點(diǎn)，需要足夠的冗余比特來(lái)表示所有8個(gè)狀態(tài)。初看起來(lái)，三比特的冗余碼即足夠(三比特可以代表8種不同狀態(tài)(000-111)并且為8種不同的可能定位)。但是差錯(cuò)還可能發(fā)生在冗余位，即七位數(shù)據(jù)(ASCII字符)加上三位冗余共是10位。因此，為覆蓋所有的差錯(cuò)，必須有足夠的附加比特。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(單比特糾錯(cuò))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.