Differences between revisions 1 and 2
⇤ ← Revision 1 as of 2003-09-02 16:23:26 →
Size: 881
Editor: velociraptor
Comment:
← Revision 2 as of 2003-09-02 16:25:11 → ⇥
Size: 916
Editor: velociraptor
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
= CRC (Cyclic Redundancy Check)
== Encoding:		 = CRC (Cyclic Redundancy Check) =
== Encoding ==
Line 6: Line 6:
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.		    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.
Line 11: Line 11:
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.		    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.
Line 16: Line 16:
== Decoding: == Decoding ==
Line 19: Line 19:
1. Divide the received (checked) frame by the generator polynomial
2. If there exists a remainder than there was an error.		    1. Divide the received (checked) frame by the generator polynomial
   2. If there exists a remainder than there was an error.
Line 22: Line 22:
== Errors Detected: == Errors Detected ==

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.

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.

Errors Detected

CyclicRedundancyCheck (last edited 2014-11-12 18:35:55 by scot)