Error Detection and Correction in Computer Networking
It is one of the most important works handled by the data link layer (know about the Layers of OSI Model). Data can be corrupted during transmission, so some applications are required that errors be detected and corrected.
Types of error:
What is Redundancy: To detect or correct errors, we need to send extra (redundant) bits with data.
Detection and correction: the correction of errors is more difficult than the detection.
There are two methods of error correction:
Forward error correction: Forward error correction is the process in which the receiver tries to guess the message by using redundant bits. This is possible if the number of errors is small.
Correction by retransmission: It is a technique in which the receiver detects the occurrence of an error and asks the sender to resend the message. Resending is repeated until a message arrives that the receiver believes its error free.
Coding:
Redundancy is achieved through various coding schemes.
The sender adds redundant bits through a process that creates a relationships between the bits and the actual data. The receiver checks the relationships to detect and correct the errors accordingly.
Coding scheme are divided into two broad categories:
Block coding: in block coding, we divide our message in to blocks, each of k bits, called Datawords and add r redundant bits to each block to make the length n=k+r. The resulting n bit blocks are called Codewords.
From the moment, it is important to know that we have a set of Datawords each of size k and a set of Codewords each of size n.
With k bits we can create a combination of (2)k Datawords; (2 to the power k)
With n bits we can create a combination of (2)n Codewords. (2 to the power n)
Since n>k, the number of possible Codewords is larger than the number of possible Datawords.
The block coding process is one to one, the same Dataword is always encoded as the same Codeword. This means that we have (2)n-(2)k Codewords that are not used. We call this Codewords invalid or illegal.
Hamming distance:
The hamming distance between two words is the number of differences between corresponding bits.
Ex. D(000, 011) is 2
Types of error:
- Single bit error: Means that only one bit of a given data unit is changed from 1 to 0 or from 0 to 1.
- Burst error: Means that 2 or more bits in the data unit have changed.
What is Redundancy: To detect or correct errors, we need to send extra (redundant) bits with data.
Detection and correction: the correction of errors is more difficult than the detection.
Method of error correction: |
|---|
- Forward error correction, and
- Correction by retransmission.
Forward error correction: Forward error correction is the process in which the receiver tries to guess the message by using redundant bits. This is possible if the number of errors is small.
Correction by retransmission: It is a technique in which the receiver detects the occurrence of an error and asks the sender to resend the message. Resending is repeated until a message arrives that the receiver believes its error free.
Coding:
Redundancy is achieved through various coding schemes.
The sender adds redundant bits through a process that creates a relationships between the bits and the actual data. The receiver checks the relationships to detect and correct the errors accordingly.
Coding scheme are divided into two broad categories:
- Block coding
- Convolution coding
Block coding: in block coding, we divide our message in to blocks, each of k bits, called Datawords and add r redundant bits to each block to make the length n=k+r. The resulting n bit blocks are called Codewords.
From the moment, it is important to know that we have a set of Datawords each of size k and a set of Codewords each of size n.
With k bits we can create a combination of (2)k Datawords; (2 to the power k)
With n bits we can create a combination of (2)n Codewords. (2 to the power n)
Since n>k, the number of possible Codewords is larger than the number of possible Datawords.
The block coding process is one to one, the same Dataword is always encoded as the same Codeword. This means that we have (2)n-(2)k Codewords that are not used. We call this Codewords invalid or illegal.
Hamming distance:
The hamming distance between two words is the number of differences between corresponding bits.
Ex. D(000, 011) is 2
No comments: