Computer Communication Networks

CS-327

Course Teacher : Sumayya Zafar

Class : TE-CIS

Data Link Layer – Error Detection and –

Correction Techniques

Fall Semester 2023 1

 Types of Errors
• In digital transmission systems, an error occurs when a bit is
altered between transmission and reception; that is, a binary 1
is transmitted and a binary 0 is received, or a binary 0 is
transmitted and a binary 1 is received.
• Two general types of errors can occur:
• Single bit errors - A single bit error is an isolated error condition that
alters one bit but does not affect nearby bits.
• Burst errors - A burst error of length B is a contiguous sequence of B
bits in which the first and last bits and any number of intermediate bits
are received in error.

Fall Semester 2023 2

 Types of Errors
0 changed to 1

00000010 00001010
Sent Single Bit Error Received

Length of Burst = 8 bits

Sent 0100010001000011
Corrupted Bits

Received 0101110101100011
Burst Error
Fall Semester 2023 3
 Types of Errors
• Single bit errors are the least likely type of error in serial data
transmission.
• A burst error does not necessarily mean that the errors occur in
consecutive bits.
• The length of the burst is measured from the first corrupted bit to the last
corrupted bit. Some bits in between may not have been corrupted.
• A burst error is more likely to occur than a single bit error. The duration of
noise is normally longer than the duration of 1 bit, which means that
when noise affects data, it affects a set of bits.
• The number of bits affected depends on the data rate and duration of
noise.
• Example: when a wireless transmitter transmits at 11 Mbps and an
interference burst of 200 μs occurs, 2200 bits are affected by the burst.

Fall Semester 2023 4

 Detection Vs Correction
• In error detection, we are looking only to see if any error has
occurred. The answer is a simple yes or no. We are not
interested in the number of errors. A single bit error is the same
for us as a burst error.
• In error correction, we need to know the exact number of bits
that are corrupted and more importantly, their location in the
message. The number of the errors and the size of the message
are important factors.

Fall Semester 2023 5

 Redundancy
• The central concept in detecting or correcting errors is
redundancy.
• To be able to detect or correct errors, we need to send some
extra(redundant) bits with our data.
• These redundant bits are added by the sender and removed by
the receiver.
• Their presence allows the receiver to detect or correct
corrupted bits.

Fall Semester 2023 6

 Coding
• Redundancy is achieved through various coding schemes.
• The sender adds redundant bits through a process that creates
a relationship between the redundant bits and the actual data
bits.
• The receiver checks the relationships between the two sets of
bits to detect or correct the errors.
• The ratio of redundant bits to the data bits is important factor
in any coding scheme.

Fall Semester 2023 7

 Forward Error Correction Vs Retransmission

• Two main methods of error correction are:

• Forward error correction(FEC) is the process in which
the receiver tries to guess the message by using
redundant bits.
• Correction by retransmission is a technique in which
the receiver detects the occurrence of an error and
asks the sender to resend the message. Resending is
repeated until a message arrives that the receiver
believes is error free.
Fall Semester 2023
8
 How it is done?
• At the sending node, data, D, to be
protected against bit errors is
augmented with error detection
and correction bits (EDC).
• EDC is the function of transmitted
bits.
• Typically, for a data block of 𝑘𝑘 bits,
the error detecting algorithm yields
an error detecting code of 𝑛𝑛 − 𝑘𝑘
bits, where (𝑛𝑛 − 𝑘𝑘) < 𝑘𝑘.
• The error detecting code, also
referred to as the check bits, is
appended to the data block to
produce a frame of 𝑛𝑛 bits, which is
then transmitted.
Fall Semester 2023 9
 How it is done?
• Both 𝐷𝐷(𝑘𝑘 bits) and 𝐸𝐸𝐸𝐸𝐸𝐸(𝑛𝑛 − 𝑘𝑘
bits) are sent to the receiving
node in a link level frame.
• At the receiving node, a
sequence of bits, 𝐷𝐷́ ( 𝑘𝑘́ bits)
́
and 𝐸𝐸𝐸𝐸𝐸𝐸 ( (𝑛𝑛 −́ 𝑘𝑘) bits)is
received.
́ may differ from
• 𝐷𝐷́ and 𝐸𝐸𝐸𝐸𝐸𝐸
the original 𝐷𝐷 and 𝐸𝐸𝐸𝐸𝐸𝐸 as a
result of in transit bit flips.
Fall Semester 2023 10
 How it is done?
• The receiver performs the
same error detecting
calculation on the data bits
and compares this value with
the value of the incoming
error detecting code.
• A detected error occurs if and
only if there is a mismatch.

Fall Semester 2023 11

 Error Detection Techniques
• Three techniques for detecting errors in the transmitted data
are:
• Parity checks
• Checksum methods
• Cyclic redundancy checks (CRC)

Fall Semester 2023

12
 Parity Checks
• The simplest error detecting scheme is to append a single
parity bit to the end of a block of data.
• In an even parity scheme, the sender simply includes one
additional bit and chooses its value such that the total number
of 1s in the 𝑑𝑑 + 1 bits (the original information plus a parity
bit) is even.
• For odd parity schemes, the parity bit value is chosen such that
there is an odd number of 1s.

Fall Semester 2023

13
 Parity Checks
‘d’ data bits parity bit(even parity scheme)

0111000110101011 1

‘d +1’ bits

• Receiver operation is also simple with a single parity bit.

• The receiver need only count the number of 1s in the received 𝑑𝑑 +
1 bits.
• If an odd number of 1 valued bits are found with an even parity
scheme, the receiver knows that at least one bit error has occurred.
More precisely, it knows that some odd number of bit errors have
occurred.
• But when even no. of bits error occurred, it is undetectable.
Fall Semester 2023
14
 Properties of Parity Checks
• Properties of parity check codes are:
• All odd numbers of bit errors are detected.
• All even numbers of bit errors are not detected.
• Parity check codes have traditionally been used on serial
interfaces, e.g. RS-232, where a parity bit has been appended
to each byte.

Fall Semester 2023

15
 Two Dimensional Parity Checks
• The 𝑑𝑑 bits in 𝐷𝐷 are divided into 𝑖𝑖 rows and 𝑗𝑗 columns.
• A parity value is computed for each row and for each column.
• The resulting 𝑖𝑖 + 𝑗𝑗 + 1 parity bits comprise the link layer
frame’s error detection bits.

Fall Semester 2023

16
 Two Dimensional Parity Checks
1100111 1011101 0111001 0101001 Original data

1100111 1 Sender Side

1011101 1 Even Parity scheme used
0111001 0
0101001 1
0101010 1

Transmitted Frame
11001111 1011101 1 0111001 0 01010011 0101010 1

Fall Semester 2023

17
 Two Dimensional Parity Checks
Receiver Side

1100111 1
1111101 1 Parity Error
0111001 0 *Bit in position (2,2) is switched to 1
0101001 1 *A single error in the parity bits is also
0101010 1 detectable and correctable.
Parity Error

Fall Semester 2023

18
 Two Dimensional Parity Checks
Receiver Side

1100111 1
*Bit in position (2,2) is switched to 1 and bit
1111001 1 in position (2,5)is switched to 0
0111001 0
*Two-dimensional parity can also detect
0101001 1 (but not correct!) any combination of two
1 errors in a packet.
0101010
Parity Error Parity Error

Fall Semester 2023

19
 Checksum Methods
• On the sender side: The checksum generator sub divides
the data unit into equal segments of ‘n’ bits(usually 16).
• These segments are added using 1’s complement
arithmetic in such a way that total is also ‘n’ bits.
• The total or sum is then complemented and appended to
the end of the data as redundancy bits.
• These redundancy bits are called checksum field.
• The extended data unit is transmitted across the network.

Fall Semester 2023 20

 Checksum Methods
• The receiver sub divides the data unit adds all the
segments and complements the results.
• If the encoded data is intact, the total values found by
adding the data segments and the checksum field should
be zero.
• If the result is not zero , the packet contains error and
receiver rejects it.
• The Internet checksum is based on this approach.

Fall Semester 2023 21

 Checksum Methods

10101001 00111001 Original data

Length of checksum = 8 bits

Sender Side:
10101001

Binary addition 00111001 Checksum

1’s complement
11100010 00011101

Encoded Word 10101001 00111001 00011101

Fall Semester 2023 22
 Checksum Methods
Received Word 10101001 00111001 00011101

Receiver Side:
10101001
00111001 Result is zero so the data is
00011101 intact and no error
1’s complement
11111111 00000000

Fall Semester 2023 23

 Checksum Methods
Now let us introduce error in first bit

Receiver Side:
00101001
00111001 Result is non zero so the data
00011101 has error and it is discarded
1’s complement
01111111 10000000

Fall Semester 2023 24

 Checksum Method - Properties
• It detects all errors involving an odd number of bits as well as most errors
involving an even number of bits.
• If one or more bits of a segment are damaged & the corresponding bit or bits
of opposite value in a second segment are also damaged , the sum of those
columns will not change and the receiver will not detect error.
Transmitted Word 10101001 00111001 00011101
Received Word 00101001 10111001 00011101

Receiver Side: 00101001

Result is zero no error is
10111001 detected though error was
00011101 present
1’s complement
11111111 00000000
Fall Semester 2023 25
 Cyclic Redundancy Check
• Most powerful and widely used error detection technique and it is based on binary
division.
• CRC codes are known as polynomials.
• Consider the 𝑑𝑑 bit piece of data, 𝐷𝐷 , that the sending node wants to send to the
receiving node.
• The sender and receiver must first agree on an 𝑟𝑟 + 1 bit pattern, known as a
generator, which we will denote as 𝐺𝐺.
• For a given piece of data, 𝐷𝐷, the sender will choose 𝑟𝑟 additional bits(also known as
frame check sequence), 𝑅𝑅, and append them to 𝐷𝐷 such that the resulting 𝑑𝑑 + 𝑟𝑟 bit
pattern is exactly divisible by 𝐺𝐺 (i.e., has no remainder) using modulo 2 arithmetic.
• All CRC calculations are done in modulo 2 arithmetic without carries in addition or
borrows in subtraction. This means that addition and subtraction are identical, and
both are equivalent to the bitwise exclusive or (XOR) of the operands.
Fall Semester 2023 26
 Cyclic Redundancy Check
• The process of error checking with CRCs is thus simple: The receiver divides
the 𝑑𝑑 + 𝑟𝑟 received bits by 𝐺𝐺.
• If the remainder is nonzero, the receiver knows that an error has occurred;
otherwise the data is accepted as being correct.
‘d’ bits ‘r’ bits

‘D’ data bits ‘R’ FCS

‘d+r’ bits

• Mathematical formula: 𝐷𝐷. 2𝑟𝑟 XOR R

Left Shift ‘D’ by ‘r’ bits to yield ‘d+r’ bits

• In order to calculate 𝑅𝑅 , we divide 𝐷𝐷. 2𝑟𝑟 by 𝐺𝐺

Fall Semester 2023 27
 Cyclic Redundancy Check
• Given:
Message ‘D’ = 1010001101 (10 Bits) = ‘d’ bits
Generator ‘G’ = 110101 (6 Bits)
Degree of G = 1. 𝑋𝑋 5 + 1. 𝑋𝑋 4 + 0. 𝑋𝑋 3 + 1. 𝑋𝑋 2 + 0. 𝑋𝑋 1 + 1. 𝑋𝑋 0 = 5 = ‘r’ bits
FCS to be calculated? = ‘R’ = ?
‘d + r’ = 10 + 5 = 15 bits
The message is multiplied 25 by yielding 101000110100000
‘10’ bits ‘r’ bits

1010001101 ‘?’ FCS

‘15’ bits

Fall Semester 2023 28

 Cyclic Redundancy Check
𝑄𝑄
𝐺𝐺 25 𝐷𝐷

‘10’ bits ‘r’ bits

1010001101 ‘?’ FCS

‘15’ bits

Fall Semester 2023 29

𝑅𝑅
 Cyclic Redundancy Check
• The remainder is added to 25 𝐷𝐷 to give 𝑇𝑇 = 101000110101110
which is transmitted.

‘10’ bits ‘r’ bits

1010001101 01110

‘15’ bits

• If there are no errors, the receiver receives 𝑇𝑇 intact. The received

frame is divided by 𝐺𝐺.

Fall Semester 2023 30

 Cyclic Redundancy Check
𝑄𝑄

𝑇𝑇
𝐺𝐺

Because there is no
remainder, it is
assumed that there
have been no errors.

Fall Semester 2023 31

𝑅𝑅
 CRC – Some Standard Polynomials
• A second way of viewing the CRC process is to express all values as
polynomials in a dummy variable 𝑋𝑋, with binary coefficients. The coefficients
correspond to the bits in the binary number.
• Thus for D = 110011 we have D 𝑋𝑋 = 𝑋𝑋 5 + 𝑋𝑋 4 + 𝑋𝑋 + 1, and for G= 11001 we
G 𝑋𝑋 = 𝑋𝑋 4 + 𝑋𝑋 3 + 1
• Arithmetic operations are again modulo 2.
• International standards have been defined for 8-, 12-, 16-, and 32-bit
generators, G.
• The CRC-32 32 bit standard, which has been adopted in a number of link level
IEEE protocols, uses a generator of:
𝐶𝐶𝐶𝐶𝐶𝐶 − 32
= 𝑋𝑋 32 + 𝑋𝑋 26 + 𝑋𝑋 23 + 𝑋𝑋 22 + 𝑋𝑋16 + 𝑋𝑋12 + 𝑋𝑋11 + 𝑋𝑋10 + 𝑋𝑋 8 + 𝑋𝑋 7 + 𝑋𝑋 5
+ 𝑋𝑋 42023+ 𝑋𝑋 2 + 𝑋𝑋 + 1
Fall Semester 32
 Cyclic Redundancy Check - Properties
• Errors are not detected when their bit pattern (taken as a
polynomial) is evenly divisible by 𝐺𝐺(𝑋𝑋)
• All single bit errors, if 𝐺𝐺(𝑋𝑋) has more than one nonzero term.
• Any odd number of errors, as long as 𝐺𝐺(𝑋𝑋) contains a factor (𝑋𝑋 +
1)
• Any burst error for which the length of the burst is less than or
equal to ‘𝑟𝑟𝑟 that is, less than or equal to the length of the FCS.

Fall Semester 2023 33

 Questions?

Fall Semester 2023 34