Differences between revisions 1 and 3 (spanning 2 versions)
⇤ ← Revision 1 as of 2003-09-02 16:23:26 →
Size: 881
Editor: velociraptor
Comment:
← Revision 3 as of 2014-11-12 18:35:55 → ⇥
Size: 1083
Editor: scot
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.

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).
Line 11: Line 13:
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 18:
== Decoding: == Decoding ==
Line 19: Line 21:
1. Divide the received (checked) frame by the generator polynomial
2. If there exists a remainder than there was an error.

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

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.

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