Division over GF(2)

XOR Is Binary Add

CRC arithmetic uses XOR instead of carried addition. This lesson pins the bit rule before the long-division matrix appears.

highlighted = computed this step

Why CRC arithmetic is different

CRC arithmetic happens over two symbols, so addition and subtraction are both XOR. That means there are no carries to propagate.

symbols=2\text{symbols}=2

XOR examples

1 XOR 1 gives 0, while 1 XOR 0 gives 1.

1⊕1=0,1⊕0=11\oplus1=0,\quad1\oplus0=1

Why this matters

Long division for CRCs uses XOR where ordinary division would subtract. The matrix in the next lessons is built from that rule.

carry=0\text{carry}=0
One bitA single bit is still rendered from exact data.One bit8 bits / 1 byte0x80byte 010000000rest0000000bit: set

Summary

In GF(2), adding and subtracting bits is XOR with no carry. Polynomial arithmetic over the exact bits; timing/throughput is not modeled here.

carry=0\text{carry}=0
One bitA single bit is still rendered from exact data.One bit8 bits / 1 byte0x80byte 010000000rest0000000bit: set