In a cyclic redundancy check, what is divided by what, and in which arithmetic?

middlemust knowfreq 60%

answer

bits read as polynomial coefficients
carry-free arithmetic, add means XOR
shift left by the generator's degree
remainder, not quotient, is transmitted
codeword becomes an exact multiple

basics

~20 s

A CRC reads the frame's bits as the coefficients of a polynomial, shifts it left by the generator's degree r, and divides by a fixed generator polynomial in GF(2) arithmetic, where addition is XOR and nothing carries. The r-bit remainder is the check field.

solid answer

~50 s

Both ends agree on a fixed generator polynomial G(x) of degree r, where r is the width of the check field. The sender reads the frame's bits as the coefficients of a polynomial M(x), multiplies by x^r (a left shift that opens r zero bits at the end), and long-divides by G(x). The arithmetic is GF(2): every coefficient is 0 or 1, addition and subtraction are both XOR, and no step carries or borrows, so each division step is just "if the top bit is set, XOR the generator in, aligned to it". The remainder has degree below r, so it fits exactly into the r-bit check field, and it is sent in the gap the shift opened. Because subtracting is the same as adding here, the transmitted frame is an exact multiple of G(x), and the receiver's own division over everything it received should leave a known residue.

Both ends agree on a fixed **generator polynomial** `G(x)` of degree `r`, where `r` is the width of the check field. The sender reads the frame's bits as the coefficients of a polynomial `M(x)`, multiplies by `x^r` (a left shift that opens r zero bits at the end), and long-divides by `G(x)`. The arithmetic is GF(2): every coefficient is 0 or 1, addition and subtraction are both XOR, and no step carries or borrows, so each division step is just "if the top bit is set, XOR the generator in, aligned to it". The remainder has degree below `r`, so it fits exactly into the r-bit check field, and it is sent in the gap the shift opened. Because subtracting is the same as adding here, the transmitted frame is an exact multiple of `G(x)`, and the receiver's own division over everything it received should leave a known residue.

code

pseudocode · 14 lines

pseudocode

# G is the generator, degree r, held as r+1 coefficient bits
remainder = 0

for each bit b of message, most significant first:
    remainder = (remainder shifted left by 1) OR b
    if bit r of remainder is set:
        remainder = remainder XOR G       # subtract G, aligned, to clear it

repeat r times:                           # feed in the r appended zero bits
    remainder = remainder shifted left by 1
    if bit r of remainder is set:
        remainder = remainder XOR G

check_field = remainder                   # degree below r, so exactly r bits

go deeper

for a junior

Remember the shape: a fixed divisor both sides know, a division over the frame's bits, and the leftover travels in a small fixed-width field beside the data.

for a middle

Be able to explain that the arithmetic is carry-free XOR, that the message is shifted left by the generator's degree before dividing, and that appending the remainder makes the codeword an exact multiple of the generator.

for a senior

Explain why the detection argument is stated over error patterns rather than messages, and why mismatched parameters — initial register, final inversion, bit reflection, field byte order — are the interoperability bug that shows up only on the wire.

for a principal

The judgement is where the check sits and what it covers: a per-hop division protects a wire, not a pipeline, so decide deliberately which bytes are inside the covered region and whether anything above it needs its own end-to-end check.

The one-sentence version

A cyclic redundancy check treats a block of bits as a polynomial, divides it by a fixed generator polynomial that both ends of the link already agree on, and transmits the remainder in a fixed-width field beside the data. The receiver repeats the division over everything it received and checks the residue. Nothing in the scheme is secret and nothing is random: it is ordinary long division, in an arithmetic where addition never carries.

Bits as a polynomial

Read the bits of a frame as coefficients, most significant first. The four bits 1101 become x^3 + x^2 + 1. The polynomial is only bookkeeping — it gives "shift" and "XOR" the names "multiply by x" and "add", so a century of algebra applies to a shift register.

A frame of n bits is a polynomial of degree at most n - 1.
The generator G(x) has degree r, and r is exactly the width of the check field in bits — degree 16 gives a 16-bit field, degree 32 a 32-bit one.
Multiplying by x^r is a left shift by r places: it appends r zero bits, opening the hole the check field will occupy.

GF(2): arithmetic without carries

Every coefficient lives in the two-element field GF(2), so all arithmetic is modulo 2:

1 + 1 = 0, which makes addition and subtraction the same operation, and that operation is bitwise XOR.
No step ever produces a carry or consumes a borrow, so the whole computation is a shift register and an XOR gate.
Division means what it means over the integers: repeatedly subtract a shifted copy of the divisor until what remains has lower degree than the divisor.

The division, step by step

Shift the message left by r bits, forming M(x) · x^r.
Divide by G(x): walk the bits from the top, and whenever the bit at position r of the working register is set, XOR G(x) in, aligned there, to clear it.
What is left when the bits run out is the remainder R(x), of degree strictly below r — so it is exactly r bits, never more.
Transmit T(x) = M(x) · x^r + R(x): the original frame with R sitting in the gap the shift opened.

Because adding and subtracting are the same here, step 4 is simultaneously "append the remainder" and "subtract the remainder", so T(x) is a message with its remainder removed. G(x) divides T(x) exactly. That is the invariant the whole scheme rests on.

Why the receiver's test works

The receiver sees T(x) + E(x), where E(x) is the pattern of flipped bits and is zero when the frame arrived clean. Dividing by G(x), the T part contributes nothing because it is an exact multiple, so the residue is determined entirely by E(x). A clean residue therefore means one of two things: no bits flipped, or the flipped pattern happened to be a multiple of the generator. This is why every guarantee a CRC offers is phrased as a property of error patterns and never as a property of messages.

Parameters that vary between specifications

Two implementations of "the same" CRC frequently disagree, because published definitions bolt extra parameters onto the raw division. They matter for interoperability and not for the mathematics of detection.

Parameter	What it changes	What it does not change
Initial register value (often all ones)	Leading zero bits now affect the result	Which error patterns are detected
Final inversion of the remainder	An all-zero frame no longer yields an all-zero check field	Which error patterns are detected
Bit reflection of input and output	The order bits enter the register and leave the field	The generator's degree and field width
Byte order of the check field	How the `r` bits are laid into the frame	Anything algebraic

The first two are fixed offsets that cancel when you subtract two codewords, which is why the detection guarantees survive them untouched. All four break interoperability silently when two vendors read the specification differently, because the field looks perfectly well-formed and simply never matches.

Cost in practice

The bit-at-a-time loop is one shift and a conditional XOR per bit of the frame — trivial in hardware, slow in software.
The usual software form precomputes a 256-entry table, one entry per possible byte value, and advances a byte per step, so the cost is linear in the frame's length and independent of the generator's degree.
Either way the work is proportional to the number of bits covered, which is why a link layer can afford to check every frame it ever sees.

## The one-sentence version A cyclic redundancy check treats a block of bits as a polynomial, divides it by a fixed **generator polynomial** that both ends of the link already agree on, and transmits the **remainder** in a fixed-width field beside the data. The receiver repeats the division over everything it received and checks the residue. Nothing in the scheme is secret and nothing is random: it is ordinary long division, in an arithmetic where addition never carries. ## Bits as a polynomial Read the bits of a frame as coefficients, most significant first. The four bits `1101` become `x^3 + x^2 + 1`. The polynomial is only bookkeeping — it gives "shift" and "XOR" the names "multiply by x" and "add", so a century of algebra applies to a shift register. - A frame of `n` bits is a polynomial of degree at most `n - 1`. - The generator `G(x)` has degree `r`, and `r` is exactly the width of the check field in bits — degree 16 gives a 16-bit field, degree 32 a 32-bit one. - Multiplying by `x^r` is a left shift by `r` places: it appends `r` zero bits, opening the hole the check field will occupy. ## GF(2): arithmetic without carries Every coefficient lives in the two-element field GF(2), so all arithmetic is modulo 2: - `1 + 1 = 0`, which makes addition and subtraction the **same operation**, and that operation is bitwise **XOR**. - No step ever produces a carry or consumes a borrow, so the whole computation is a shift register and an XOR gate. - Division means what it means over the integers: repeatedly subtract a shifted copy of the divisor until what remains has lower degree than the divisor. ## The division, step by step 1. Shift the message left by `r` bits, forming `M(x) · x^r`. 2. Divide by `G(x)`: walk the bits from the top, and whenever the bit at position `r` of the working register is set, XOR `G(x)` in, aligned there, to clear it. 3. What is left when the bits run out is the remainder `R(x)`, of degree strictly below `r` — so it is exactly `r` bits, never more. 4. Transmit `T(x) = M(x) · x^r + R(x)`: the original frame with `R` sitting in the gap the shift opened. Because adding and subtracting are the same here, step 4 is simultaneously "append the remainder" and "subtract the remainder", so `T(x)` is a message with its remainder removed. **`G(x)` divides `T(x)` exactly.** That is the invariant the whole scheme rests on. ## Why the receiver's test works The receiver sees `T(x) + E(x)`, where `E(x)` is the pattern of flipped bits and is zero when the frame arrived clean. Dividing by `G(x)`, the `T` part contributes nothing because it is an exact multiple, so the residue is determined entirely by `E(x)`. A clean residue therefore means one of two things: no bits flipped, or the flipped pattern happened to be a multiple of the generator. This is why every guarantee a CRC offers is phrased as a property of **error patterns** and never as a property of messages. ## Parameters that vary between specifications Two implementations of "the same" CRC frequently disagree, because published definitions bolt extra parameters onto the raw division. They matter for interoperability and not for the mathematics of detection. | Parameter | What it changes | What it does not change | | --- | --- | --- | | Initial register value (often all ones) | Leading zero bits now affect the result | Which error patterns are detected | | Final inversion of the remainder | An all-zero frame no longer yields an all-zero check field | Which error patterns are detected | | Bit reflection of input and output | The order bits enter the register and leave the field | The generator's degree and field width | | Byte order of the check field | How the `r` bits are laid into the frame | Anything algebraic | The first two are fixed offsets that cancel when you subtract two codewords, which is why the detection guarantees survive them untouched. All four break interoperability silently when two vendors read the specification differently, because the field looks perfectly well-formed and simply never matches. ## Cost in practice - The bit-at-a-time loop is one shift and a conditional XOR per bit of the frame — trivial in hardware, slow in software. - The usual software form precomputes a 256-entry table, one entry per possible byte value, and advances a byte per step, so the cost is linear in the frame's length and independent of the generator's degree. - Either way the work is proportional to the number of bits covered, which is why a link layer can afford to check every frame it ever sees.

Why does appending the remainder make the transmitted frame an exact multiple of the generator?
Because in GF(2) adding and subtracting are the same operation. The shifted message equals a multiple of the generator plus the remainder, so adding the remainder back is identical to subtracting it away. What goes on the wire is the shifted message with its remainder removed, which divides exactly.
Many specifications start the register at all ones and invert the final remainder. What do those two parameters change?
They stop degenerate frames slipping through: a non-zero initial register makes leading zero bits affect the result, and the final inversion stops an all-zero frame producing an all-zero check field. Neither changes which error patterns are detected, because both are fixed offsets that cancel when two codewords are subtracted.
If the check field is the remainder, what happens to the quotient?
It is discarded. Only the remainder carries the redundancy the receiver can test; the quotient is a by-product of the division and reconstructing it would tell the receiver nothing it does not already have. This is also why the field width is set by the generator's degree and not by the frame's length.

Like writing the leftover of a fixed division on a form: the clerk redoes the same division on what arrived and expects the same leftover, without ever needing your original working.

saying these in an interview costs you the question

Describes the check field as a sum of the frame's bytes
Assumes ordinary binary arithmetic with carries and borrows
Says the transmitted value is the quotient of the division
Thinks the field width grows with the frame's length
Believes the receiver needs the original frame to verify

In a cyclic redundancy check, what is divided by what, and in which arithmetic?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The one-sentence version

Bits as a polynomial

GF(2): arithmetic without carries

The division, step by step

Why the receiver's test works

Parameters that vary between specifications

Cost in practice

▾common follow-ups3 questions

▾analogy~10 s

▾red flags5 flags

The one-sentence version

Bits as a polynomial

GF(2): arithmetic without carries

The division, step by step

Why the receiver's test works

Parameters that vary between specifications

Cost in practice

answer

go deeper