Scribd
Upload
100 views

Error Detection Techniques

This document discusses error detection and correction in data transmission. It describes four main types of errors: single-bit, multiple-bit, burst error. It then explains four methods of error detection: vertical redundancy check (VRC), longitudinal redundancy check (LRC), cyclic redundancy check (CRC), and checksum. CRC adds check bits to the message to create a remainder that is sent and used to detect errors. Checksum adds message sections and complements the sum to detect errors involving an odd number of bits.

Uploaded by

SahilPrabhakar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
100 views

Error Detection Techniques

This document discusses error detection and correction in data transmission. It describes four main types of errors: single-bit, multiple-bit, burst error. It then explains four methods of error detection: vertical redundancy check (VRC), longitudinal redundancy check (LRC), cyclic redundancy check (CRC), and checksum. CRC adds check bits to the message to create a remainder that is sent and used to detect errors. Checksum adds message sections and complements the sum to detect errors involving an odd number of bits.

Uploaded by

SahilPrabhakar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 27

Error Detection

and Correction
Types of Errors
Detection
Correction

Types of Errors

Single-bit error

Multiple-bit error

Burst error

Error detection
Error detection means to decide whether the
received data is correct or not without having a
copy of the original message.
Error detection uses the concept of redundancy,
which means adding extra bits for detecting
errors at the destination.

Redundancy

Four types of redundancy checks are used


in data communications

Vertical Redundancy Check


VRC

Performance
It can detect single bit error
It can detect burst errors only if the total
number of errors is odd.

Longitudinal Redundancy Check


LRC

Longitudinal Redundancy Check (LRC)


Organize data into a table and create a parity for
each column
11100111 11011101 00111001 10101001
11100111
11011101
00111001
10101001
10101010
11100111 11011101 00111001 10101001 10101010
LRC
Original Data

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

VRC and LRC

Cyclic Redundancy Check


CRC

Cyclic Redundancy Check


Given a k-bit frame or message, the
transmitter generates an n-bit sequence,
known as a frame check sequence (FCS), so
that the resulting frame, consisting of (k+n)
bits, is exactly divisible by some
predetermined number.
The receiver then divides the incoming
frame by the same number and, if there is
no remainder, assumes that there was no
error.

Binary Division

CRC Example Encoding


x3 x2 1
= 1101
Generator
x7 x4 x3 x
= 10011010 Message

C(x) =
M(x) =
1101
k + 1 bit check
sequence c,
equivalent to a
degree-k
polynomial

10011010000
1101

Message plus k
zeros

1001
1101
1000
1101

Result:

1011
1101
1100
1101

Remainder
m mod c

1000
1101
101

Transmit message
followed by
remainder:
10011010101

CRC Example Decoding No


Errors
C(x) =
x x 1
= 1101
Generator
3

P(x) = x10 x7 x6 x4 x2 1
Received Message
1101

10011010101
1101

k + 1 bit check
sequence c,
equivalent to a
degree-k
polynomial

Received
message, no
errors

1001
1101
1000
1101

Result:

1011
1101

CRC test is passed

1100
1101
Remainder
m mod c

= 10011010101

1101
1101
0

CRC Example Decoding


with Errors

C(x) =
x3 x2 1
P(x) = x10 x7 x5 x4 x2 1
Received Message
1101
k + 1 bit check
sequence c,
equivalent to a
degree-k
polynomial

10010110101
1101
1000
1101

m mod c

Received message
Two bit errors

1011
1101

Result:

1101
1101
0101

Remainder

= 1101
Generator
= 10010110101

CRC test failed

Polynomial

Polynomial and Divisor

Standard Polynomials

Checksum

At the sender
The unit is divided into k sections, each of n
bits.
All sections are added together using ones
complement to get the sum.
The sum is complemented and becomes the
checksum.
The checksum is sent with the data

At the receiver
The unit is divided into k sections, each of n
bits.
All sections are added together using ones
complement to get the sum.
The sum is complemented.
If the result is zero, the data are accepted:
otherwise, they are rejected.

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.

You might also like