计算机网络和协议分析课件

AdvancedComputerNetworks计算机网络AdvancedComputerNetworks计算机网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?在数据传输过程中，若接收方收到发送方送来的信息为10110011，生成多项式为G(x)=x3+x2+1，接收方收到的数据是否正确？若想发送的一段信息为10110011，则在线路上传输的码字是怎样的？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+冗余码的计算举例现在

k=6,M=101001。设

n=3,除数

P=1101，被除数是2nM=101001000。模2运算的结果是：商

Q=110101，

余数

R=001。把余数R作为冗余码添加在数据M的后面发送出去。发送的数据是：2nM+R

即：101001001，共(k+n)位。19冗余码的计算举例现在k=6,M=101001。接收端对收到的每一帧进行CRC检验(1)若得出的余数R=0，则判定这个帧没有差错，就接受(accept)。(2)若余数R

0，则判定这个帧有差错，就丢弃。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。只要经过严格的挑选，并使用位数足够多的除数

P，那么出现检测不到的差错的概率就很小很小。20接收端对收到的每一帧进行CRC检验(1)若得出的余数SummarizeDesignissuesServiceProvidedtothenetworklayerFramingError-CorrectingCodesError-DetectingCodes

21SummarizeDesignissues21HomeworkPage2432,3,5,14,1522HomeworkPage24322PreparationElementarydatalinkprotocols23PreparationElementarydatali差错的检测与控制（1）差错检测衡量通信线路传输质量的技术指标是误码率。Pe=错误接收的码元数/接收的总码元数（2）几种冗余校验方法垂直冗余校验 水平冗余校验 水平垂直冗余校验 循环冗余校验24差错的检测与控制（1）差错检测24垂直奇偶校验垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所有奇数个错，但检测不出偶数个的错，如下图所示，因而对差错的漏检率接近1/2。位\数字0123456789C10101010101C20011001100C30000111100C40000000011C51111111111C61111111111C70000000000偶C00110100110奇1001011001垂直奇偶校验方式25垂直奇偶校验垂直奇偶校验又称纵向奇偶校验，它能检水平奇偶校验水平奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度<=p的所有突发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。位\数字0123456789偶校验C101010101011C200110011000C300001111000C400000000110C511111111111C611111111111C700000000000水平奇偶校验方式26水平奇偶校验水平奇偶校验又称横向奇偶校验，它不但水平垂直校验水平垂直校验(LRC)又叫报文校验、方块校验。将若干水平奇偶校验码排成若干行，然后对每列进行奇偶校验，放在最后一行，该检验字符的编码方法是使每一位纵向代码中1的个数成为奇数(或偶数)。传输时按照列顺序进行传输，在一批字符传送之后，另外增加一个检验字符，在接收端又按照行的顺序检验是否存在差错。图2-25水平垂直奇偶校验方式Back27水平垂直校验水平垂直校验(LRC)又叫报文校验、2828292930303131Back32Back32Thanks!33Thanks!33AdvancedComputerNetworks计算机网络AdvancedComputerNetworks计算机网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?在数据传输过程中，若接收方收到发送方送来的信息为10110011，生成多项式为G(x)=x3+x2+1，接收方收到的数据是否正确？若想发送的一段信息为10110011，则在线路上传输的码字是怎样的？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+冗余码的计算举例现在

k=6,M=101001。设

n=3,除数

P=1101，被除数是2nM=101001000。模2运算的结果是：商

Q=110101，

余数

R=001。把余数R作为冗余码添加在数据M的后面发送出去。发送的数据是：2nM+R

即：101001001，共(k+n)位。52冗余码的计算举例现在k=6,M=101001。接收端对收到的每一帧进行CRC检验(1)若得出的余数R=0，则判定这个帧没有差错，就接受(accept)。(2)若余数R

0，则判定这个帧有差错，就丢弃。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。只要经过严格的挑选，并使用位数足够多的除数

P，那么出现检测不到的差错的概率就很小很小。53接收端对收到的每一帧进行CRC检验(1)若得出的余数SummarizeDesignissuesServiceProvidedtothenetworklayerFramingError-CorrectingCodesError-Det