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:

to share this page with your friends, select below