Let's look at Data-link layer functionality.

The most common error-detecting method:

The Polynomial Code

or Cyclic Redundancy Code (CRC)

Here's how it works:

Example:

1 1 0 1 0 1 1 0 1 1

Because there are 10 bits, represent it as a polynomial of degree 9.
The rightmost bit is associated with x0, the next as x1, the next as x2,
and so on. So, represent that as a polynomial:

     1*x9 + 1*x8 + 0*x7 + 1*x6 + 0*x5 + 1*x4 + 1*x3 + 0*x2 + 1*x1 + 1*x0

And that comes out to be:

x9 + x8 + x6 + x4 + x3 + x1 + 1

Examples:

  10011011           11110000
+ 11001010         - 10100110
  --------          ---------
  01010001           01010110
 

Example:           
                 G(x) = x4 + x + 1

That has 5 terms:     1 0 0 1 1 

==>        1*x4 + 0*x3 + 0*x2 + 1*x1 + 1*x0

The degree is 4.
 

Example:

Packet:       1 1 0 1 0 1 1 0 1 1   

G(X) = x4 + x + 1

So, Generator is: 1 0 0 1 1

Modified packet: 1 1 0 1 0 1 1 0 1 1 0 0 0 0 (the original packet plus 4 0's)

Now do the division:
 
            1 1 0 0 0 0 1 0 1 0
           _____________________________
1 0 0 1 1 ) 1 1 0 1 0 1 1 0 1 1 0 0 0 0
            1 0 0 1 1
            ---------
            0 1 0 0 1 1
              1 0 0 1 1
              ---------
              0 0 0 0 0 1
                0 0 0 0 0
                ---------
                0 0 0 0 1 0
                  0 0 0 0 0
                  ---------
                   0 0 0 1 0 1
                     0 0 0 0 0
                     ---------
                     0 0 1 0 1 1
                       0 0 0 0 0
                       ---------
                       0 1 0 1 1 0
                         1 0 0 1 1
                         ---------
                         0 0 1 0 1 0
                           0 0 0 0 0
                           ---------
                           0 1 0 1 0 0
                             1 0 0 1 1
                             ---------
                           0 0 1 1 1 0 <- This is the remainder!

So, subtract the remainder from the (xr * M(X)):

            1 1 0 1 0 1 1 0 1 1 0 0 0 0
          -                     1 1 1 0
            ---------------------------
            1 1 0 1 0 1 1 0 1 1 1 1 1 0

And that's what you transmit! So you send "1 1 0 1 0 1 1 0 1 1 1 1 1 0" to the peer. Note that we send the original packet with 4 extra bits. The 4 extra bits is the checksum!

Now, let's call the thing we transmit "T(x)".

T(x) is evenly divisible by G(x).

So, when the receiver gets the bits, they divide it by G(x) (i.e., 10011), and the result should have no remainder! If the result has no remainder, the receiver says the packet passed the checksum! The receiver chops off the last 4 bits and send the packet up to the next layer.

 

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 to bits that have been inverted.
For example, if bits 0, 5, and 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!