Parity checking Single Bit Parity: Two Dimensional Bit Parity: Detect single bit errors Detect and correct single bit errors d data bits -parity d 1,j+1 bit 2,1 d 2j+1 011001010 d olumn 1.1 d 101011 11011 1111oO 王(11)Pa error 011101 01110n 001010 0101o no errors parIty error correctab/e single bit error 5: DataLink Lo
5: DataLink Layer 5a-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: o treat segment contents g compute checksum of received segment as sequence of 16-bit Integers o check if computed checksum equals checksum field value 口 checksum: addition(1s 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 5a-12
5: DataLink Layer 5a-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 o view data bits, d, as a binary number o choose r+1 bit pattern(generator), G o goal: choose r CRC bits, R, such that o D, R> exactly divisible byG(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 o widely used in practice (ATM, HDCL) -d bits ← r bits→ bit D: data bits to be sent R: CRC bits pattern mathematical D*2 XOR R formula 5: DataLink Layer 5a-13
5: DataLink Layer 5a-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, HDCL)
CRC Example Want D2r XoRR= nG 10101 equivalently 100 01110000 G 100 D D2r= nG XOR R 101 equivalently 000 010 if we divide D 2r 1001 G want remainder r 110 000 1100 1001 1010 R remainder D2r 1001 01 5: DataLink Layer 5a-14
5: DataLink Layer 5a-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
Chapter 5 outline g 5.1 Introduction and 口56Hubs, bridges,and services switches 0 5.2 Error detection g 5.7 Wireless links and and correction LANS 0 5. 3 Multiple access 05. 8 PPP protocols 059ATM 0 5.4 LAN addresses o 5.10 Frame Relay and Arp 0 5.5 Ethernet 5: DataLink Layer 5a-15
5: DataLink Layer 5a-15 Chapter 5 outline 5.1 Introduction and services 5.2 Error detection and correction 5.3Multiple access protocols 5.4 LAN addresses and ARP 5.5 Ethernet 5.6 Hubs, bridges, and switches 5.7 Wireless links and LANs 5.8 PPP 5.9 ATM 5.10 Frame Relay