Error detection EDC=Error Detection and Correction bits(redundancy) D Data protected by error checking,may include header fields ·Error detection not1o0%reliable！ protocol may miss some errors,but rarely larger EDC field yields better detection and correction datagram datagram otherwisel all bits in D' OK detected error +-d data bits 0 EDC D EDC' bit-error prone link Link Layer 5-11
Link Layer 5-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
Parity checking single bit parity: two-dimensional bit parity: detect single bit detect and correct single bit errors errors row parity parity d1,1 d1,j d1,j+1 d data bits bit d2,1 d2i d2,j+1 01110001101010110 。·· column d,1 di.j di,j+1 parity di+1,1 di+1}di+1,j+1 101011 10101h 111100 101100parity error 011101 011101 001010 001010 no errors parity error correctable single bit error Link Layer 5-12
Link Layer 5-12 Parity checking single bit parity: detect single bit errors two-dimensional bit parity: detect and correct single bit errors 0 0
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 checksum equals (1's complement sum) checksum field value: of segment contents ■NO-error detected sender puts checksum ■YES-no error value into UDP detected.But maybe checksum field errors nonetheless? Link Layer 5-13
Link Layer 5-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 )
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) -d bits- →←一r bits+ bit D:data bits to be sent R:CRC bits pattern D*2「XORR mathematical formula Link Layer 5-14
Link Layer 5-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)
CRC example want: G D r=3 D.2r XOR R=nG 101000 equivalently: 1001D0111000 D2=nG XOR R 1001 101 equivalently: 000 if we divide D.2r by 1010 G,want remainder 1001 R to satisfy: 010 000 100 R=remainder[ D:2r G R 000 1000 0000 1000 Link Layer 5-15
Link Layer 5-15 CRC example want: D. 2r XOR R = nG equivalently: D. 2r = nG XOR R equivalently: if we divide D. 2r by G, want remainder R to satisfy: R = remainder[ ] D. 2 r G 1001 101110000 1001 1 101 01000 000 1010 1001 010 000 100 000 1000 0000 1000 G D R r = 3