CSE 123 Lecture Notes - Lecture 4: Frame Check Sequence, Xor Gate, Checksum
19 views2 pages
- simply sum ALL of the data in the frame
- extremely “lightweight” (fast to compute)
- fragile: Hamming Distance of 2
Checksum in Hardware
- Modulo-2 Arithmetic (ALL math but no carry bits!)
- addition/subtraction is simply XOR
- need ONLY a “word-length” shift register and XOR gate
- assume data arrives “serially”
- ALL registers initially 0
Addition & subtraction are XOR
- 1+1 = 0; 0 - 1 = 1 (no carries!)
From Sums to Remainders
- checksums are easy to compute, but VERY fragile
- burst errors - frequently undetected
- want a scheme that “smears” parity
Cyclic Remainder Check
- idea is to divide the incoming data, D, rather than add
- divisor is called the generator, g
- CRC resilient to k-bit burst errors!
- need a generator of k+1 bits (where MSB is always 1)
- divide 2kD by g to get remainder, r
- remainder is called frame check sequence
- send 2kD - r (i.e., 2kD XOR r)
- 2kD is just D shifted left k bits!
- remainder must be AT MOST k bits
- receiver checks that (2kD-r)/g = 0
CRC: Rooted in Polynomials
- we’re ACTUALLY doing polynomial arithmetic
Ex: 1101 is (1*x3) + (1*x2) + (0*x1) + (1*x0)
CRC Example Encoding
x3 + x2 + 1 = 1101 generator
X7 + x4 + x3 + x = 10011010 Message
10011010000 ← message plus k zeros (generator is k+1 bits!)
Does this number divide into the generator?
- it has a remainder of 5!
Simply sum all of the data in the frame. Modulo-2 arithmetic (all math but no carry bits!) Need only a word-length shift register and xor gate. 1+1 = 0; 0 - 1 = 1 (no carries!) Need a generator of k+1 bits (where msb is always 1) 2kd is just d shifted left k bits! Remainder must be at most k bits. Checksums are easy to compute, but very fragile. Idea is to divide the incoming data, d, rather than add. Divide 2kd by g to get remainder, r. Send 2kd - r (i. e. , 2kd xor r) Ex: 1101 is (1*x3) + (1*x2) + (0*x1) + (1*x0) Crc example encoding x3 + x2 + 1. 10011010000 message plus k zeros (generator is k+1 bits!) Receiver checks if this number divides evenly into the generator 1101. If remainder is not 0, then crc test failed.