Error Detection Correction Techniques

Error Detection & Correction Techniques
There are two types of error.

Single-bit error: In a single-bit error, only 1 bit in the data unit has changed.
Burst Error: A burst error mean that 2 or more bits in the data unit have changed.

There are many techniques to detect errors. They are
* Vertical Redundancy checking / Parity Checks
* Checksum
* Longitudinal Redundancy checkinng
* CRC (Cyclic Redundancy Check)

Parity Bits:
Parity check is one of the simplest checking mechanisms. It also referred as a VRC (Vertical Redundancy Check or Vertical Redundancy Checking). It involves adding an additional bit (called a parity bit) to a certain number of bits of data called a code word. Code word has 7 bits so as to form a byte when combined with the parity bit. In code word if the total number of 1 bits is even then the parity bit will be 0. Take the following example:

If the total number of 1 bits is odd then the parity bit will be 1.

When bit error occurs one 0 becomes 1, then receiver will count the total number of 1 bits is even so the parity bit should be zero. But here is 1, so found error by checking parity bit.

However, if two bits (or an even number of bits) had simultaneously changed as the signal was being sent, no error would have been detected.

As the parity control system can only detect an odd number of errors, it can only detect 50% of all errors. This error-detection mechanism also has the major problem that it unable to correct the errors it finds.

Checksums:
The Internet uses 16-bit checksum. Sender follows the following steps-

At sender Side:
Step-1: First, sender converts the messages into ASCII value.
Original Message
ASKII Value
M
77
y
121

32
n
110
a
97
m
109
e
101

32
i
105
s
115

32
N
78
a
97
d
100
i
105
m
109

Step-2: Then it converts the ASCII value into Hex number
Original Message
ASKII Value
Hexa Decimal
M
77
4D
y
121
79

32
20
n
110
6E
a
97
61
m
109
6D
e
101
65

32
20
i
105
69
s
115
73

32
20
N
78
4E
a
97
61
d
100
64
i
105
69
m
109
6D

Step-3: Data sets as a pair character. Each pair of characters is treated as a 16-bit integer.
Hex Number
4D79
206E
616D
6520
6973
204E
6164
696D

Step-4: Now we have to sum all the data according to column and a initial checksum which is all 0.
Carries of the next column
2
2
3
4

Message

4
D
7
9
2
0
6
E
6
1
6
D
6
5
2
0
6
9
7
3
2
0
4
E
6
1
6
4
6
9
6
D
Initial Checksum
0
0
0
0
Total
8
9
0
6

Example: 1st Column summation 9+E+D+0+3+E+4+D
= 9+14+13+3+14+4+13 = 70
70 is 46 in Hexa Decimal
So 6 in Total and 4 is carries of the next column

2nd Column summation 7+6+6+2+7+4+6+6+0=44
44+4 Carries = 48 is 30 in Hexa Decimal
So 0 in Total and 3 in Carries of the next column


Step-5: If the sum overflows 16 bits, the carry bits are added to the total. Here we found overflow 2. Now we will add this to the
Total
8
9
0
6
Last carries



2
Total
8
9
0
8

Step-6: Now we have to convert the total from Hex to binary.
Total (in Hex)
8908
Total (in Binary)
1000100100001000

Step-7: Now we have to complement the sum
Total (in binary)
1000100100001000
Complemented sum
111011011110111

Step-8: Now the complemented sum 76F7 (in Hexa Decimal) has to send with message.

At receiver end:
Step-1: When receiver get this it adds message and received checksum.
Carries of the next column
2
2
3
4

Message

4
D
7
9
2
0
6
E
6
1
6
D
6
5
2
0
6
9
7
3
2
0
4
E
6
1
6
4
6
9
6
D
Received Checksum
7
6
F
7
Total
F
F
F
D

Step-2: Receiver add the carry bit with sum.
Total
F
F
F
D
Last carries



2
Total
F
F
F
F

Step-3: Now we have to complement the sum and the sum becomes the new checksum.
Sum (in Hex)
FFFF
Complemented Sum
0000

Step-4: If the value of complemented sum is 0, the message is error free and accepted, otherwise, it is rejected.

The advantage of such checksums is the size and easy to calculate. Addition requires very little computation and the cost of sending an additional 16-bits is negligible. However, checksums do not detect all common errors, as illustrated in table

Massages

Checksum Value
Massages
Checksum value
0001
1
0001
1
0010
2
0011
3
0011
3
0011
3
0100
4
0011
3
Total
10
Total
10
Table: Checksum failure

In these case both result same but there has transmission errors but no error will detect.

Cyclic Redundancy Checks (CRC):
It is possible to detect more errors without increasing the amount of additional information in the packet using a Cyclic Redundancy Check (CRC) technique. Moreover, the hardware necessary to generate them is very simple. Data Link layer can do this check. So we will learn it later.


Click image to go:
http://nadimall.blogspot.com/2013/10/turorial-list.html

http://www.facebook.com/nadimallblog?ref=aymt_homepage_panel

to share this page with your friends, select below

No comments:

Post a Comment