Chapter 10 Error Detection and Correction

Chapter 10 of Data Communications and Networking by Behrouz A. Forouzan, titled "Error Detection and Correction", explains techniques for ensuring data accuracy during transmission. Below are detailed notes from the chapter:

1. Introduction

• Errors in Transmission: Data may be corrupted during transmission due to noise, interference, or other factors.

• Types of Errors:

  1. Single-Bit Error: Only one bit of a data unit changes (e.g., 0 to 1 or 1 to 0).

  2. Burst Error: Two or more bits in the data unit change, which may or may not be consecutive.

• Error Detection and Correction: Detecting errors means identifying whether any errors have occurred, while correcting errors involves identifying and fixing them.

2. Redundancy

• Redundancy: Extra bits (redundant bits) are added to the original data to detect or correct errors. These bits help identify whether the received data has been altered during transmission.

3. Detection vs. Correction

• Error Detection: Focuses on determining if an error has occurred. It does not provide information about the number or location of errors.

• Error Correction: More complex, as it requires identifying the specific error and its position. This process is more resource-intensive than detection.

4. Forward Error Correction vs. Retransmission

• Forward Error Correction (FEC): The receiver uses redundant bits to correct errors without needing a retransmission.

• Retransmission: The receiver detects the error and requests the sender to resend the data.

5. Coding for Error Detection and Correction

• Coding: Redundancy is introduced through coding schemes. Common types of coding include:

  • Block Coding: Data is divided into blocks, and redundant bits are added.

  • Convolution Coding: More complex but beyond the scope of the chapter.

6. Block Coding

• Datawords and Codewords: The message is divided into blocks of bits (datawords), and additional redundant bits are added to create codewords.

• Error Detection in Block Coding:

  • The receiver checks whether the received codeword matches any valid codeword from a pre-determined set.

  • If the codeword is valid, the message is accepted. Otherwise, it is discarded.

7. Hamming Distance

• Hamming Distance: The number of bit differences between two codewords. It is used to measure the ability of a coding scheme to detect or correct errors.

• Minimum Hamming Distance: A larger Hamming distance allows for detecting and correcting more errors. For instance, to detect up to s errors, the minimum Hamming distance must be at least s + 1.

8. Linear Block Codes

• Linear Codes: In these codes, the XOR of any two valid codewords produces another valid codeword.

• Parity Check Code: A simple error-detecting code, where a single parity bit is added to detect errors.

9. Cyclic Codes

• Cyclic Redundancy Check (CRC): A popular error-detecting code used in networks such as LANs and WANs. It is a special type of linear block code where codewords can be cyclically shifted.

• CRC Generator: Uses polynomial division to generate redundant bits for detecting errors.

10. Checksum

• Internet Checksum: A technique used primarily in network protocols. The checksum is calculated by summing the data bits and then taking the one's complement of the result.

• Error Detection: If the calculated checksum does not match the received checksum, an error is detected.

11. Summary

• Errors during data transmission can be detected or corrected using various coding techniques.

• Block codes, Hamming codes, cyclic codes, and checksums are commonly used methods for ensuring the accuracy of data transmission.

These notes provide a comprehensive understanding of error detection and correction methods, highlighting key techniques like block coding, Hamming distance, and CRC .