CRC (Cyclic Redundancy Check)

Detect transmission errors by dividing the frame by a fixed generator and sending the remainder along with it.

CRC treats your data as one giant binary number and divides it by a fixed bit pattern called the generator. The leftover — the remainder — is a short fingerprint appended to the frame. The receiver divides the whole received frame by the *same* generator: if the remainder comes out zero, the bits almost certainly arrived intact; if it's anything else, the frame was corrupted in transit.

The pieces

1Generator — a bit pattern both sides agree on in advance. Its length sets the CRC size: a k+1-bit generator produces a k-bit CRC. 1011 (4 bits) gives a 3-bit remainder.
2Append zeros — before dividing, the sender appends k zero bits to the data (one fewer than the generator's length), making room for the CRC.
3XOR division — divide using XOR instead of subtraction. There are no borrows or carries; you just cancel bits that match.
4Remainder — whatever is left becomes the CRC. Replace the appended zeros with it and transmit data + CRC together.

Why XOR, not subtraction

XOR asks 'are these bits different?' — 1 if they differ, 0 if they match. That makes binary long division mechanical: wherever the current leading bit is 1, line the generator up and XOR; wherever it's 0, the quotient bit is 0 and you slide on. No carrying to track.

Worked example: data 1010, generator 1011

The generator 1011 is 4 bits, so the CRC is 3 bits and we append 3 zeros to the data: 1010 becomes 1010000. Now XOR-divide by 1011. Each time the leftmost remaining 1 lines up, XOR the generator under it.

  1 0 1 0 0 0 0     data 1010 with 3 zeros appended
^ 1 0 1 1           generator lines up under the leading 1
  -----------
  0 0 0 1 0 0 0
      ^ 1 0 1 1     slide right to the next leading 1, XOR again
      -----------
  0 0 0 0 0 1 1     remainder = 011  <- the CRC

So the CRC is `011`. The sender transmits the data with the remainder in place of the zeros: 1010 + 011 = `1010011`. To verify, the receiver divides 1010011 by 1011 — the same XOR division now leaves remainder 000, so no error is flagged.

CRC detects, it does not correct

A non-zero remainder only tells you *something* changed — it can't say which bit. The frame is discarded and (in a reliable protocol) retransmitted. A well-chosen generator catches every burst error shorter than the generator and all single- and double-bit errors, but a rare corruption can still divide cleanly and slip through.

OperationTimeSpace

Compute / check CRC · one XOR pass over n frame bitsO(n)O(1)

Check yourself

The receiver divides the received frame by the agreed generator. What remainder means 'no error detected'?