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= 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
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:
to share this page with your friends, select below
No comments:
Post a Comment