Berkeley ELENG 122 - Error detection and reliable transmission - D2979147

Home> Schools> University of California, Berkeley> Electrical Engineering (ELENG) > ELENG 122> Error detection and reliable transmission

DOC PREVIEW

Berkeley ELENG 122 - Error detection and reliable transmission

School name University of California, Berkeley

Course Eleng 122- Introduction to Communication Networks

Pages 30

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save

View full document

Premium Document

Do you want full access? Go Premium and unlock all 30 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

View full document

Premium Document

Do you want full access? Go Premium and unlock all 30 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

View full document

Premium Document

Do you want full access? Go Premium and unlock all 30 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

View full document

Premium Document

Do you want full access? Go Premium and unlock all 30 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

View full document

Premium Document

Do you want full access? Go Premium and unlock all 30 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

View full document

Premium Document

Do you want full access? Go Premium and unlock all 30 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

Premium Document

Do you want full access? Go Premium and unlock all 30 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

Unformatted text preview:

EE122:ErrordetectionandreliabletransmissionIonStoicaSeptember16,[email protected] 2HighLevelViewGoal:transmitcorrectinformationProblem:bitscangetcorrupted- Electricalinterference,thermalnoiseSolution- Detecterrors- Recoverfromerrors• Correcterrors• [email protected] 3OverviewErrordetectionReliable[email protected] 4ErrorDetectionProblem:detectbiterrorsinpackets(frames)Solution:addredundancy bitstoeachpacketGoals:- Reduceoverhead,i.e.,reducethenumberofredundancybits- IncreasethenumberandthetypeofbiterrorpatternsthatcanbedetectedExamples:- Two-dimensionalparity- Checksum- CyclicRedundancyCheck(CRC)[email protected] 5Two-dimensionalParityAddoneextrabittoa7-bitcodesuchthatthenumberof1’sintheresulting8bitsiseven(forevenparity,andoddforoddparity)AddaparitybyteforthepacketExample:five7-bitcharacterpacket,evenparity01101001011010001011011101011001011101101000110 [email protected] 6HowManyErrorsCanyouDetect?All1-biterrorsExample:01101001011010000011011101011001011101101000110 1errorbitoddnumberof1’[email protected] 7HowManyErrorsCanyouDetect?All2-biterrorsExample:01101001011010000011111101011001011101101000110 1errorbitsoddnumberof1’son[email protected] 8HowManyErrorsCanyouDetect?All3-biterrorsExample:01101001011010000011111001011001011101101000110 1errorbitsoddnumberof1’son[email protected] 9HowManyErrorsCanyouDetect?Most4-biterrorsExampleof4-biterrorthatisnot detected:01101001011010000011111001001001011101101000110 1errorbitsHowmanyerrorscanyou[email protected] 10ChecksumSender:addallwordsofapacketandappendtheresult(checksum)tothepacketReceiver:addallwordsofapacketandcomparetheresultwiththechecksumCandetectall1-biterrorsExample:Internetchecksum- Use1’scomplement[email protected] 111’sComplementRevisitedNegativenumber–xisxwithallbitsinvertedWhentwonumbersareadded,thecarry-onisaddedtotheresultExample:-15+16;assume8-bitrepresentation15= 00001111-15=1111000016=00010000+000000001+100000001-15+16=[email protected] 12CyclicRedundancyCheck(CRC)Representa(n+1)-bitmessagebyann-degreepolynomialM(x)- E.g.,10101101M(x)=x7+x5+x3+x2+x0Chooseadivisork-degreepolynomialC(x)ComputereminderR(x)ofM(x)*xk/C(x),andthencomputeT(x)=M(x)*xk- R(x)- T(x)isdivisiblebyC(x)- FirstncoefficientsofT(x)representM(x)Sender:- ComputeandsendT(x),i.e.,thecoefficientsofT(x)Receiver:- LetT’(x)bethe(n+k)-degreepolynomialgeneratedfromthereceivedmessage- IfC(x)dividesT’(x)noerrors;otherwise[email protected] 13SomePolynomialArithmeticModulo2PropertiesIfC(x)dividesB(x),thendegree(B(x))>=degree(C(x))SubtractingC(x)fromB(x)reducestoperformanXORoneachpairofmatchingcoefficientsofC(x)andB(x)- E.g.:B(x)=x7+x5+x3+x2+x010101101C(x)=x3+x1+x000001011B(x)- C(x)=x7+x5+x2+x1[email protected] 14ComputingT(x)ComputethereminderR(x)ofM(x)*xk/C(x)T(x)=M(x)*xk- R(x)Example:sendpacket110111,assumeC(x)=101- k=2,M(x)*xK11011100- ComputeR(x)- T(x)=M(x)*xk- R(x)11011100xor1=11011101101)110111001011111011011011001011R(x)[email protected] 15CRCPropertiesDetectallsingle-biterrorsifcoefficientsofxkandx0ofC(x)areoneDetectalldouble-biterrors,ifC(x)hasafactorwithatleastthreetermsDetectallnumberofodderrors,ifC(x)containsfactor(x+1)Detectallburstoferrorssmallerthankbits[email protected] 16OverviewErrordetectionReliable[email protected] 17ReliableTransmissionProblem:obtaincorrectinformationonceerrorsaredetectedSolutions:- Useerrorcorrectioncodes(canyougiveanexampleoferrordetectioncodethatcanalsocorrecterrors?)- Useretransmission(we’lldothisindetails)Algorithmicchallenges:- Achievehighlinkutilization,andlow[email protected] 18Latency,Bandwidth,Round-TripTimeLatency=propagation+transmit+queue- Propagation:timeittakesthesignaltopropagatealongthelink- Transmit:timeittakestotransmitthepacket=(packet_size)/(link_bandwidth)- Queue:timeforwhichthepacketwaitsintotheadapteratthesenderbeforebeingtransmittedNote:nextwe’llassumeshortpackets,i.e,transmittermcanbeneglected!Round-TripTime(RTT)=timeittakestoapackettotravelfromsendertodestinationandback- RTT=one-waylatencyfromsendertoreceiver+one-waylatencyfromreceiverto[email protected] 19AutomaticRepeatRequest(ARQ)AlgorithmsUsetwobasictechniques:- Acknowledgements(ACKs)- TimeoutsTwoexamples:- Stop-and-go- Sliding[email protected]

View Full Document

Berkeley ELENG 122 - Error detection and reliable transmission

Sign up for free to view:

This document and 3 million+ documents and flashcards
High quality study guides, lecture notes, practice exams
Course Packets handpicked by editors offering a comprehensive review of your courses
Better Grades Guaranteed


School:
Email:
New Password:
Confirm Password:

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Berkeley ELENG 122 - Error detection and reliable transmission

Sign up for free to view:

Please select your school