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:

• A packet contains a bit string
• We represent the bit string as a polynomial with coefficients of 0 and 1 only.
• A k-bit packet is represented as a polynomial with k terms. It is said to be of degree (k - 1).

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

•  Polynomial arithmetic is done modulo-2; there are no carries for addition and no borrow for subtraction. So, both addition and subtraction are identical to "exclusive-or".

Examples:

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

• Both sender and receiver agree on a "generator polynomial" (let's call it G(x)). Both high-order and low-order bits of G(x) must be 1.

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.

• Here's how the checksum works:
• Let's say the packet has m bits.
• Let r be the degree of G(X).
• Append r 0-bits to the low-order end of the packet, so the packet contains (m + r) bits. Note: if the polynomial associated with the frame was M(X), it is now (xr * M(x))
• Divide the bit string corresponding to G(X) into the bit string corresponding to (xr * M(X)), using modulo-2 division.
• Subtract the remainder from the bit string corresponding to (xr * M(X)), using Modulo-2 subtraction.
• The result is the check-summed packet to send!

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).

• Because in any division, if you diminish the dividend by the remainder, the amount left is divisible by the divisor!

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)

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!