Introduction to Error Detection and Correction

During transmission, the bits sent from one node to another can be changed or corrupted because of noise or interference. Therefore, the data-link layer needs mechanisms to detect whether the received frame contains errors and, when possible, correct them.

At the data-link layer, a corrupted frame is generally discarded, and retransmission is handled by the appropriate protocol. Some wireless protocols may attempt to correct corrupted frames.

1. Types of Errors

There are two basic types:

Single-Bit Error

Only one bit of the data unit changes.

Sent:      0 1 0 1 0 1 0 0
Received:  0 1 0 0 0 1 0 0
                  ↑
             corrupted bit

Burst Error

Two or more bits in the data unit are changed.

Sent:      0 1 0 1 0 1 0 0 1 1
Received:  0 1 0 0 1 1 1 0 1 1
                 ↑ ↑ ↑
              burst error

Burst errors are more common because noise generally lasts longer than the duration of a single bit.

---

2. Redundancy

The basic idea behind error detection and correction is redundancy.

The sender adds some extra bits to the original data:

Original Data + Redundant Bits
          ↓
        Sender
          ↓
       Channel
          ↓
       Receiver
          ↓
Check redundant bits

The receiver uses these redundant bits to determine whether the data has been corrupted.

The redundant bits are removed after the checking process.

---

3. Error Detection vs Error Correction

Error Detection

The receiver determines:

"Has an error occurred?"

The answer is essentially Yes or No.

It does not necessarily need to know how many bits are corrupted or where they are.

Error Correction

The receiver must determine:

• How many bits are corrupted?
• Where are the corrupted bits?
• What should their correct values be?

Therefore, error correction is more difficult than error detection.

---

4. Coding

Redundancy is introduced using coding schemes.

The sender creates a relationship between:

• Actual data bits
• Redundant bits

The receiver checks this relationship to detect errors.

We broadly divides coding schemes into:

1. Block coding
2. Convolution coding

The discussion here concentrates mainly on block coding.

In short

Error detection and correction provide mechanisms for dealing with corrupted data during transmission. They use redundant bits added to the original data so that the receiver can detect, and in some cases correct, transmission errors.