Chapter 3 Error Detection and Correction

Error Detection
and Correction
10 Error Detection and Correction
1 Types of Errors
2 Detection
3 Error Correction
Error Detection and Correction
 Data can be corrupted during transmission. For reliable
communication, error must be detected and corrected
 Error Detection and Correction are implemented either

at the data link layer or the transport layer of the OSI
model
1 Type of Errors
Type of Errors(cont’d)
 Single-Bit Error
~ is when only one bit in the data unit has changed
(ex : ASCII STX - ASCII LF)

 Multiple-Bit Error
~ is when two or more nonconsecutive bits in the data

unit have changed(ex : ASCII B - ASCII LF)
 Burst Error
~ means that 2 or more consecutive bits in the data unit

have changed
Detection
 Error detection uses the concept of redundancy, which
means adding extra bits for detecting errors at the
destination
Detection(cont’d)
 Redundancy: sending some extra bits in order to detect or correct
Errors.
Detection(cont’d)
 Detection methods
Detection(cont’d)
 Parity Check
 A parity bit is added to every data unit so that the total

number of 1s(including the parity bit) becomes even for
even-parity check or odd for odd-parity check
 Simple parity check

Detection -examples
Example 1
Suppose the sender wants to send the word world. In
ASCII the five characters are coded as
1110111 1101111 1110010 1101100 1100100
The following shows the actual bits sent
11101110 11011110 11100100 11011000 11001001
Detection – examples
Example 2
Now suppose the word world in Example 1 is received by the
receiver without being corrupted in transmission.
11101110 11011110 11100100 11011000 11001001
The receiver counts the 1s in each character and comes up
with even numbers (6, 6, 4, 4, 4). The data are accepted.
Detection – examples
Example 3
Now suppose the word world in Example 1 is corrupted
during transmission.
11111110 11011110 11101100 11011000
11001001
The receiver counts the 1s in each character and comes up
with even and odd numbers (7, 6, 5, 4, 4). The receiver
knows that the data are corrupted, discards them, and asks
for retransmission.
Two –Dimensional Parity Check
Detection - example
Example 4
Suppose the following block is sent:
10101001 00111001 11011101 11100111 10101010
However, it is hit by a burst noise of length 8, and some bits

are corrupted.
10100011 10001001 11011101 11100111 10101010
When the receiver checks the parity bits, some of the bits do
not follow the even-parity rule and the whole block is
discarded.
VRC and LRC
Four types of redundancy checks are used
in data communications
VERTICAL REDUNDANCY CHECK
VRC
Performance of VRC
It can detect single bit error
It can detect burst errors only if the total number of

errors is odd.
Unreliable error-detection method, because it only

works if an even number of bits is distorted.
Longitudinal Redundancy Check
LRC
•Longitudinal redundancy check (LRC) also
known as horizontal redundancy check,
•It is a form of redundancy check that is applied
independently to each of a parallel group of bit
streams.
•The data must be divided into transmission
blocks, to which the additional check data is
added.
Longitudinal Redundancy Check
LRC
EXAMPLE
Performance of LRC
LRC increases the likelihood of detecting burst
errors.
If two bits in one data units are damaged and two bits
in exactly the same positions in another data unit are
also damaged, the LRC checker will not detect an
error.
CRC
 The CRC is a network method designed to detect errors in the
data and information transmitted over the network.
 CRC is performed by a binary solution on the transmitted data

at the sender’s side and verifying the same at the receiver’s side.
 The term CRC is used to describe this method because Check

represents the “data verification,” Redundancy refers to the
“recheck method,” and Cyclic points to the “algorithmic
formula.”
 To understand the working of the CRC method, we will divide the

steps into two parts:
Sender Side (CRC Generator and Modulo Division):
 The first step is to add the no. of zeroes to the data to be sent,
calculated using k-1 (k - is the bits obtained through the
polynomial equation(Ex. X3+X2+X+1)
 Applying the Modulo Binary Division to the data bit by applying

the XOR and obtaining the remainder from the division
 The last step is to append the remainder (r2r1r0) to the end of

the data bit and share it with the receiver. The quotient of the
division is discarded.
 Example - The data bit to be sent is [100100], and the

polynomial equation is [x3+x2+1].
Receiver Side (Checking for errors in the received data):
 To check the error, perform the Modulo division again and check
whether the remainder is 0 or not,
 If the remainder is 0, the data bit received is correct, without any

errors.
 If the remainder is not 0, the data received is corrupted during

transmission.
 Example - The data bit to be received is [100100001], and the

polynomial equation is [x3+x2+1].
Detection(cont’d)
 CRC(Cyclic Redundancy Check)
~ is based on binary division.

Detection (Sender Side)
 CRC generator
~ uses modular-2 division.
Binary Division
in a
CRC Generator
CRC Decoder (Reciver Side)
Binary Division
in a
CRC Checker
Home Work
 Message:1 1 0 1 0 1 1 0 1 1
 Devisor: 1 0 0 1 1
 Remainder:1 1 1 0
 Transmitted msg:
1101011011 1110
Checksum
 Checksum
~ used by the higher layer protocols
~ is based on the concept of redundancy(VRC, LRC, CRC)

Explain the process of Checksum with example.
 Checksum is an error detection method.
 Step-01:
At sender side, If m bit checksum is used, the data unit to be

transmitted is divided into segments of m bits.
All the m bit segments are added.
The result of the sum is then complemented using 1‟s complement

arithmetic.
The value so obtained is called as checksum.
 Step-02:
The data along with the checksum value is transmitted to the receiver.
 Step-03:
All the m bit segments are added along with the checksum value. The
value so obtained is complemented and the result is checked.
 Case-01: Result = 0 (If the result is zero)
 Receiver assumes that no error occurred in the data during the

transmission.
Receiver accepts the data.
 Case-02: Result ≠ 0 (If the result is non-zero)
 Receiver assumes that error occurred in the data during the transmission.
 Receiver discards the data and asks the sender for retransmission.
Checksum-Example
 At the sender
Original data : 10101001 00111001
10101001
00111001
--------------
11100010 Sum
00011101 Checksum
10101001 00111001 00011101

Detection(cont’d)
 Example ( at a receiver)
Received data : 10101001 00111001 00011101
10101001
00111001
00011101
---------------
11111111  Sum
00000000  Complement
Performance
The checksum detects all errors involving an odd
number of bits.
It detects most errors involving an even number of bits.
If one or more bits of a segment are damaged and the

corresponding bit or bits of opposite value in a second
segment are also damaged, the sums of those columns
will not change and the receiver will not detect a
problem.
Checksum Example
 Consider the data unit to be transmitted is-
10011001111000100010010010000100 Consider 8 bit checksum is
used.
 Step-01:
At sender side,
The given data unit is divided into segments of 8 bits as-
 Now, all the segments are added and the result is obtained as-
10011001 + 11100010 + 00100100 + 10000100 = 1000100011
Since the result consists of 10 bits, so extra 2 bits are wrapped around.
00100011 + 10 = 00100101 (8 bits)
Now, 1‟s complement is taken which is 11011010.

 Step-02:
The data along with the checksum value is transmitted to the receiver.
 Step-03:
At receiver side, The received data unit is divided into segments of 8
bits.
All the segments along with the checksum value are added.
Sum of all segments + Checksum value =
 00100101 + 11011010= 11111111
Complemented value = 00000000
Since the result is 0, receiver assumes no error occurred in the data

and therefore accepts it.
4.3 Error Correction
~ can be handled in two ways
when an error is discovered, the receiver can have the

sender retransmit the entire data unit.
Automatic Repeat Request (ARQ)
 a receiver can use an error-correcting code, which

automatically corrects certain errors.
Hamming Code
Automatic Repeat Request (ARQ)
 In the ARQ system of error correction, when an error
occurs, the receiver makes the request for
retransmission.
 A feedback channel is required for this system.

Error Correction(cont’d)
 Redundancy Bits
~ to calculate the number of redundancy bits (R) required

to correct a given number of data bit (M)
 Hamming Code
~ developed by R.W.Hamming
 positions of redundancy bits in Hamming code
 The redundant bits are inserted at each 2n bit where

n=0,1,2,3,……
 each r bit is the VRC bit for one combination of data
bits
r1 = bits 1, 3, 5, 7, 9, 11
r2 = bits 2, 3, 6, 7, 10, 11
r4 = bits 4, 5, 6, 7
r8 = bits 8, 9, 10, 11
 Redundancy bits
calculation(cont’d)
 Redundancy bits calculation
 Calculating the r values (Sender Side)
Calculating Even Parity

 Error Detection and Correction
 Error detection using Hamming Code (Receiver Side)

Chapter 3 Error Detection and Correction

Uploaded by

Copyright:

Available Formats

Chapter 3 Error Detection and Correction

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 3 Error Detection and Correction

Uploaded by

Copyright:

Available Formats

Error Detection

 Error Detection and Correction are implemented either

~ is when only one bit in the data unit has changed

(ex : ASCII STX - ASCII LF)

~ is when two or more nonconsecutive bits in the data

~ means that 2 or more consecutive bits in the data unit

 A parity bit is added to every data unit so that the total

 Simple parity check

However, it is hit by a burst noise of length 8, and some bits

It can detect burst errors only if the total number of

Unreliable error-detection method, because it only

 CRC is performed by a binary solution on the transmitted data

 The term CRC is used to describe this method because Check

 To understand the working of the CRC method, we will divide the

 Applying the Modulo Binary Division to the data bit by applying

 The last step is to append the remainder (r2r1r0) to the end of

 Example - The data bit to be sent is [100100], and the

 If the remainder is 0, the data bit received is correct, without any

 If the remainder is not 0, the data received is corrupted during

 Example - The data bit to be received is [100100001], and the

~ is based on binary division.

~ used by the higher layer protocols

~ is based on the concept of redundancy(VRC, LRC, CRC)

At sender side, If m bit checksum is used, the data unit to be

All the m bit segments are added.

The result of the sum is then complemented using 1‟s complement

The value so obtained is called as checksum.

 Case-01: Result = 0 (If the result is zero)

 Receiver assumes that no error occurred in the data during the

Receiver accepts the data.

 Case-02: Result ≠ 0 (If the result is non-zero)

Original data : 10101001 00111001

10101001 00111001 00011101

Received data : 10101001 00111001 00011101

It detects most errors involving an even number of bits.

If one or more bits of a segment are damaged and the

At sender side,

The given data unit is divided into segments of 8 bits as-

Now, 1‟s complement is taken which is 11011010.

Sum of all segments + Checksum value =

 00100101 + 11011010= 11111111

Complemented value = 00000000

Since the result is 0, receiver assumes no error occurred in the data

~ can be handled in two ways

when an error is discovered, the receiver can have the

 a receiver can use an error-correcting code, which

 A feedback channel is required for this system.

~ to calculate the number of redundancy bits (R) required

 positions of redundancy bits in Hamming code

 The redundant bits are inserted at each 2n bit where

Calculating Even Parity

You might also like