CRC - The Mathematics of Cyclic Redundance Checks

The idea of validating messages using cyclic redundancy checks (CRCs) goes back to an invention of W. Wesley Petersen in 1961¹⁾.
It is based on cyclic codes which themselves are based on polynomial ring arithmetic. Let's see what this is all about.

Mathematians define entities with operations on them and then study the general properties of the resulting structures. For example, they do this extensively with natural numbers in number theory where the existence of prime numbers and the representation of any number as a unique product of prime numbers is an important result that has applications e.g. in todays cryptography. Among the structures mathematians study are fields, groups and rings. Here we will look at rings.

Alternative Implementations

Rings are general structures of entities along with two operations called addition and multiplication that have to satisfy certain laws such as associativity of operation or the existence of inverse elements. A ring is called commutative if your can exchange the order of operands for the addition and still gain the same result.
Based on theses laws mathematicians deduce additional common properties. All rings dispite their elements share these common properties.

There are rings with infinite many members such as the ring of integers.

There are also rings with a finite number of members. If you take a number n you can consider all numbers that have the same remainder divided by n to be equivalent. This leads to quotient rings having the elements 0 to n-1. Addition and multiplication wrap around mod p.
If n is a prime number the rings have additional beneficial properties. They are fields and there is always a unique factorization of any ring member into prime factors. On important prime quotient ring is W₂ = { 0, 1 } that is suitable to represent single bits.

Computer scientists are interested in rings that have 2ⁿ (for some n, e.g. 16 or 32) elements as typical computer memory cells hold n bits.

Quotient rings based on polynomials indeed have 2ⁿ members and are thus good for giving memory cells a mathematical interpretion and making use of their mathematical properties. Again polynomial rings with “prime” polynomials, so called irreducible polynoms, have the unique factorization property.

So let's look at polynomials. We will concentrate on a special kind of polynomials that is well suited for our application area.

A polynomial is an entity with the following definition:

Assume we have a single symbol x a so called generator variable.
Assume we have a set of coefficients C which itself is a commutative ring with appropriate addition and multiplication. For our purpose assume that C is the quotient ring W₂ based on the prime 2 with the members 0 and 1.

A polynomial over W₂ with generator x has the form:

a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀

where a_i ∈ W₂ so can only be 0 or 1.

The degree of the polynomial is the exponent i of the largest xⁱ with a non zero coefficient a_i.

The set of polynomials over W₂ with generator x is infinite.

Note that different from high school the variable x never gets a value when we think of polynomials this way. We're not interested in evaluating polynomials but only in their properties as entities. We use them as self contained atomic elements, as values of their own for computation.

We can add and multiply polynomials and similar to integers we can think of division of polynomials.

As an example let's add (x² + 1) and (x²). With integer coefficients this would lead to 2x² + 1 but as our coefficients are from W₂ the calculation 1 + 1 equals 0 and so (x² + 1) + (x²) = 1.

We can multiply (x² + 1) by (x²) and get x⁴+x². And we can divide (x⁴+x²) by (x² + 1) giving x².

Similar to prime numbers some polynomials cannot be expressed as a product of two other polynomials. For example there are no proper factors for x² + x + 1. Such polymials are called irreducible. (Note that x²+1 is not irreducible over W₂ as (x+1) * (x+1) = x² + x + x + 1 = x² + 1 with coefficients from W₂).

If you divide polynomials you get - similar to the notion of remainders in integer division - polynomial remainders.

If we take an irreducible polynomial p and we look at the quotient ring R_p with respect to p then this ring has all the polynomial remainders of p as its members. If p is of degree n then R_p has 2ⁿ members. p is called the generator polynomial.

Every larger polynomial can be mapped into one of the polynomials in R_p by dividing it by p and determining its remainder.

The idea of a cyclic redundancy check is to consider the message to be checked as a huge polynomial over W₂ and divide it by the generator polynomial p. As the coefficients are from W₂ each bit of the message can represent one coefficient. The resulting remainder, the CRC value, (a polynomial represented as a sequence of degree(p) bits) is appended to the message. The receiver can re-calculate the remainder and compare it with the supplied one. If they differ, then the sent and the received message are not identical.

Implementations differ in the way they consider the message to be a large polynomial. They also differ in their generator polynomial.

As an example let's consider CRC-16-CCITT that uses the generator polynomial

x¹⁶ + x¹² + x⁵ + 1

Assuming the first coefficient is always 1 this polynomial can be represented as the combination of the 16 bits

(1) 0001 0000 0010 0001 = $1021
16  1  1 1 98 7654 3210
    5  2 1

Similar to paper and pencil division with numbers we divide by the generator polynomial by subtraction according to place. As the coefficients are from W₂ adding and subtracting can be implemented by the bit-wise-xor-operation.

The bits of the message are inspected one after the other and if possible the generator polynomial is subtracted at the inspected position.

At the end of this procedure we gain the remainder of the division by the generator polynomial encoded as a 16-bit-number.

DISCUSS THE CONCRETE ALGORITHM AND THE EXAMPLE CALCULATION

uh 2022-05-16