CRC / XOR / Modulo-2 Long Division Calculator

How to use the CRC / XOR / Modulo-2 Long Division Calculator

To compute a CRC by modulo-2 division, follow these 4 steps:

• Enter the binary message (data bits) in the first field.
• Enter the generator polynomial as binary bits in the second field.
• The calculator appends (n − 1) zero bits, where n is the generator length.
• Click Calculate to XOR down the message and read the remainder as the CRC.

The quotient is usually discarded in CRC work — the remainder is the checksum that gets appended to the message before transmission.

CRC and modulo-2 arithmetic

A cyclic redundancy check detects transmission errors by treating a message as a large binary polynomial and dividing it by an agreed generator polynomial. The division is done in modulo-2 (GF(2)) arithmetic, where addition and subtraction are identical and equal to XOR — there are no carries or borrows. The remainder from this division is the CRC. When the receiver divides the message plus CRC by the same generator, a remainder of 0 means no detected error. This calculator reproduces that exact bitwise process.

How modulo-2 CRC division works

The calculator computes the CRC through five internal actions:

• Appends (n − 1) zero bits to the message, where n is the number of generator bits.
• Aligns the generator under the leftmost 1 bit of the current remainder.
• XORs the generator into those bits (modulo-2 subtraction with no borrow).
• Shifts to the next leading 1 bit and repeats the XOR alignment.
• Stops when the remaining bits are fewer than the generator; those bits are the CRC.

Each quotient bit is 1 wherever the generator is XORed in and 0 elsewhere, but for CRC only the final remainder matters.

Formula for CRC division

The CRC / XOR / Modulo-2 Long Division Calculator computes CRC = (M(x) · xⁿ⁻¹) mod G(x) in GF(2), where M(x) is the message, G(x) is the generator of n bits, and all additions are XOR. The transmitted frame is M(x)·xⁿ⁻¹ + CRC, which G(x) divides exactly. On the receive side, a zero remainder confirms integrity.

CRC / XOR example problems

These examples show modulo-2 division with XOR at each step.

Example 1 — Message 1101, generator 101

1. Generator length 3, so append 2 zeros: 1101 becomes 110100.
2. XOR 101 into the leading bits repeatedly: 110100 → 011100 → 001000 → 000010.
3. The last 2 bits, 10, are the CRC remainder.

Example 2 — Why subtraction is XOR

1. In modulo-2, 1 + 1 = 0 and 1 − 1 = 0, so add and subtract are the same operation.
2. That operation is exactly bitwise XOR, with no carry or borrow.
3. So each division step is one XOR of the generator into the current bits.

Example 3 — Receiver check

1. Append the CRC to the message and divide by the same generator.
2. XOR down exactly as before.
3. A remainder of 0 means no error was detected.

Generator length 3, so append 2 zeros: 1101 becomes 110100.
XOR 101 into the leading bits repeatedly: 110100 → 011100 → 001000 → 000010.
The last 2 bits, 10, are the CRC remainder.

In modulo-2, 1 + 1 = 0 and 1 − 1 = 0, so add and subtract are the same operation.
That operation is exactly bitwise XOR, with no carry or borrow.
So each division step is one XOR of the generator into the current bits.

Append the CRC to the message and divide by the same generator.
XOR down exactly as before.
A remainder of 0 means no error was detected.

Worked CRC problems

How do you compute the CRC of 10110 with generator 1011?

Append 3 zeros (generator length 4) to get 10110000, then XOR down. Align 1011 under each leading 1 and XOR: 10110000 → 00100000 → after successive XORs the final 3 bits form the CRC remainder. The remainder is then appended to 10110 so the full frame is divisible by 1011 with no remainder.

Why does a zero remainder mean the data is intact?

The sender chose the CRC so the transmitted frame is an exact multiple of the generator. Any multiple of G(x) divided by G(x) leaves remainder 0. If bits flip in transit, the frame is usually no longer a multiple, so the receiver's division leaves a non-zero remainder, flagging an error.

Common CRC / modulo-2 mistakes

Modulo-2 CRC division produces 5 frequent errors:

• Using ordinary binary subtraction with borrows instead of XOR.
• Appending the wrong number of zero bits (it must be generator length minus one).
• Aligning the generator under a 0 bit instead of the leading 1.
• Treating carries as if they exist in GF(2) arithmetic.
• Reporting the quotient as the CRC instead of the remainder.

The CRC / XOR / Modulo-2 Long Division Calculator XORs at every step, appends the correct zeros, and returns the remainder as the checksum.

Frequently Asked Questions