Error detection EDC=Error Detection and Correction bits(redundancy) D Data protected by error checking,may include header fields ·Error detection not1oo%reliable！ protocol may miss some errors,but rarely larger EDC field yields better detection and correction ↑ datagram datagram otherwisel all bits in D N OK detected error ←d data bits- D EDC D EDC' bit-error prone link Link Layer and LANs 6-11
Error detection EDC= Error Detection and Correction bits (redundancy) D = Data protected by error checking, may include header fields • Error detection not 100% reliable! • protocol may miss some errors, but rarely • larger EDC field yields better detection and correction otherwise Link Layer and LANs 6-11
Parity checking single bit parity: two-dimensional bit parity: detect single bit detect and correct single bit errors errors row parity parity d1,1 d1j d1,j+1 d data bits bit d2,1 d2l d2,j+1 ··· 。。。 。。. 0111000110101011 0 column di1 dij di,j+1 parity d+1,1 d+1}d+1,j+1 10101h 10101h 111100 101109- parity error 011101 011101 001016 001010 no errors parity error correctable Check out the online interactive exercises for more single bit error examples:http://gaia.cs.umass.edu/kurose_ross/interactive/ Link Layer and LANs 6-12
Parity checking single bit parity: ▪ detect single bit errors two-dimensional bit parity: ▪ detect and correct single bit errors 0 0 Link Layer and LANs 6-12 * Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive/
Internet checksum(review) goal:detect "errors"(e.g.flipped bits)in transmitted packet (note:used at transport layer only) sender: receiver: treat segment contents ■compute checksum of as sequence of 16-bit received segment integers check if computed ■ checksum:addition (I's checksum equals checksum complement sum)of field value: segment contents ·NO-error detected ■ sender puts checksum YES-no error detected. value into UDP But maybe errors checksum field nonetheless? Link Layer and LANs 6-13
Internet checksum (review) sender: ▪ treat segment contents as sequence of 16-bit integers ▪ checksum: addition (1’ s complement sum) of segment contents ▪ sender puts checksum value into UDP checksum field receiver: ▪ compute checksum of received segment ▪ check if computed checksum equals checksum field value: • NO - error detected • YES - no error detected. But maybe errors nonetheless? goal: detect “ errors ” (e.g., flipped bits) in transmitted packet (note: used at transport layer only) Link Layer and LANs 6-13
Cyclic redundancy check more powerful error-detection coding view data bits,D,as a binary number choose r+I bit pattern(generator),G goal:choose r CRC bits,R,such that <D,R>exactly divisible by G(modulo 2) receiver knows G,divides <D,R>by G.If non-zero remainder: error detected! can detect all burst errors less thanr+l bits widely used in practice(Ethernet,802.I I WiFi,ATM) d bits- →←一r bits- bit D:data bits to be sent R:CRC bits pattern D*2「XORR mathematical formula Link Layer and LANs 6-14
Cyclic redundancy check ▪ more powerful error-detection coding ▪ view data bits, D, as a binary number ▪ choose r+1 bit pattern (generator), G ▪ goal: choose r CRC bits, R, such that • <D,R> exactly divisible by G (modulo 2) • receiver knows G, divides <D,R> by G. If non-zero remainder: error detected! • can detect all burst errors less than r+1 bits ▪ widely used in practice (Ethernet, 802.11 WiFi, ATM) Link Layer and LANs 6-14
CRC example G 101011 want: 1001 101110000 D.2r XOR R=nG 1001 equivalently: 101 000 D D.2r=nG XOR R 1010 equivalently: 1001 if we divide D.2r by 110 000 G,want remainder R 1100 to satisfy: 1001 1010 1001 R=remainder[ D.2r G 011 R *Check out the online interactive exercises for more examples:http://gaia.cs.umass.edu/kurose_ross/interactive/ Link Layer and LANs 6-15
CRC example want: D.2 r XOR R = nG equivalently: D.2 r = nG XOR R equivalently: if we divide D.2 r by G, want remainder R to satisfy: R = remainder[ ] D.2 r G Link Layer and LANs 6-15 * Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive/