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

19 views2 pages

Published on 5 Oct 2018

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!)

- 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!

Send: 10011010101

## Document Summary

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.