CRC (Cyclic Redundancy Check)

Encoding

Given a frame and a generator polynomial of the form x^n + ax^n-1+...+1. The following conditions must hold:

1. The size of the frame must be longer than the degree of the polynomial.
2. The polynomial can only have coefficients of 1 or 0.
3. The first and last coefficients must be 1.

Let G be the binary representation of the generator polynomial (e.g. 1101), Let D be the data from the frame. We define r=n from the generator polynomial (or the number of bits in G - 1).

To Encode the CRC as part of the data:

1. Take the frame and add n 0s to the end of it where n is the degree of the polynomial
2. Treating the frame as a polynomial divide it by the generator polynomial using twos complement addition
3. Take the remainder and add it on to the original frame.
4. Send the Checked frame to the receiver.

Decoding

To Decode the Checked Frame:

1. Divide the received (checked) frame by the generator polynomial
2. If there exists a remainder than there was an error.