# CSE 123 Lecture Notes - Lecture 4: Frame Check Sequence, Xor Gate, Checksum

19 views2 pages
Published on 5 Oct 2018
School
UCSD
Department
Computer Science and Engineering
Course
CSE 123
Professor
Checksums
- 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!)
- need ONLY a “word-length” shift register and XOR gate
- assume data arrives “serially”
- ALL registers initially 0
- 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!
Send: 10011010101
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.