Cyclic redundancy check
The conceptHow a ZIP file knows one of its bits got flipped
A cyclic redundancy check (CRC) is a short fingerprint calculated from the data, saved next to it and calculated again on arrival. If the two don't match, the data was damaged.
The trick is to treat the bits as a polynomial: 1101 means x³ + x² + 1. The sender divides that polynomial by a fixed 'generator' polynomial, everyone using the same CRC standard uses the same one, and keeps the remainder as the check bits.
The arithmetic has no carries: adding and subtracting are both just XOR (exclusive or, where 1+1 gives 0). So the division is a run of shifts and XORs, like long division with simpler steps.
What it’s forCalculates the check bits a sender attaches to a message.
R(x) = M(x) · xⁿ mod G(x)
- M(x)
- the message bits read as a polynomial
- G(x)
- the agreed generator polynomial, e.g. 1011 = x³ + x + 1
- n
- the degree of G, which is also the number of check bits (32 for CRC-32)
- R(x)
- the remainder: the n check bits that are sent along
What it givesA message plus check bits that divides evenly by G, so the receiver expects a remainder of zero.
- Message 1101, G = 1011, n = 3: append 000 → 1101000
- XOR-divide 1101000 by 1011 → remainder 001
- Send 1101001; dividing it by 1011 leaves 000, so it is accepted