6.2 Error detection and correction

Summary

This section explores error detection and correction techniques at the link layer. It revisits the concepts of simple and two-dimensional parity checks, demonstrating how errors can be detected and corrected without retransmission. The focus then shifts to the Cyclic Redundancy Check (CRC), a powerful error detection technique used in Ethernet and Wi-Fi. CRC utilizes a predefined generator bit pattern to detect burst errors, offering much stronger error detection than basic checksums. The section concludes by emphasizing the importance of CRC in modern communication systems, especially when retransmissions are impractical, such as in space communications and digital networks.

Takeaways

• 😀 The internet checksum is used in the UDP protocol to detect bit-level errors in datagrams.
• 😀 At the link layer, frames are transmitted, and error detection and correction bits (EDC) are added to ensure data integrity.
• 😀 Simple error detection can be achieved using parity checks, where a parity bit is added to ensure an even or odd number of bits.
• 😀 Two-dimensional parity checks improve error detection by detecting bit errors and also locating single-bit errors for correction without retransmission.
• 😀 Forward Error Correction (FEC) allows for error correction without retransmission, which is important in applications with long delays like space communications.
• 😀 Parity checks and the internet checksum are relatively simple error detection methods but have limitations in detecting multiple errors.
• 😀 The Cyclic Redundancy Check (CRC) is a more powerful error detection technique used in Ethernet and Wi-Fi, capable of detecting all bursts of bit errors.
• 😀 CRC works by using a generator polynomial (bit pattern) agreed upon by both the sender and the receiver to check for data integrity during transmission.
• 😀 The CRC computation involves left-shifting data and dividing it by the generator, with any remainder indicating an error.
• 😀 CRCs are widely used in real-world protocols like Ethernet and Wi-Fi because of their ability to detect a broader range of errors compared to simpler techniques like parity checks.

Q & A

What is the main topic discussed in this section?

The main topic discussed is error detection and correction at the link layer, focusing on simple parity checks, two-dimensional parity, and cyclic redundancy checks (CRC).

How does the link layer ensure data integrity?

The link layer ensures data integrity by adding error detection and correction bits (EDC) to the frames before transmission. If an error is detected during reception, the frame may be discarded or a retransmission may be requested.

What is a parity check, and how does it work?

A parity check is a simple error detection method where an additional parity bit is added to data to make the total number of 1s either even or odd. The receiver checks if the number of 1s matches the expected parity to detect errors.

What is the advantage of a two-dimensional parity check over a simple parity check?

The two-dimensional parity check provides more error detection and correction capability by calculating both row and column parity bits. It can detect and correct single bit errors without requiring retransmission.

How does a two-dimensional parity check help in locating bit errors?

In a two-dimensional parity check, if an error occurs, the receiver can identify the exact location of the error by checking both the row and column parity bits. This allows the receiver to correct the error without needing a retransmission.

What is forward error correction (FEC), and where is it used?

Forward error correction (FEC) is a technique where errors are detected and corrected at the receiver without the need for retransmission. It is used in systems like DVDs, compact discs, DSL networks, and deep-space communication.

What is the Internet checksum, and how does it compare to parity checks?

The Internet checksum is an error detection technique where the sender computes the sum of the bytes and appends the checksum to the data. Unlike parity checks, it uses byte-level checksumming but is less robust and not typically used in link layer protocols.

What is a Cyclic Redundancy Check (CRC), and why is it more powerful than the Internet checksum?

A CRC is a more robust error detection technique used in Ethernet and Wi-Fi. It uses a predefined generator bit pattern to check data integrity and can detect all bursts of bit errors smaller than the generator length, making it more powerful than the Internet checksum.

How is the CRC computed at the sender's side?

At the sender's side, the CRC is computed by left-shifting the data, appending CRC bits, and performing an XOR operation with the generator bit pattern. The result is a bit pattern that is divisible by the generator without a remainder.

Why is CRC used in practical networking systems like Ethernet and Wi-Fi?

CRC is used in Ethernet and Wi-Fi because it can detect a wide range of errors, particularly burst errors, which are common in noisy transmission environments. It is an efficient and reliable method for ensuring data integrity at the link layer.