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

• School: UCSD
• Department: Computer Science and Engineering
• Course: CSE 123
• Professor: Alex Snoeren

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.