Computer Networking Cyclic Redundancy Check CRC Modulo 2 Arithmetic, Polynomial Division

Modulo 2 Arithmetic:

Here, $ T $ is a frame with $ n $ bits of data to be transmitted. $ D $ is the first $ k $ bits of data which we want to transmit. $ R $ is rest of the $ n - k $ bits used for CRC error checking. Here $ r = |R| $, the length of CRC $ R $ bits. The goal is to have no remainder for $ \frac{T}{G} $. $ R $ must be calculated beforehand. Also, $ d = |D| $, the length of the data bits. So if we know our data bits $ D $ and divisor $ G $, then $ R $ can be calculated in such a way that there is no remainder.

$ |T| = |D| + |R| = d + r $ bits. To satisfy the above criterion, $ \frac{D*2^r \oplus R}{G} = n $ must be true.

$ T = D * 2^r + R \\ $
$ T = D * 2^r \oplus R \\ $
$ nG = D * 2^r \oplus R \\ $
$ R = D * 2^r \text{ mod } G \\ $

Division:

If, $ D = 111011 $ and $ G = 1011 $. Then, $ r = |G| - 1 = 3 $.

Step 1:

Left shift $ D \ll r $ or, $ D*2^r = 111011000 $

Step 2:

$ \require{enclose} \begin{array}{rll} n \\[-3pt] G \enclose{longdiv}{D*2^r}\kern-.2ex \\[-3pt] \underline{......}\\[-3pt] R\phantom{0}\\[-3pt] \end{array} $
Now divide using the values. The goal is to find $ R $ in such a way that $ D*2^r \oplus R = nG $.

$ \require{enclose} \begin{array}{rll} 110001 \\[-3pt] 1011 \enclose{longdiv}{111011000}\kern-.2ex \\[-3pt] \underline{1011\phantom{00000}}\\[-3pt] 1011\phantom{0000}\\[-3pt] \underline{1011\phantom{0000}}\\[-3pt] \phantom{0000}1000 &&\\[-3pt] \underline{1011}\\[-3pt] \phantom{0}011 &&\\[-3pt] \end{array} $

So, here $ R = 011 $, since remainder must be $ 3 $ bits, $ r = |R| $. Here, $ n = 110001$. Now, testing to see if the above division is correct.

Galois calculator result for, $ n * G = 110001 * 1011 = 111011011 $.

Now calculating $ D * 2^r \oplus R $,
$ 111011000 \oplus 011 = 111011011 $.
So, $ D*2^r \oplus R = nG $.

Polynomial Long Division:

Similarly using the above as an example the polynomial division can be performed. In order to calculate polynomial representation, where ever there is a $ 1 $ set $ X $ and set its power just like binary representation. Here, $ X $ is a dummy base.

Note $ G(X) $ could also be written as $ P(X) $. Formula for calculation is,
$ R(X) = \frac{X^r * D(X)}{G(X)} $

$1011 = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 1*2^3 + 1*2^1 + 1*2^0 = 8 + 2 + 1 = 11 $.

Here, $ D = 111011 $. In polynomial representation it is,
$ D(X) = X^5 + X^4 + X^3 + X^1 + X^0 = X^5 + X^4 + X^3 + X + 1 $.

Similarly, $ G = 1011 $ in polynomial is, $ G(X) = X^3 + X + 1 $. Also, $ R = 011 $ which is, $ R(X) = X + 1 $. The quotient, $ n \text{ or, } Q(X) = X^5 + X^4 + 1 $

Now, $ X^r * D(X) = X^3*(X^5 + X^4 + X^3 + X + 1) = X^8 + X^7 + X^6 + X^4 + X^3 $.

Now the task remains is to check if the remainder actually matches with the modulo 2 arithmetic, otherwise something is wrong. Note below I did not maintain formatting due to writing quickly.

$ \require{enclose} \begin{array}{rll} X^5 + X^4 + 1 \\[-3pt] X^3 + X + 1 \enclose{longdiv}{X^8 + X^7 + X^6 + X^4 + X^3}\kern-.2ex \\[-3pt] \underline{X^8 + X^6 + X^5\phantom{0000000000}}\\[-3pt] X^7 + X^5 + X^4 + X^3\\[-3pt] \underline{X^7 + X^5 + X^4\phantom{00000}}\\[-3pt] \phantom{0000}X^3 &&\\[-3pt] \underline{X^3 + X + 1}\\[-3pt] \phantom{0}X + 1 &&\\[-3pt] \end{array} $

Looking above all the values, $ Q(X) = X^5 + X^4 + 1, G(X) = X^3 + X + 1, R(X) = X + 1 $ are exactly as conversion from modulo 2 arithmetic.