Parity Checking Single Bit Parity: Two Dimensional Bit Parity: Detect single bit errors Detect and correct single bit errors row parity parity d data bits d1,1 dij nbit d1,j+1 d21 d2i d2,j+1 01110001101010110 column d,1 dij di,j+1 parity di+1,1 di+1}di+1,j+1 101011 1Φ101h 111100 101100parity error 011101 011101 001010 001010 no errors parity error correctable single bit error 5:DataLink Layer 5-11
5: DataLink Layer 5-11 Parity Checking Single Bit Parity: Detect single bit errors Two Dimensional Bit Parity: Detect and correct single bit errors 0 0
Internet checksum Goal:detect "errors"(e.g.,flipped bits)in transmitted segment (note:used at transport layer only) Sender: Receiver: compute checksum of received treat segment contents as sequence of 16-bit segment integers check if computed checksum equals checksum field value: checksum:addition(1's o NO-error detected complement sum)of o yES-no error detected.But segment contents maybe errors nonetheless? ▣sender puts checksum More later . value into UDP checksum field 5:DataLink Layer 5-12
5: DataLink Layer 5-12 Internet checksum 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? More later . Goal: detect “errors” (e.g., flipped bits) in transmitted segment (note: used at transport layer only)
Checksumming:Cyclic Redundancy Check 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) o receiver knows G,divides <D,R>by G.If non-zero remainder: error detected! o can detect all burst errors less than r+1 bits widely used in practice(ATM,HDLC) d bits →←一r bits bit D:data bits to be sent R:CRC bits pattern D*2「XORR mathematical formula 5:DataLink Layer 5-13
5: DataLink Layer 5-13 Checksumming: Cyclic Redundancy Check 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 (ATM, HDLC)
CRC Example Want: D2r XORR=nG 101011 equivalently: G 903 101110000 1001 D D2r=nG XOR R 101 equivalently: 000 1010 if we divide D.2r by 1001 G,want remainder R 110 000 1100 1001 1010 B=remainder[ 1001 011 5:DataLink Layer 5-14
5: DataLink Layer 5-14 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 R = remainder[ ] D.2 r G
Link Layer ▣5.1 Introduction and ▣5.6 Hubs and switches services ▣5.7PPP 口5.2 Error detection 5.8 Link Virtualization: and correction ATM 5.3Multiple access protocols ▣5.4Link-Layer Addressing ▣5.5 Ethernet 5:DataLink Layer 5-15
5: DataLink Layer 5-15 Link Layer 5.1 Introduction and services 5.2 Error detection and correction 5.3Multiple access protocols 5.4 Link-Layer Addressing 5.5 Ethernet 5.6 Hubs and switches 5.7 PPP 5.8 Link Virtualization: ATM