G22.2262
October 29, 1998

More on Data Link Layer Protocols

Note:  For IEEE 802.3 and old Ethernet,
G(x) is:
x32  +  x31  +  x18  +  x17  +  x16  +  x15  +  x 2 +  1
Note that the degree is 32, so you would add 32 0-bits to the packet (and the Ethernet checksum field is 32 bits)!

How good is CRC?

Let's find out! Let E(x) be a polynomial whose coefficients correspond ro bits that have been inverted.
For example, if bits 0, 5, abd 7 in the packet have been inverted, then:

E(x) = x7  +  x5  +  1

So, in our previous example:

we sent:                    1 1 0 1 0 1 1 0 1 1 1 1 1 0
the other side got:    1 1 0 1 0 1 0 0 0 1 1 1 1 1
|     |               |  bit 0 inverted
|     |
|     |                  bit 5 inverted
|
|                        bit 7 inverted

So, the bit pattern the receiver got was T(x) + E(x), in other words:

1 1 0 1 0 1 1 0 1 1 1 1 1 0  (that's T(x))
+  0 0 0 0 0 0 1 0 1 0 0 0 0 1  (that's E(x))
---------------------------
1 1 0 1 0 1 0 0 0 1 1 1 1 1  (that what the receiver got)

T(x) + E(x)
------------
G(x)

That's the same as:

T(x)     E(x)
----  +  ----
G(x)     G(x)

Now, we note that (T(x)/G(x)) has 0 as a remainder.  So, the only way the checksum on the packet that the receiver got will have 0 as a remainder is if (E(x)/G(x)) has no remainder!

In other words, only those error polynomials containing G(x) as a factor will slip by unnoticed!

In our example, because G(x) is  x4  +  x  +  1, G(x) will NEVER evenly divide an E(x) if E(x) has only one term! So, all single-bit errors will be caught!