Let's look at Datalink layer functionality.
The most common errordetecting 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 x^{0}, the next as x^{1},
the next as x^{2},
and so on. So, represent that as a polynomial:
1*x^{9} + 1*x^{8} + 0*x^{7}
+ 1*x^{6} + 0*x^{5} + 1*x^{4} + 1*x^{3} + 0*x^{2}
+ 1*x^{1} + 1*x^{0}
And that comes out to be:
x^{9} + x^{8} + x^{6}
+ x^{4} + x^{3} + x^{1} + 1
Examples:
10011011 11110000
+
11001010  10100110
 
01010001 01010110
Example:
G(x)
= x^{4} + x + 1
That has 5 terms: 1 0 0 1 1
==> 1*x^{4} + 0*x^{3} + 0*x^{2} + 1*x^{1} + 1*x^{0}
The degree is 4.
Example:
Packet: 1 1 0 1 0 1 1 0 1 1
G(X) = x^{4} + 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 (x^{r} * 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:
x^{32} + x^{31} + x^{18} + x^{17} + x^{16} + x^{15} + x ^{2} + 1
Note that the degree is 32, so you would add 32
0bits 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) = x^{7} + x^{5} + 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 x^{4} + x + 1, G(x) will NEVER evenly divide an E(x) if E(x) has only one term! So, all singlebit errors will be caught!