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)
 

The receiver computes:

                        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!