數(shù)據(jù)通信與網(wǎng)絡(luò)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(不連續(xù)的)

bitsinthedataunithavechanged.9.1.3BursterrorAbursterrormeansthattwoormore

consecutive(連續(xù)的)

bitsinthedataunithavechanged.突發(fā)差錯大多發(fā)生在串行傳輸時?！ǔＴ肼暢掷m(xù)時間比位持續(xù)時間長，這就是說當噪聲影響數(shù)據(jù)時就會影響一組比特。 影響的位數(shù)依賴于數(shù)據(jù)速率和噪聲持續(xù)時間。例如，如果發(fā)送數(shù)據(jù)速率是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,循環(huán)冗余校驗)Checksum(校驗和)VRC、LRC、CRC在物理層實現(xiàn)，數(shù)據(jù)鏈路層使用；校驗和應(yīng)用于更高的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).在縱向冗余校驗中，將一個數(shù)據(jù)塊劃分成幾行，并將校驗位組成的冗余行添加到整個數(shù)據(jù)塊中。LRC(LongitudinalRedundancy)9.2.3LRC(LongitudinalRedundancy)(縱向冗余校驗碼)(dataunit)9.2.3LRC(LongitudinalRedundancy)LRCenormouslyincreasesthelikelihoodofdetectingmultiple-bitandbursterrors.However,thereisonepatternoferrorsthatremainselusive.

Iftwobitsinonedataunitaredamagedandtwobitsinexactlythesamepositionsinanotherdataunitarealsodamaged,theLRCcheckerwillnotdetectanerror.

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

binarydivision.在CRC中，在數(shù)據(jù)單元末尾附加一串冗余比特，稱作循環(huán)冗余校驗碼或循環(huán)冗余校驗余數(shù)，使得整個數(shù)據(jù)單元可以被另一個預(yù)定的二進制數(shù)所整除。到達目的地后，用同一個數(shù)去除整個數(shù)據(jù)單元。如果不產(chǎn)生余數(shù)，則認為數(shù)據(jù)單元是完整正確的，從而接受該數(shù)據(jù)單元；有余數(shù)意味著數(shù)據(jù)單元被破壞，因此拒絕接受該數(shù)據(jù)單元。9.2.4CyclicRedundancyCheck(CRC)9.2.4CyclicRedundancyCheck(CRC)CRCgeneratorandchecker在循環(huán)冗余校驗中使用的冗余比特是將數(shù)據(jù)單元除以一個預(yù)定的除數(shù)后產(chǎn)生的，余數(shù)就是循環(huán)冗余校驗碼(CRC碼)。只有以下兩個特性的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(多項式)TheCRCgenerator(thedivisor)ismostoftenrepresentedasanalgebraicpolynomial(代數(shù)多項式).多項式所需具備的(基本)性質(zhì)：

1、不被x除盡；

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

1、至少包含兩項；

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

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

higherlayerprotocols

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

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

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

負數(shù)的反碼是對其原碼逐位取反(符號位除外)。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.發(fā)送16位數(shù)據(jù)，采用8位校驗和。-----1010100100111001使用反碼算法相加數(shù)據(jù)得：10101001

+00111001和11100010校驗和(反碼)00011101

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

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

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