The bits of data that are the message to be checked by the CRC can
be represented by a polynomial
of degree
. As an example
the one octet message
is represented by the polynomial
. In general, leading zero bits do not affect
whereas
trailing zero bits each add a factor of
. The generating polynomial
is chosen by very clever mathematicians and is essentially fixed.
The polynomial
is used to represent 32 successive ones.
The CRC is defined as the ones complement of a remainder
obtained from the modulo two division of
by the
generating polynomial
. I.e. the CRC is
.
The multiplication by corresponds to leaving space at the end
of the message for the generated CRC. The addition of
(which
is equivalent to inverting the first 32 bits of the message) precludes
erroneous addition or deletion of leading zeros. The inversion of the
CRC before sending it precludes erroneous addition of trailing zeros.
As described:
for some quotient and remainder
. The CRC is the complement.
The transmitted message denoted is
followed by the CRC.
At the receiver the operation is again repeated. This time however the
value used is rather than
also the message is 32 bits
longer so
is replaced by
. We consider:
Factoring out we get:
Substituting (3) and thence (2) gives:
Taking the divisor inside we can now substitute (1).
From which the terms cancel in our modulo two arithmetic. We
are, or course, only interested in the remainder of the division which
is therefore.
Which is a known constant value (called the residual or residue) for all messages
.