Error Detection and Correction Techniques

Error-detection and correction techniques are crucial for reliable communication, particularly over channels that are noisy or inherently unreliable.

These methods are designed to counteract issues like bit errors, which occur when a transmitted bit flips (e.g., from 0 to 1 or 1 to 0) due to noise, interference, or signal degradation in the transmission medium.

Dual Functionality:

• Error Detection: Identifying when bit errors have occurred in a received data block. This is typically achieved by adding extra bits to the original data, known as redundancy. These redundant bits are calculated based on the data and are used at the receiver to check for consistency. If the check fails, an error is detected.
• Error Correction: A more advanced capability is error correction, where the receiver can not only detect errors but also automatically determine their precise location and fix them, often without requiring the sender to retransmit the data.

Common techniques include parity checks, checksums, Cyclic Redundancy Check (CRC), and Hamming codes.

---

Bit Error

• A bit error occurs when a transmitted bit is flipped from its original value during transmission. This means a '0' might change to a '1', or a '1' might change to a '0'.

• Causes of Bit Errors: These errors typically happen due to various physical phenomena in the transmission medium, such as noise, interference, or signal degradation. Wireless links, for example, are more prone to higher bit error rates compared to wired links.

• Consequences: A bit error can cause the receiving end to misinterpret the data, leading to data corruption or incorrect interpretation of the message.

• Detection Methods: To counteract this, bit errors are frequently detected using error-detection codes. Common techniques mentioned include parity checks and Cyclic Redundancy Check (CRC).

Single Parity Check

A single parity check is an error detection method where a single parity bit is added to a data block. The purpose of this bit is to ensure that the total count of '1's in the entire data block (including the parity bit itself) adheres to either an even or odd scheme.

Parity Bit Calculation: The value of the parity bit is determined by the number of '1's in the original data:

• Even Parity: The parity bit is chosen so that the total number of '1's in the data block (including the parity bit) is even.

• Odd Parity: The parity bit is chosen so that the total number of '1's in the data block (including the parity bit) is odd.

Error Detection at the Receiver: When the receiver gets the data block and its parity bit, it performs the same count of '1's.

If the counted number of '1's does not match the expected parity (e.g., an odd count for an even parity scheme), then an error is detected. This indicates that at least one bit error has occurred.

Limitation of single parity check is its inability to detect an even number of bit errors. If, for instance, two bits in the data flip, the total count of '1's might still appear correct, leading to an undetected error.

This makes it a relatively weak form of error protection, especially against burst errors where multiple bits are corrupted simultaneously.

Example: Single Parity Check Walkthrough

Given:

• Data word = 1101 (This is 4 bits).
• Parity type = Even parity.

Step 1: Calculate Parity Bit

• Count the number of '1's in the original data word 1101. There are three '1's, which is an odd number.
• Since the goal is to achieve even parity, a '1' is added as the parity bit to make the total count of '1's even (3 + 1 = 4).

Step 2: Codeword

• The codeword transmitted is the original data + Parity Bit: 11011.

Step 3: Error Detection Example

• Imagine that during transmission, the second bit flips from '1' to '0'. So, the received codeword becomes 10011 (instead of 11011).

• At the receiver's end, the number of '1's in 10011 is counted. There are three '1's.

• Since an odd number of '1's is found, but even parity was expected, an error is detected.

Two-Dimensional Even Parity Check

• Instead of just one parity bit for an entire data block, this method adds a parity bit for each row and each column within the data block.

• This is achieved by dividing the data (D) into 'i' rows and 'j' columns. A parity value is computed for every row and every column.

• The sum of these parity bits (i + j + 1 parity bits, if considering the overall corner bit as well) comprises the error-detection bits in the link-layer frame.

• The core principle remains the same as even parity: it ensures that the total number of '1's in each row and each column, including its respective parity bit, is even.

• If an odd parity scheme were used, the count of '1's would need to be odd.

Its key advantage is the ability to correct a single bit error. If a single bit in the data block flips (e.g., from 1 to 0 or 0 to 1), the parity of both the row and the column containing that flipped bit will be incorrect (odd, when even parity is expected). By identifying the intersection of the row and column with parity errors, the receiver can precisely locate the corrupted bit and flip it back to its original value, thereby correcting the error.

It can also detect, but not correct, any combination of two errors in a packet.

The ability of the receiver to both detect and correct errors is known as forward error correction (FEC). FEC is valuable as it can reduce the need for retransmissions and allows for immediate error correction at the receiver, which is beneficial for real-time applications or links with long propagation delays.

---

Example: Two-Dimensional Even Parity Check

A data block organized as a 4x4 matrix with additional parity bits for each row and column:

Original Data Block:

1 0 1 1 | 1 (Row Parity for row 1)
1 0 1 1 | 1 (Row Parity for row 2)
0 0 1 1 | 0 (Row Parity for row 3)
0 1 1 0 | 0 (Row Parity for row 4)
-------
0 1 1 0     (Column Parity for col 1-4)

Step 1 & 2: Verify Parity:

• The receiver checks that the number of '1's in each row and column, including the parity bits, is even. If all checks pass, the data is assumed to be uncorrupted.

Step 3: Error Detection Example (with a flipped bit):

• Assume the bit at position (row 2, column 3) flips from '1' to '0'.

• The modified data block might look like this:

1 0 1 1 | 1
1 0 o 1 | 1 (Second bit in the row 2, col 3 has flipped to 0)
0 0 1 1 | 0
0 1 1 0 | 0
-------
0 1 0 0    (Column Parity for col 1-4)

When the receiver performs parity checks:

• Row Parity Check: Row 2 would now have an odd number of '1's, indicating an error in that row.
• Column Parity Check: Column 3 would also have an odd number of '1's, indicating an error in that column.

Since both Row 2 and Column 3 show a parity error, the receiver detects an error specifically at position (Row 2, Column 3).

Step 4: Correct the Error:

• Knowing the exact location of the error (Row 2, Column 3), the receiver simply flips the bit back to its original value (from '0' to '1'). This restores the original data block and satisfies all parity checks.

This technique is a more robust form of error detection than a single parity check, commonly employed at the link layer, where error detection is often more sophisticated and implemented in hardware.

Cyclic Redundancy Check (CRC)

CRC stands for Cyclic Redundancy Check. It is an error-detection method commonly used in data communication. The core idea behind CRC is that it treats data as a binary polynomial. At the sender, this data polynomial is divided by a fixed generator polynomial. The remainder of this division is called the CRC bits, which are then appended to the data before transmission. At the receiver's end, the same division process is performed on the received data (including the appended CRC bits) by the same generator polynomial. If the remainder is non-zero, it indicates that an error has occurred during transmission. Otherwise, the data is accepted as being correct.

CRC calculations are performed using modulo-2 arithmetic, which means addition and subtraction are equivalent to bitwise exclusive-or (XOR) operations without carries or borrows.

Need for CRC

CRC is a widely adopted error-detection technique due to several key advantages:

• Error Detection: It is highly effective in detecting single-bit, double-bit, and burst errors.

• Reliability: CRC ensures high integrity of transmitted data by providing strong protection against errors.

• Efficiency: It requires minimal extra bits (redundancy) for strong error detection, making it an efficient choice for data communication.

• Ease of Implementation: CRC uses simple XOR and shift operations which makes it easy to implement in hardware/software.

• Applications: Due to its robust nature, CRC is widely used in various communication protocols and devices, including Ethernet, USB, storage devices, and other communication protocols.

The choice often depends on the layer of the protocol stack; transport layer (software) often uses checksums for simplicity and speed, while link layer (hardware) uses CRC for its stronger error detection capability.

Problem: CRC Encoding and Error Detection

Given:

• Data word D = 1011001 (7 bits). Data that needs to be transmitted.

• Generator polynomial G(x) = x³ + x + 1, which translates to its binary form 1011. The degree of this polynomial (r) is 3, which determines the number of CRC bits to be appended.

Step 1: Append zeros:

• To prepare the data for division, r = 3 zeros are appended to the data word.
• The modified data becomes 1011001000. This effectively shifts the data polynomial by r positions (multiplying by 2^r) to make room for the remainder (CRC bits).

Step 2: Perform binary division (mod-2):

• The extended data 1011001000 is divided by the generator 1011 using XOR operations (modulo-2 arithmetic).
• The example states the first division: 1011 XOR 1011 = 0000. This process continues until the end of the extended data, resulting in a final remainder = 011. This remainder is the CRC value (R).

Step 3: Form codeword:

• The codeword that will be transmitted is created by appending this remainder (CRC bits) to the original data.
• Codeword = Data + Remainder = 1011001011.

Step 4: Error detection example:

• Assume that during transmission, the 5th bit of the transmitted codeword flips from 0 to 1.
• The received codeword is now 1011101011.
• At the receiver, this modified codeword 1011101011 is again divided by the generator 1011.
• The result of this division yields a remainder = 111, which is not 000 (the expected remainder if no errors occurred).
• Therefore, an error is detected.