計(jì)算機(jī)網(wǎng)絡(luò)和協(xié)議分析課件

AdvancedComputerNetworks計(jì)算機(jī)網(wǎng)絡(luò)AdvancedComputerNetworks計(jì)算機(jī)網(wǎng)ReviewDatalinklayerdesignissuesServiceProvidedtothenetworklayerFramingError-CorrectingCodesError-DetectingCodes2ReviewDatalinklayerdesigniTheDataLinkLayerChapter33TheDataLinkLayerChapter3TopicsErrordetectionandcorrectionHammingcodeCRC(CyclicRedundancyCheck)4TopicsErrordetectionandcorr2.1Error-CorrectingCodes2.ErrorDetectionandCorrection1010110101011110000100101010110010101111100010100100010100Evencheck?

Asingleparitybit

appendedtothedata,theparitybitischosensothatthenumberof1bitsinthecodewordiseven(orodd)

E.g.,1011010101101002Dparitycheck

code:Formthedatatobetransmittedintoamatrix.Addaparitybittoeachrowandeachcolumnofthematrix.52.1Error-CorrectingCodes2.EHammingdistance

Rule:Todeterminehowmanybitsdiffer,justexclusiveORthetwocodewordsandcountthenumberof1bitsintheresult,forexample:Definition:

Thenumberofbitpositionsinwhichtwocodewordsdifferiscalled

theHammingdistance.

Significance:iftwocodewordsareaHammingdistancedapart,itwillrequiredsingle-biterrorstoconvertoneintotheother.6HammingdistanceRule:Tode

Thebitsthatarepowersof2(1,2,4,8,16,etc.)arecheckbits.Therest(3,5,6,7,9,etc.)arefilledupwiththemdatabits.Eachcheckbitforcestheparityofsomecollectionofbits,includingitself,tobeeven(orodd).HammingcodeCorrectsingleerrors!7ThebitsthatarepowersExercise1.An8-bitbytewithbinaryvalue10101111istobeencodedusinganeven-parityHammingcode.Whatisthebinaryvalueafterencoding?2.A12-bitHammingcodewhosehexadecimalvalueis0xE4Farrivesatareceiver.Whatwastheoriginalvalueinhexadecimal?Assumethatnotmorethan1bitisinerror.101001001111Theoriginal8-bitdatavaluewas0xAF.8Exercise1.An8-bitbytewithGoal:detect“errors”(e.g.,flippedbits)intransmittedframe(note:usedattransportlayeronly)SenderReceive2.2Error-DetectingCodes9Goal:detect“errors”(e.g.,fModulo2arithmeticNocarriesforadditionorborrowsforsubtractionBothadditionandsubtractionareidenticaltoexclusiveORLongdivisioniscarriedoutthesamewayasitisinbinaryexceptthatthesubtractionisdonemodulo2,asabove.10Modulo2arithmeticNocarriesGeneratorPolynomial--G(x)ThesenderandreceivermustagreeuponageneratorpolynomialinadvanceBoththehigh-andlow-orderbitsofG(x)mustbe1Tocomputethechecksumforsomeframewithmbits,correspondingtothepolynomialM(x),theframemustbelongerthanG(x)11GeneratorPolynomial--G(x)TTheideaofCRCTheideaistoappendachecksumtotheendoftheframeinsuchawaythatthepolynomialrepresentedbythechecksummedframeisdivisiblebyG(x).Whenthereceivergetsthechecksummedframe,ittriesdividingitbyG(x).Ifthereisaremainder,therehasbeenatransmissionerror.12TheideaofCRCTheidviewdatabits,

D,asabinarynumberchooser+1bitpattern(generator),

G

goal:chooserCRCbits,

R,suchthat

<D,R>exactlydivisiblebyG(modulo2)receiverknowsG,divides<D,R>byG.Ifnon-zeroremainder:errordetected!candetectallbursterrorslessthanr+1bitswidelyusedinpractice(ATM,HDLC)CyclicRedundancyCheck13viewdatabits,D,asabinaryR=remainder[]D.2rGExample1DataFrame:101110000GeneratorG(x)=x3+1ThetransmittedFrame:10111000001114R=remainder[]D.2rFig.2CalculationofthepolynomialcodechecksumFig.2illustratesthecalculationforaframe1101011011usingthegeneratorG(x)=x4+x+1.Example2ThetransmittedFrame:15Fig.2CalculationofthepolynTransmittingT(x),receivingT’(x)ReceivercomputesE(x)=T’(x)/G(x)ThoseerrorsthathappentocorrespondtopolynomialscontainingG(x)asafactorwillslipby;allothererrorwillbecaught.16TransmittingT(x),receivingTWhatistheremainderobtainedbydividingx7+x5+1bythegeneratorpolynomialx3+x+1?在數(shù)據(jù)傳輸過(guò)程中，若接收方收到發(fā)送方送來(lái)的信息為10110011，生成多項(xiàng)式為G(x)=x3+x2+1，接收方收到的數(shù)據(jù)是否正確？若想發(fā)送的一段信息為10110011，則在線(xiàn)路上傳輸?shù)拇a字是怎樣的？Exercise010不正確1011001110017WhatistheremainderobtainedThepopularG(x)CRC-4X4+X+1CRC-8X8+X5+X4+1CRC-12X12+X11+X3+X+1CRC-16X16+X15+X2+1CRC-16-CCITTX16+X12+X5+1CRC32

X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+118ThepopularG(x)CRC-4X4+X+冗余碼的計(jì)算舉例現(xiàn)在

k=6,M=101001。設(shè)

n=3,除數(shù)

P=1101，被除數(shù)是2nM=101001000。模2運(yùn)算的結(jié)果是：商

Q=110101，

余數(shù)

R=001。把余數(shù)R作為冗余碼添加在數(shù)據(jù)M的后面發(fā)送出去。發(fā)送的數(shù)據(jù)是：2nM+R

即：101001001，共(k+n)位。19冗余碼的計(jì)算舉例現(xiàn)在k=6,M=101001。接收端對(duì)收到的每一幀進(jìn)行CRC檢驗(yàn)(1)若得出的余數(shù)R=0，則判定這個(gè)幀沒(méi)有差錯(cuò)，就接受(accept)。(2)若余數(shù)R

0，則判定這個(gè)幀有差錯(cuò)，就丟棄。但這種檢測(cè)方法并不能確定究竟是哪一個(gè)或哪幾個(gè)比特出現(xiàn)了差錯(cuò)。只要經(jīng)過(guò)嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù)

P，那么出現(xiàn)檢測(cè)不到的差錯(cuò)的概率就很小很小。20接收端對(duì)收到的每一幀進(jìn)行CRC檢驗(yàn)(1)若得出的余數(shù)SummarizeDesignissuesServiceProvidedtothenetworklayerFramingError-CorrectingCodesError-DetectingCodes

21SummarizeDesignissues21HomeworkPage2432,3,5,14,1522HomeworkPage24322PreparationElementarydatalinkprotocols23PreparationElementarydatali差錯(cuò)的檢測(cè)與控制（1）差錯(cuò)檢測(cè)衡量通信線(xiàn)路傳輸質(zhì)量的技術(shù)指標(biāo)是誤碼率。Pe=錯(cuò)誤接收的碼元數(shù)/接收的總碼元數(shù)（2）幾種冗余校驗(yàn)方法垂直冗余校驗(yàn) 水平冗余校驗(yàn) 水平垂直冗余校驗(yàn) 循環(huán)冗余校驗(yàn)24差錯(cuò)的檢測(cè)與控制（1）差錯(cuò)檢測(cè)24垂直奇偶校驗(yàn)垂直奇偶校驗(yàn)又稱(chēng)縱向奇偶校驗(yàn)，它能檢測(cè)出每列中所有奇數(shù)個(gè)錯(cuò)，但檢測(cè)不出偶數(shù)個(gè)的錯(cuò)，如下圖所示，因而對(duì)差錯(cuò)的漏檢率接近1/2。位\數(shù)字0123456789C10101010101C20011001100C30000111100C40000000011C51111111111C61111111111C70000000000偶C00110100110奇1001011001垂直奇偶校驗(yàn)方式25垂直奇偶校驗(yàn)垂直奇偶校驗(yàn)又稱(chēng)縱向奇偶校驗(yàn)，它能檢水平奇偶校驗(yàn)水平奇偶校驗(yàn)又稱(chēng)橫向奇偶校驗(yàn)，它不但能檢測(cè)出各段同一位上的奇數(shù)個(gè)錯(cuò)，而且還能檢測(cè)出突發(fā)長(zhǎng)度<=p的所有突發(fā)錯(cuò)誤。其漏檢率要比垂直奇偶校驗(yàn)方法低，但實(shí)現(xiàn)水平奇偶校驗(yàn)時(shí)，一定要使用數(shù)據(jù)緩沖器。位\數(shù)字0123456789偶校驗(yàn)C101010101011C200110011000C300001111000C400000000110C511111111111C611111111111C700000000000水平奇偶校驗(yàn)方式26水平奇偶校驗(yàn)水平奇偶校驗(yàn)又稱(chēng)橫向奇偶校驗(yàn)，它不但水平垂直校驗(yàn)水平垂直校驗(yàn)(LRC)又叫報(bào)文校驗(yàn)、方塊校驗(yàn)。將若干水平奇偶校驗(yàn)碼排成若干行，然后對(duì)每列進(jìn)行奇偶校驗(yàn)，放在最后一行，該檢驗(yàn)字符的編碼方法是使每一位縱向代碼中1的個(gè)數(shù)成為奇數(shù)(或偶數(shù))。傳輸時(shí)按照列順序進(jìn)行傳輸，在一批字符傳送之后，另外增加一個(gè)檢驗(yàn)字符，在接收端又按照行的順序檢驗(yàn)是否存在差錯(cuò)。圖2-25水平垂直奇偶校驗(yàn)方式Back27水平垂直校驗(yàn)水平垂直校驗(yàn)(LRC)又叫報(bào)文校驗(yàn)、2828292930303131Back32Back32Thanks!33Thanks!33AdvancedComputerNetworks計(jì)算機(jī)網(wǎng)絡(luò)AdvancedComputerNetworks計(jì)算機(jī)網(wǎng)ReviewDatalinklayerdesignissuesServiceProvidedtothenetworklayerFramingError-CorrectingCodesError-DetectingCodes35ReviewDatalinklayerdesigniTheDataLinkLayerChapter336TheDataLinkLayerChapter3TopicsErrordetectionandcorrectionHammingcodeCRC(CyclicRedundancyCheck)37TopicsErrordetectionandcorr2.1Error-CorrectingCodes2.ErrorDetectionandCorrection1010110101011110000100101010110010101111100010100100010100Evencheck?

Asingleparitybit

appendedtothedata,theparitybitischosensothatthenumberof1bitsinthecodewordiseven(orodd)

E.g.,1011010101101002Dparitycheck

code:Formthedatatobetransmittedintoamatrix.Addaparitybittoeachrowandeachcolumnofthematrix.382.1Error-CorrectingCodes2.EHammingdistance

Rule:Todeterminehowmanybitsdiffer,justexclusiveORthetwocodewordsandcountthenumberof1bitsintheresult,forexample:Definition:

Thenumberofbitpositionsinwhichtwocodewordsdifferiscalled

theHammingdistance.

Significance:iftwocodewordsareaHammingdistancedapart,itwillrequiredsingle-biterrorstoconvertoneintotheother.39HammingdistanceRule:Tode

Thebitsthatarepowersof2(1,2,4,8,16,etc.)arecheckbits.Therest(3,5,6,7,9,etc.)arefilledupwiththemdatabits.Eachcheckbitforcestheparityofsomecollectionofbits,includingitself,tobeeven(orodd).HammingcodeCorrectsingleerrors!40ThebitsthatarepowersExercise1.An8-bitbytewithbinaryvalue10101111istobeencodedusinganeven-parityHammingcode.Whatisthebinaryvalueafterencoding?2.A12-bitHammingcodewhosehexadecimalvalueis0xE4Farrivesatareceiver.Whatwastheoriginalvalueinhexadecimal?Assumethatnotmorethan1bitisinerror.101001001111Theoriginal8-bitdatavaluewas0xAF.41Exercise1.An8-bitbytewithGoal:detect“errors”(e.g.,flippedbits)intransmittedframe(note:usedattransportlayeronly)SenderReceive2.2Error-DetectingCodes42Goal:detect“errors”(e.g.,fModulo2arithmeticNocarriesforadditionorborrowsforsubtractionBothadditionandsubtractionareidenticaltoexclusiveORLongdivisioniscarriedoutthesamewayasitisinbinaryexceptthatthesubtractionisdonemodulo2,asabove.43Modulo2arithmeticNocarriesGeneratorPolynomial--G(x)ThesenderandreceivermustagreeuponageneratorpolynomialinadvanceBoththehigh-andlow-orderbitsofG(x)mustbe1Tocomputethechecksumforsomeframewithmbits,correspondingtothepolynomialM(x),theframemustbelongerthanG(x)44GeneratorPolynomial--G(x)TTheideaofCRCTheideaistoappendachecksumtotheendoftheframeinsuchawaythatthepolynomialrepresentedbythechecksummedframeisdivisiblebyG(x).Whenthereceivergetsthechecksummedframe,ittriesdividingitbyG(x).Ifthereisaremainder,therehasbeenatransmissionerror.45TheideaofCRCTheidviewdatabits,

D,asabinarynumberchooser+1bitpattern(generator),

G

goal:chooserCRCbits,

R,suchthat

<D,R>exactlydivisiblebyG(modulo2)receiverknowsG,divides<D,R>byG.Ifnon-zeroremainder:errordetected!candetectallbursterrorslessthanr+1bitswidelyusedinpractice(ATM,HDLC)CyclicRedundancyCheck46viewdatabits,D,asabinaryR=remainder[]D.2rGExample1DataFrame:101110000GeneratorG(x)=x3+1ThetransmittedFrame:10111000001147R=remainder[]D.2rFig.2CalculationofthepolynomialcodechecksumFig.2illustratesthecalculationforaframe1101011011usingthegeneratorG(x)=x4+x+1.Example2ThetransmittedFrame:48Fig.2CalculationofthepolynTransmittingT(x),receivingT’(x)ReceivercomputesE(x)=T’(x)/G(x)ThoseerrorsthathappentocorrespondtopolynomialscontainingG(x)asafactorwillslipby;allothererrorwillbecaught.49TransmittingT(x),receivingTWhatistheremainderobtainedbydividingx7+x5+1bythegeneratorpolynomialx3+x+1?在數(shù)據(jù)傳輸過(guò)程中，若接收方收到發(fā)送方送來(lái)的信息為10110011，生成多項(xiàng)式為G(x)=x3+x2+1，接收方收到的數(shù)據(jù)是否正確？若想發(fā)送的一段信息為10110011，則在線(xiàn)路上傳輸?shù)拇a字是怎樣的？Exercise010不正確1011001110050WhatistheremainderobtainedThepopularG(x)CRC-4X4+X+1CRC-8X8+X5+X4+1CRC-12X12+X11+X3+X+1CRC-16X16+X15+X2+1CRC-16-CCITTX16+X12+X5+1CRC32

X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+151ThepopularG(x)CRC-4X4+X+冗余碼的計(jì)算舉例現(xiàn)在

k=6,M=101001。設(shè)

n=3,除數(shù)

P=1101，被除數(shù)是2nM=101001000。模2運(yùn)算的結(jié)果是：商

Q=110101，

余數(shù)

R=001。把余數(shù)R作為冗余碼添加在數(shù)據(jù)M的后面發(fā)送出去。發(fā)送的數(shù)據(jù)是：2nM+R

即：101001001，共(k+n)位。52冗余碼的計(jì)算舉例現(xiàn)在k=6,M=101001。接收端對(duì)收到的每一幀進(jìn)行CRC檢驗(yàn)(1)若得出的余數(shù)R=0，則判定這個(gè)幀沒(méi)有差錯(cuò)，就接受(accept)。(2)若余數(shù)R

0，則判定這個(gè)幀有差錯(cuò)，就丟棄。但這種檢測(cè)方法并不能確定究竟是哪一個(gè)或哪幾個(gè)比特出現(xiàn)了差錯(cuò)。只要經(jīng)過(guò)嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù)

P，那么出現(xiàn)檢測(cè)不到的差錯(cuò)的概率就很小很小。53接收端對(duì)收到的每一幀進(jìn)行CRC檢驗(yàn)(1)若得出的余數(shù)SummarizeDesignissuesServiceProvidedtothenetworklayerFramingError-CorrectingCodesError-Det