CRC (cyclic redundancy checks)

Mathematics#

We discuss the arithmetic of the polynomial ring \(G\mathbb{F}(2)[X]\), which is over the field \(G\mathbb{F}(2)\). We let \(oplus\) denote the XOR operation.

• Addition: \(\sum_i a_i X^i + \sum_j b_j X^j = \sum_k a_k\oplus b_k X^k\).
• Subtraction: \(\sum_i a_i X^i - \sum_j b_j X^j = \sum_k a_k\oplus b_k X^k\).
• Multiplication: \(\sum_i a_i X^i \cdot \sum_j b_j X^j = \sum_k (\oplus_{l=0}^k a_l b_{k-l})X^k\) where \(a_l b_{k-l}\) is the ordinary multiplication of \(\mathbb{Z}_2\).

The addition and the subtraction are simple, as for the multiplication the point is simply to replace the summation in \(\sum^k_{l=0} a_l b_{k-l}\) with XOR, \(\oplus\).

A polynomial \(\sum_i^n a_i X^i \in G\mathbb{F}(2)[X]\) can be represented simply by the bit string \(a_n a_{n-1}\ldots a_1 a_0\). The addition and the subtraction then is represented by the XOR of two bit strings. The multiplication is the multiplication of the number represented by bit strings, without carrying:

\[\phantom{aaaaaa}a_n a_{n-1}\ldots\ \ldots a_0 \\ \phantom{aaaaaaaaaaaa\ }b_m\ldots b_0 \\ ----------\\(a_n b_0) (a_{n-1} b_0)\ldots(a_1 b_0)(a_0 b_0)\\ (a_n b_0) (a_{n-1} b_{1})(a_{n-2} b_1)\ldots(a_0 b_1)\phantom{aaaaaaaaaaa} \\ \ldots \\ ------------\\ (\sum_{k=0}^m a_{n-k}b_k)\ldots(a_1b_0+a_0 b_1)(a_0 b_0)\]

From this we get the algorithm for division with remainders. Suppose that we want to compute the remainder \(R(x)\) in \(R(x) = M(x) x^n\ \text{mod}\ G(x)\) and that \(G(x)\) is of degree \(n\) and is known. Put \(M(x) = \sum_i m_i x^i\). We have \(M(x) \cdot x^n = Q(x) G(x) + R(x)\) for some \(Q(x)\), so \(R(x) = M(x)\cdot x^n - Q(x)G(x)\). Now we need to determine \(Q(x)\). The \(k\)th coefficient of \(M(x)\cdot x^n\) should be equal to that of \(Q(x)G(x)\) for any \(k>n\) since \(R(x)\) is of degree at most \(n\), and \(G(x)\) is of degree \(n\), hence \(q_k = m_{i+n}\). Thus we have:

\[M(x)\cdot x^n - G(x) \sum m_{i+n} x^i =R(x).\]

It can be seen that \(R(x)\) can be computed from \(M(x)\) and \(G(x)\). Pad \(M(x)\) with \(n\) zeroes to get \(M(x)\cdot x^n\). Subtract \(G(x) x^i\) from \(M(x)\cdot x^n\) whenever \(m_{i+n}\) is nonzero.

CRC checksum#

Let \(G(x) \in G\mathbb{F}(2)[X]\) be degree \(n\) and call it the degree-\(n\) generator polynomial. The computation of CRC is the computation of the remainder polynomial \(R(x)\) of the original message polynomial \(M(x)\):

\[R(x) = M(x)\cdot x^n\ \text{mod}\ G(x).\]

The sender computes \(R(x)\), then attaches the bits of \(R(x)\) to \(M(x)\), which is equivalent to computing

\[W(x) = M(x) \cdot x^n +R(x) = M(x) \cdot x^n - R(x)\]

and sends it. The receiver divides \(W(x)\) by \(G(x)\) and checks that the remainder is zero. If it is, the last \(n\) bits of the bit string associated to \(W\) is discarded and assumes the received message bits \(M\) to be correct.