計算機網(wǎng)絡和協(xié)議分析課件

AdvancedComputerNetworks計算機網(wǎng)絡AdvancedComputerNetworks計算機網(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ù)傳輸過程中，若接收方收到發(fā)送方送來的信息為10110011，生成多項式為G(x)=x3+x2+1，接收方收到的數(shù)據(jù)是否正確？若想發(fā)送的一段信息為10110011，則在線路上傳輸?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+冗余碼的計算舉例現(xiàn)在

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

n=3,除數(shù)

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

Q=110101，

余數(shù)

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

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

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

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

21SummarizeDesignissues21HomeworkPage2432,3,5,14,1522HomeworkPage24322PreparationElementarydatalinkprotocols23PreparationElementarydatali差錯的檢測與控制（1）差錯檢測衡量通信線路傳輸質(zhì)量的技術(shù)指標是誤碼率。Pe=錯誤接收的碼元數(shù)/接收的總碼元數(shù)（2）幾種冗余校驗方法垂直冗余校驗 水平冗余校驗 水平垂直冗余校驗 循環(huán)冗余校驗24差錯的檢測與控制（1）差錯檢測24垂直奇偶校驗垂直奇偶校驗又稱縱向奇偶校驗，它能檢測出每列中所有奇數(shù)個錯，但檢測不出偶數(shù)個的錯，如下圖所示，因而對差錯的漏檢率接近1/2。位\數(shù)字0123456789C10101010101C20011001100C30000111100C40000000011C51111111111C61111111111C70000000000偶C00110100110奇1001011001垂直奇偶校驗方式25垂直奇偶校驗垂直奇偶校驗又稱縱向奇偶校驗，它能檢水平奇偶校驗水平奇偶校驗又稱橫向奇偶校驗，它不但能檢測出各段同一位上的奇數(shù)個錯，而且還能檢測出突發(fā)長度<=p的所有突發(fā)錯誤。其漏檢率要比垂直奇偶校驗方法低，但實現(xiàn)水平奇偶校驗時，一定要使用數(shù)據(jù)緩沖器。位\數(shù)字0123456789偶校驗C101010101011C200110011000C300001111000C400000000110C511111111111C611111111111C700000000000水平奇偶校驗方式26水平奇偶校驗水平奇偶校驗又稱橫向奇偶校驗，它不但水平垂直校驗水平垂直校驗(LRC)又叫報文校驗、方塊校驗。將若干水平奇偶校驗碼排成若干行，然后對每列進行奇偶校驗，放在最后一行，該檢驗字符的編碼方法是使每一位縱向代碼中1的個數(shù)成為奇數(shù)(或偶數(shù))。傳輸時按照列順序進行傳輸，在一批字符傳送之后，另外增加一個檢驗字符，在接收端又按照行的順序檢驗是否存在差錯。圖2-25水平垂直奇偶校驗方式Back27水平垂直校驗水平垂直校驗(LRC)又叫報文校驗、2828292930303131Back32Back32Thanks!33Thanks!33AdvancedComputerNetworks計算機網(wǎng)絡AdvancedComputerNetworks計算機網(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ù)傳輸過程中，若接收方收到發(fā)送方送來的信息為10110011，生成多項式為G(x)=x3+x2+1，接收方收到的數(shù)據(jù)是否正確？若想發(fā)送的一段信息為10110011，則在線路上傳輸?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+冗余碼的計算舉例現(xiàn)在

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

n=3,除數(shù)

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

Q=110101，

余數(shù)

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

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

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

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