Error Detection and Correction Fundamentals

---

1. Introduction: Transmission Errors

During transmission over physical media, electromagnetic noise, thermal interference, attenuation, and line cross-talk can alter the signal, flipping bits from 0 to 1 or 1 to 0.

  Transmitted: 1 0 1 0 0 1 1 0
                     | (Noise spike flips bit)
  Received:    1 0 1 1 0 1 1 0  <=== Bit Error!

Types of Errors:

1. Single-Bit Error:
   • Only one bit in the entire data unit (byte or packet) has changed from 1 to 0 or 0 to 1.
   • Rare in serial data communication because noise duration ($T_{\text{noise}}$) is typically much longer than the duration of a single bit ($T_{\text{bit}}$).
2. Burst Error:
   • Two or more bits in the data unit have changed.
   • Length of Burst: Measured from the first corrupted bit to the last corrupted bit (some intermediate bits in between may not be corrupted).
   • Example: In a $10\text{ Mbps}$ link ($T_{\text{bit}} = 0.1\text{ }\mu\text{s}$), a brief static noise burst lasting $1\text{ ms}$ affects up to $10{,}000$ bits!

 Transmitted:   0  1  0  0  0  1  0  0  0  0  1  1
 Received:      0  1  1  1  0  1  0  1  0  0  1  1
                      ^  ^        ^
                      |-- Corrupted --|
                <--- Burst Length = 6 bits --->

---

2. Redundancy Principle

To detect or correct errors without seeing the original source message, extra bits called Redundant Bits ($r$) are appended to the data bits ($k$), creating a longer transmission unit called a Codeword ($n$):

  Sender:   [ Data Bits: k ] + [ Redundant Bits: r ] = [ Codeword: n ]
                                       |
                               (Transmission)
                                       v
  Receiver: [ Codeword: n ] ──> [ Checker Logic ] ──> OK (Accept) or Error (Discard)

• Error Detection: The receiver detects that errors occurred, discards the corrupted frame, and requests retransmission (Automatic Repeat Request - ARQ).
• Error Correction (Forward Error Correction - FEC): The receiver deduces the exact positions of corrupted bits and flips them back without requiring retransmission (vital for simplex links or high-latency satellite channels).

---

3. Basic Error Detection Schemes

A. Simple Parity Check

Appends a single redundant parity bit ($r = 1$) to a data block of $k$ bits to make the total number of 1s either even or odd.

• Even Parity: Parity bit is set such that the count of 1s in the codeword is even.
• Odd Parity: Parity bit is set such that the count of 1s in the codeword is odd.
• Limitation: Can detect all single-bit errors and any odd number of errors. It fails completely to detect any even number of bit errors (e.g., if two bits flip, the parity remains unchanged).

B. Two-Dimensional (2D) Parity Check

Organizes data into a table (rows and columns). A parity bit is calculated for each row, and a parity byte is calculated for all columns.

       Bit 1  Bit 2  Bit 3  Bit 4  Bit 5  Bit 6  Bit 7  [Row Parity]
 Byte 1: 1      0      1      1      0      0      1       (0)
 Byte 2: 0      1      1      0      1      0      0       (0)
 Byte 3: 1      1      0      1      1      1      0       (1)
 -------------------------------------------------------------
 [Col]:  0      0      0      0      0      1      1       (1) <=== Parity Byte

• Detection Capability: Detects all 1-bit, 2-bit, and 3-bit errors, and most burst errors.
• Correction Capability: If a single bit flips, the intersection of the corrupted row and corrupted column pinpoints the exact erroneous bit, allowing 1-bit error correction.

C. Internet Checksum

Used by network/transport layer protocols (IPv4, ICMP, UDP, TCP).

• Algorithm (Sender):
  1. Data unit is divided into 16-bit words.
  2. All 16-bit words are added using One's Complement Arithmetic (if an overflow carry occurs past 16 bits, it wraps around and is added to the least significant bit).
  3. The final sum is inverted (complemented bitwise) to form the Checksum.
  4. The checksum is sent along with the data.
• Algorithm (Receiver):
  1. Receiver sums all received 16-bit words including the checksum in one's complement.
  2. If the result is all 1s (0xFFFF, or 0 after complement), the data is accepted as error-free; otherwise, it is rejected.

---

4. Detection vs. Correction Trade-offs

Parameter	Error Detection (with ARQ)	Error Correction (FEC)
Redundancy Bits ($r$)	Very small ($16\text{ to }32$ bits for CRC)	Much larger (Hamming, Reed-Solomon)
Bandwidth Overhead	Minimal	High
Computation Complexity	Fast, simple hardware shift registers	Complex decoding matrices
Channel Suitability	Channels with feedback & low error rate (LANs)	Channels with long round-trip delay (Satellites) or no feedback

---

5. Key Exam Questions & Numericals

1. Calculate the checksum for the following two 8-bit bytes using 1's complement arithmetic:
   • Byte 1: 10011001, Byte 2: 11100010
   • Sum:

• Wrap-around carry:

• One's complement (Checksum):

2. Why does Simple Parity fail to detect double-bit errors?
   • Flipping two bits changes the count of 1s by $+2$, $-2$, or $0$. In all cases, the parity (evenness or oddness) remains unchanged, leaving the error completely invisible to the receiver.
3. What is Forward Error Correction (FEC) and where is it mandatory?
   • FEC is an error control method where the receiver detects and corrects errors without retransmission. It is mandatory in simplex links (no return path) and deep-space communications where round-trip propagation delay makes retransmission impractical.