Error Detection in Computer Networks

When data is transmitted from one device to another device, the system does not guarantee whether the data received by the device is identical to the data transmitted by another device. An Error is a situation when the message received at the receiver end is not identical to the message transmitted.

Importance of Error Detection

The significance of error detection in sending and receiving electronic data. The varied mediums that data could be sent over (copper wire, fiber optic cable, and wirelessly) can all have noise interference, loss of data, and distortion. But particularly in transactions, medical files, or control data, even small errors can have massive impacts.

Below are a few of the reasons that error detection in these scenarios is necessary:

1. Data Integrity: The data at the receiving end should be the same as the data at the sending end.
2. System Reliability: It increases the dependability of the communication method.
3. Fault Isolation: It helps identify faulty communication links or devices.
4. Efficient Communication: It stops the spread of damaged data to the upper levels of the system.
5. Security Enhancement: Accidental errors that could be misinterpreted as intentional corruption are identifiable.

Types Of Errors

Errors can be classified into two categories:

• Single-Bit Error
• Burst Error

Single-Bit Error:

The only one bit of a given data unit is changed from 1 to 0 or from 0 to 1.

In the above figure, the message which is sent is corrupted as single-bit, i.e., 0 bit is changed to 1.

Single-Bit Error does not appear more likely in Serial Data Transmission. For example, Sender sends the data at 10 Mbps, this means that the bit lasts only for 1 ?s and for a single-bit error to occurred, a noise must be more than 1 ?s.

Single-Bit Error mainly occurs in Parallel Data Transmission. For example, if eight wires are used to send the eight bits of a byte, if one of the wire is noisy, then single-bit is corrupted per byte.

Burst Error:

The two or more bits are changed from 0 to 1 or from 1 to 0 is known as Burst Error.

The Burst Error is determined from the first corrupted bit to the last corrupted bit. These errors are caused by:

• Electrical interference
• Signal fading
• Synchronization loss
• Faulty hardware

Most basic error detection methods have a problem with long burst errors. CRC is designed to address long burst errors. Depending on the CRC polynomial selection, it can address all burst errors smaller than the polynomial's degree and most of the larger burst errors as well.

The duration of noise in Burst Error is more than the duration of noise in Single-Bit.

Burst Errors are most likely to occurr in Serial Data Transmission.

The number of affected bits depends on the duration of the noise and data rate.

Error Detecting Techniques:

The most popular Error Detecting Techniques are:

• Single parity check
• Two-dimensional parity check
• Checksum
• Cyclic redundancy check

Single Parity Check

• Single Parity checking is the simple mechanism and inexpensive to detect the errors.
• In this technique, a redundant bit is also known as a parity bit which is appended at the end of the data unit so that the number of 1s becomes even. Therefore, the total number of transmitted bits would be 9 bits.
• If the number of 1s bits is odd, then parity bit 1 is appended and if the number of 1s bits is even, then parity bit 0 is appended at the end of the data unit.
• At the receiving end, the parity bit is calculated from the received data bits and compared with the received parity bit.
• This technique generates the total number of 1s even, so it is known as even-parity checking.

Drawbacks Of Single Parity Checking

• It can only detect single-bit errors which are very rare.
• If two bits are interchanged, then it cannot detect the errors.

Two-Dimensional Parity Check

• Performance can be improved by using Two-Dimensional Parity Check which organizes the data in the form of a table.
• Parity check bits are computed for each row, which is equivalent to the single-parity check.
• In Two-Dimensional Parity check, a block of bits is divided into rows, and the redundant row of bits is added to the whole block.
• At the receiving end, the parity bits are compared with the parity bits computed from the received data.

Drawbacks Of 2D Parity Check

• If two bits in one data unit are corrupted and two bits exactly the same position in another data unit are also corrupted, then 2D Parity checker will not be able to detect the error.
• This technique cannot be used to detect the 4-bit errors or more in some cases.

Checksum

A Checksum is an error detection technique based on the concept of redundancy.

It is divided into two parts:

Checksum Generator

A Checksum is generated at the sending side. Checksum generator subdivides the data into equal segments of n bits each, and all these segments are added together by using one's complement arithmetic. The sum is complemented and appended to the original data, known as checksum field. The extended data is transmitted across the network.

Suppose L is the total sum of the data segments, then the checksum would be ?L

Checksum Checker

A Checksum is verified at the receiving side. The receiver subdivides the incoming data into equal segments of n bits each, and all these segments are added together, and then this sum is complemented. If the complement of the sum is zero, then the data is accepted otherwise data is rejected.

Cyclic Redundancy Check (CRC)

CRC is a redundancy error technique used to determine the error.

Following are the steps used in CRC for error detection:

• In CRC technique, a string of n 0s is appended to the data unit, and this n number is less than the number of bits in a predetermined number, known as division which is n+1 bits.
• Secondly, the newly extended data is divided by a divisor using a process is known as binary division. The remainder generated from this division is known as CRC remainder.
• Thirdly, the CRC remainder replaces the appended 0s at the end of the original data. This newly generated unit is sent to the receiver.
• The receiver receives the data followed by the CRC remainder. The receiver will treat this whole unit as a single unit, and it is divided by the same divisor that was used to find the CRC remainder.

If the resultant of this division is zero which means that it has no error, and the data is accepted.

If the resultant of this division is not zero which means that the data consists of an error. Therefore, the data is discarded.

Let's understand this concept through an example:

Suppose the original data is 11100 and divisor is 1001.

CRC Generator

• A CRC generator uses a modulo-2 division. Firstly, three zeroes are appended at the end of the data as the length of the divisor is 4 and we know that the length of the string 0s to be appended is always one less than the length of the divisor.
• Now, the string becomes 11100000, and the resultant string is divided by the divisor 1001.
• The remainder generated from the binary division is known as CRC remainder. The generated value of the CRC remainder is 111.
• CRC remainder replaces the appended string of 0s at the end of the data unit, and the final string would be 11100111 which is sent across the network.

CRC Checker

• The functionality of the CRC checker is similar to the CRC generator.
• When the string 11100111 is received at the receiving end, then CRC checker performs the modulo-2 division.
• A string is divided by the same divisor, i.e., 1001.
• In this case, CRC checker generates the remainder of zero. Therefore, the data is accepted.

Error Detection Capability of CRC

The cyclic redundancy check (CRC) technique is the most prominent one that is able to identify errors easily. The effectiveness of error detection using CRC is based on the generator polynomial used. Selecting the proper polynomial assists CRC in efficiently identifying varying error distributions.

Some errors that CRC aids in identifying include:

1. All single-bit errors

A single-bit error that exists in the generator polynomial will always result in a single-bit error. A single-bit error creates a remainder and thus will be detected.

2. All double-bit errors

CRC will identify double-bit errors as long as the generator polynomial does not divide for some value of k < frame length.

3. All odd-numbered bit errors

If the polynomial possesses the (x+1) element, CRC will be able to identify documents that contain an odd number of bit changes.

4. Burst errors

Burst errors less than or equal to the generator polynomial of the CRC will be detected by the CRC. If the number of burst identifiers is greater than that of the generator polynomial, there is a high likelihood that CRC will identify that error.

Difference between Error Detection and Error Correction

In data communication and computer networks, errors may occur during the transmission of data due to noise, interference, or hardware faults. To ensure reliable communication, two important techniques are used: Error Detection and Error Correction. Although both aim to improve data accuracy, they serve different purposes.

Error Detection: The receiver only verifies if the incoming data is original or if it has been corrupted. If an error is sensed, the data is thrown away, and a retransmission is requested.

Error Correction: The receiver detects and corrects the error on its own, using the redundant data, and does not require a retransmission.

In most of the communication systems, the preference is to use error detection instead of error correction, since it is less redundant and less complex from a computational standpoint. In systems where retransmission becomes expensive or impossible, e.g., satellite communication or deep space probes, error correction becomes an absolute necessity.

Comparison of Error-Detecting Techniques

In data communication, errors can occur during transmission due to noise, interference, or hardware faults. Error-detecting techniques are used to identify whether transmitted data has been corrupted. The most commonly used techniques are Parity Check, Checksum, and Cyclic Redundancy Check (CRC).

Among the methods, CRC has the highest error-detecting capabilities, which is a driving factor in why it is so commonly used in data link and physical layer protocols.

Error Detection in Network Layers

Different layers possess the ability to employ methods to detect errors in the various models of the OSI and TCP/IP framework.

1. Physical Layer

Error detection is the least prevalent in the physical layer. Error detection is typically performed in the upper layers. Certain physical layer tools might detect problems on the signal level (e.g., loss of carrier or signal noise).

2. Data Link Layer

Error detection and possibly correction are primary functions of the data link layer. The use of CRC and parity checks is common in this layer. Different CRC implementations are used for error detection in frames for protocols like Ethernet, HDLC, and PPP.

3. Transport Layer

Data integrity across end-to-end communication is maintained by TCP, which is one of the protocols that uses checksums. TCP can detect errors and request a retransmission.

4. Application Layer

Some applications incorporate their own error detection mechanisms, such as file transfer protocols that utilize a hashing function (MD5 or SHA) to check if the file is the same after it is transmitted.

Error Detection in Real-World Applications

In real-world applications, error detection plays a crucial role in ensuring data integrity, system reliability, and user trust. From internet communication to banking systems and space missions, error detection is an essential component of modern technology.

1. Computer Networks

Both wired and wireless networks utilize CRC in order to find errors caused by noise, interference, or degraded signals. Frames in Ethernet networks have a CRC value in a Frame Check Sequence (FCS) field.

2. Wireless Communication

Wireless networks suffer more errors due to fading and interference. Retransmission strategies like Automatic Repeat Request (ARQ) are used in combination with error detection to make sure the data gets through.

3. Storage Systems

Memory systems, SSDs, and hard disks utilize error detection to find corrupted data. More advanced methods like Error-Correcting Codes (ECC) and two-dimensional parity are used.

4. Satellite and Space Communication

In satellite and space communication, it can be impossible or extremely expensive to perform retransmission due to long delays. Because of this, there is a combination of methods of error detection with advanced error correction to make sure data is not lost.

Advantages of Error Detection Techniques

The following are the advantages of error detection methods bring to a data communication system:

Improved Data Integrity: Data processors are more efficient and reliable because error correction helps them retain all the essential bits of a data set and thus, The Integrity of the data stays intact.

Low Cost Implementation: Most error detection techniques and methods of communication have minimal requirements for additional hardware or software.

Compatibility with High-Speed Networks: Certain techniques, such as CRC, can be quickly incorporated at the hardware level, and thus they can be used with high-speed communication.

Flexibility: The number of varying techniques and methods gives a choice, depending on the requirements of the application: for instance, a simple system may use just parity, while for a more sophisticated system, it may be required to use CRC.

Layered Network Design: The reliability of the system increases as error detection is used at different levels of the network protocol stack.

Conclusion

Error detection is a fundamental requirement in modern digital systems. From computer networks and wireless communication to banking, healthcare, and space technology, error detection ensures data integrity and system reliability. With the increasing demand for high-speed and reliable data transmission, effective error detection techniques such as checksum and CRC will continue to be essential in real-world applications.