计算机网络和协议分析8

WeihongChenDepartmentofComputerScienceHunanCityUniversitySep2010AdvancedComputerNetworks计算机网络Review•Datalinklayerdesignissues–ServiceProvidedtothenetworklayer–Framing–Error-CorrectingCodes–Error-DetectingCodesWeihongChenHunanCityUniversitySep’10CNTheDataLinkLayerChapter3WeihongChenHunanCityUniversitySep’10CNTopicsErrordetectionandcorrection–Hammingcode–CRC(CyclicRedundancyCheck)WeihongChenHunanCityUniversitySep’10CN2.1Error-CorrectingCodes2.ErrorDetectionandCorrection1010110101011110000100101010110010101111100010100100010100Evencheck?•Asingleparitybitappendedtothedata,theparitybitischosensothatthenumberof1bitsinthecodewordiseven(orodd)E.g.,101101010110100•2Dparitycheckcode:Formthedatatobetransmittedintoamatrix.Addaparitybittoeachrowandeachcolumnofthematrix.WeihongChenHunanCityUniversitySep’10CNHammingdistanceRule:Todeterminehowmanybitsdiffer,justexclusiveORthetwocodewordsandcountthenumberof1bitsintheresult,forexample:Definition:ThenumberofbitpositionsinwhichtwocodewordsdifferiscalledtheHammingdistance.Significance:iftwocodewordsareaHammingdistancedapart,itwillrequiredsingle-biterrorstoconvertoneintotheother.WeihongChenHunanCityUniversitySep’10CNThebitsthatarepowersof2(1,2,4,8,16,etc.)arecheckbits.Therest(3,5,6,7,9,etc.)arefilledupwiththemdatabits.Eachcheckbitforcestheparityofsomecollectionofbits,includingitself,tobeeven(orodd).HammingcodeCorrectsingleerrors!Exercise•1.An8-bitbytewithbinaryvalue10101111istobeencodedusinganeven-parityHammingcode.Whatisthebinaryvalueafterencoding?•2.A12-bitHammingcodewhosehexadecimalvalueis0xE4Farrivesatareceiver.Whatwastheoriginalvalueinhexadecimal?Assumethatnotmorethan1bitisinerror.101001001111Theoriginal8-bitdatavaluewas0xAF.Goal:detect“errors”(e.g.,flippedbits)intransmittedframe(note:usedattransportlayeronly)SenderReceive2.2Error-DetectingCodesWeihongChenHunanCityUniversitySep’10CNModulo2arithmetic•Nocarriesforadditionorborrowsforsubtraction•BothadditionandsubtractionareidenticaltoexclusiveOR•Longdivisioniscarriedoutthesamewayasitisinbinaryexceptthatthesubtractionisdonemodulo2,asabove.GeneratorPolynomial--G(x)•Thesenderandreceivermustagreeuponageneratorpolynomialinadvance•Boththehigh-andlow-orderbitsofG(x)mustbe1•Tocomputethechecksumforsomeframewithmbits,correspondingtothepolynomialM(x),theframemustbelongerthanG(x)TheideaofCRCTheideaistoappendachecksumtotheendoftheframeinsuchawaythatthepolynomialrepresentedbythechecksummedframeisdivisiblebyG(x).Whenthereceivergetsthechecksummedframe,ittriesdividingitbyG(x).Ifthereisaremainder,therehasbeenatransmissionerror.viewdatabits,D,asabinarynumberchooser+1bitpattern(generator),Ggoal:chooserCRCbits,R,suchthat–D,RexactlydivisiblebyG(modulo2)–receiverknowsG,dividesD,RbyG.Ifnon-zeroremainder:errordetected!–candetectallbursterrorslessthanr+1bitswidelyusedinpractice(ATM,HDLC)CyclicRedundancyCheckR=remainder[]D.2rGExample1DataFrame:101110000GeneratorG(x)=x3+1ThetransmittedFrame:101110000011Fig.2CalculationofthepolynomialcodechecksumFig.2illustratesthecalculationforaframe1101011011usingthegeneratorG(x)=x4+x+1.Example2ThetransmittedFrame:•TransmittingT(x),receivingT’(x)•ReceivercomputesE(x)=T’(x)/G(x)•ThoseerrorsthathappentocorrespondtopolynomialscontainingG(x)asafactorwillslipby;allothererrorwillbecaught.WeihongChenHunanCityUniversitySep’10CNWhatistheremainderobtainedbydividingx7+x5+1bythegeneratorpolynomialx3+x+1?在数据传输过程中，若接收方收到发送方送来的信息为10110011，生成多项式为G(x)=x3+x2+1，接收方收到的数据是否正确？若想发送的一段信息为10110011，则在线路上传输的码字是怎样的？Exercise010不正确10110011100WeihongChenHunanCityUniversitySep’10CNThepopularG(x)•CRC-4X4+X+1•CRC-8X8+X5+X4+1•CRC-12X12+X11+X3+X+1•CRC-16X16+X15+X2+1•CRC-16-CCITTX16+X12+X5+1•CRC32X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1WeihongChenHunanCityUniversitySep’10CN冗余码的计算举例•现在k=6,M=101001。•设n=3,除数P=1101，•被除数是2nM=101001000。•模2运算的结果是：商Q=110101，余数R=001。•把余数R作为冗余码添加在数据M的后面发送出去。发送的数据是：2nM+R即：101001001，共(k+n)位。WeihongChenHunanCityUniversitySep’10CN接收端对收到的每一帧进行CRC检验•(1)若得出的余数R=0，则判定这个帧没有差错，就接受(accept)。•(2)若余数R0，则判定这个帧有差错，就丢弃。•但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。•只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。WeihongChenHunanCityUniversitySep’10CNSummarize•Designissues•ServiceProvidedtothenetworklayer•Framing•Error-CorrectingCodes•Error-DetectingCodesWeihongChenHunanCityUniversitySep’10CNHomeworkPage243•2,3,5,14,15WeihongChenHunanCityUniversitySep’10CNPreparation•ElementarydatalinkprotocolsWeihongChenHunanCityUniversitySep’10CN差错的检测与控制（1）差错检测衡量通信线路传输质量的技术指标是误码率。Pe=错误接收的码元数/接收的总码元数（2）几种冗余校验方法垂直冗余校验水平冗余校验水平垂直冗余校验循环冗余校验WeihongChenHunanCityUniversitySep’10CN垂直奇偶校验垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所有奇数个错，但检测不出偶数个的错，如下图所示，因而对差错的漏检率接近1/2。位\数字0123456789C10101010101C20011001100C30000111100C40000000011C51111111111C61111111111C70000000000偶C00110100110奇1001011001垂直奇偶校验方式WeihongChenHunanCityUniversitySep’10CN水平奇偶校验水平奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度=p的所有突发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。位\数字0123456789偶校验C101010101011C200110011000C300001111000C400000000110C511111111111C611111111111C700000000000水平奇偶校验方式水平垂直校验水平垂直校验(LRC)又叫报文校验、方块校验。将若干水平奇偶校验码排成若干行，然后