Week 3 – Data Link Layer COMP90007 Internet Technologies
Lecturer: Semester 2, 2021
© University of Melbourne 2021
1
Error Detection Codes
Parity Bit (1 bit): (Hamming distance=2) Internet Checksum (16 bits): (Hamming
distance=2)
Cyclic Redundancy Check (CRC) (Standard 32-bit CRC: Hamming distance=4)
23
How it works?
Sender: calculates R check bits using a function of data bits:
Codeword
Receiver: receives the codeword and calculates the same function on the data and match the results with received check bits:
R=R’ ?
DATA
R=F(D)
DATA
R’
R=F(D)
24
Parity Bit
Given data 10001110, count the number of 1s Sender: Add parity bit 100011100 (for even parity)
100011101 (for odd parity) Receiver: Check the received data for errors.
Hamming distance is 2 for Parity Bit…
2 – 1 = 1 error bit can be detected and
(2 – 1) / 2 = 1⁄2 not even 1 bit error can be corrected
25
Internet Checksum
There are different variations of checksum Internet Checksum (16-bit word):
Sum modulo 216 and add any overflow of high order bits back into low-order bits
26
Example of Checksum
Calculate checksum (5-bit word) for data
00110 10001 11001 01011
1
00110
+10001 = 10111
The checksum is
one’s complement
of 11100 which is 00011
2 11001
+10111 = 10000 +1 = 10001
4
3
01011
+10001 = 11100
Data sent: 00110 10001 11001 01011 00011
27
Cyclic Redundancy Check
Based on a generator polynomial G(x)
e.g. G(x) = x4+x+1 (10011)
Steps:
LetrbethedegreeofG(x)(r=4).Appendrzerobitstothelow- order end of the frame so it now contains m + r bits and corresponds to the polynomial xrM(x).
DividethebitstringcorrespondingtoG(x)intothebitstring corresponding to xrM(x), using modulo 2 division.
Subtracttheremainder(whichisalwaysrorfewerbits)from the bit string corresponding to xrM(x) using modulo 2 subtraction.
Theresultisthechecksummedframetobetransmitted.Callits polynomial T(x).
28
Example
Data: 1101001 and G(x) = x4+x+1 (10011)
5 bits polynomial add 4 bits as the checksum – so add 0000
10011 11010010000 10011
010010 10011
000011000 10011
010110 10011
00101
Data sent: 11010010101
29
Error Correction: Hamming Code
n=2k-k-1 (n: number of data, k: check bits) Example: Data: 0101 – > requires 3 check bits
4 = (23) – 3 – 1
Put check bits in positions p that are power of 2, starting with position 1
Check bit in position p is parity of positions with a p term in their value
30
Example
Data: 0101 requires 3 check bits Position
Data
1. Calculate the parity bits for P1, P2, P4 (rule: even parity)
P1 + P3 + P5 + P7 = ?+0+1+1 (even) P1 = 0 P2+P3+P6+P7=?+0+0+1(odd) P2=1 P4 + P5 + P6 + P7 = ?+1+0+1 (even) P4 = 0
Put check bits in positions p that are power of 2, starting with position 1
111
P1
P2
P3
P4
P5
P6
P7
?
?
0
?
1
0
1
Data sent: 0100101
Example 1: At the receiver: 0100100
P1 + P3 + P5 + P7 = 0+0+1+0= 1× P2 + P3 + P6 + P7 = 1+0+0+0= 1× P4 + P5 + P6 + P7 = 0+1+0+0= 1×
error
error Example 2: At the receiver: 0000101
P1 + P3 + P5 + P7 = 0+0+1+1= 0 P2 + P3 + P6 + P7 = 0+0+0+1= 1 × P4 + P5 + P6 + P7 = 0+1+0+1= 0
Error bit: P1, P2, P4P(1+2+4)=P7
Error bit: P2
31
Error Control Discussion
Error Correction: More efficient in noisy transmission media e.g., wireless
Error Detection: More efficient in the transmission media where low error rates occur, e.g. quality copper
The error can occur in the check bits
Require assumption on a specific number of errors occurring in transmission
32