Before going toward error detection and correction, let bit explore the byte stuffing which accrues in packet transmission.

What is Byte Stuffing?

Byte stuffing is a data encoding technique used in computer networking to ensure the reliable transmission of information, particularly in the context of data framing. It involves the insertion of special control characters, known as “flag” or “escape” characters, into the data stream to distinguish them from the actual data.

The primary purpose of byte stuffing is to avoid ambiguity in data communication, especially when the data might contain patterns or sequences that could be misinterpreted as control characters by the receiving end. Here’s how byte stuffing works:

1. Flag Characters: In byte stuffing, two special “flag” characters are defined, typically at the beginning and end of a frame. These flags are not part of the actual data but serve as delimiters to mark the start and end of a frame. Common flag characters are “01111110” in binary (or 0x7E in hexadecimal) and are also known as the “start-of-frame” and “end-of-frame” markers.
2. Data Transmission: When data is sent, it can potentially include sequences that match the flag characters. If such sequences are not handled properly, it could lead to misinterpretation of the data’s boundaries.
3. Byte Stuffing: To prevent this ambiguity, a technique called byte stuffing is employed. When the sender encounters a flag character within the data, it inserts an escape character before it. The escape character serves as an indicator that the following character should not be treated as a flag.
4. Receiver Handling: The receiver, upon receiving the data, monitors for the escape character. When it encounters an escape character followed by another escape character, it treats the second character as the actual data and not a flag. If it encounters an escape character followed by the flag character, it interprets it as a flag and knows that it marks the start or end of a frame.
5. De-Stuffing: To retrieve the original data, the receiver also removes the escape characters that were added during byte stuffing. This process is known as “de-stuffing.”

Byte stuffing ensures that the data and control characters are unambiguously separated within the transmitted information. It is commonly used in various networking protocols and communication systems to guarantee the integrity of the data. One well-known example is the High-Level Data Link Control (HDLC) protocol, which uses byte stuffing to delineate frames within a data stream.

Error Detection

Error detection is the process of identifying errors or data corruption that may occur during data transmission. Its primary purpose is to determine if any part of the transmitted data has been altered, lost, or corrupted in any way.

Techniques used for error detection are;

Parity Bit: In some cases, a single parity bit is used for error detection. The sender sets the parity bit to ensure that the total number of bits with a value of 1 in the data (including the parity bit) is either even or odd. The receiver checks the parity to detect errors.

Cyclic Redundancy Check (CRC): CRC is a more sophisticated error detection method used in various networking protocols. It involves polynomial division to generate a remainder, which is appended to the data. If the receiver’s calculated CRC matches the received CRC, the data is considered error-free.

Checksum: A common error detection technique involves calculating a checksum based on the data’s content. The sender generates a checksum value and sends it along with the data. The receiver also calculates its own checksum based on the received data. If the received checksum matches the calculated checksum, the data is assumed to be error-free. Otherwise, an error is detected.

How does Parity Bit Work?

A parity bit is a simple error-detection technique used in digital data communication and storage systems to help identify errors in transmitted data. It works by adding an extra bit (the parity bit) to a group of binary bits, usually a byte or word, to ensure that the total number of “1” bits in the data, including the parity bit, is either even or odd. The two common types of parity used are even parity and odd parity.

Here’s how the parity bit works:

Even Parity

• In even parity, the total number of “1” bits, including the parity bit, must be even. If the data contains an odd number of “1” bits, the parity bit is set to “1” so that the total number of “1” bits is even.
• Example: Suppose you want to transmit the binary data 1011001 using even parity. The number of “1” bits in the data is 4, which is even. So, the parity bit is set to “1” to make the total number of “1” bits in the combined data an even number. The transmitted data becomes 11011001.
• Upon receiving the data, the receiver checks the parity by counting the “1” bits. If the total number is not even, an error is detected.

Odd Parity

• In odd parity, the total number of “1” bits, including the parity bit, must be odd. If the data contains an even number of “1” bits, the parity bit is set to “1” to make the total number of “1” bits odd.
• Example: If you want to transmit the binary data 1011001 using odd parity, you calculate that the number of “1” bits in the data is 4, which is even. To make it odd, the parity bit is set to “1,” resulting in the transmitted data 11011001.
• At the receiving end, the receiver checks the parity by counting the “1” bits. If the total number is not odd, an error is detected.

Error Detection

• When the data is received, the receiver calculates the parity by counting the “1” bits, including the received parity bit. If the parity doesn’t match the expected parity (even or odd), an error is detected, indicating that the data may have been corrupted during transmission.

Parity bits are a simple and effective means of detecting errors in data transmission. They can identify errors caused by single-bit flips or other minor disruptions. However, they are not suitable for correcting errors, as they can only detect the presence of errors. More advanced error-correction techniques, such as Hamming codes or Reed-Solomon codes, are used when both error detection and correction are required.

How Does Cyclic Redundancy Check (CRC) Work?

A Cyclic Redundancy Check (CRC) is an error-detection technique used in digital data communication and storage systems to identify errors or data corruption that may occur during the transmission of binary data. CRC is a more sophisticated and powerful method compared to simple parity checks. It works by generating a CRC code, also known as a CRC checksum or CRC remainder, which is appended to the data to create a codeword. The receiving end can then use this code to check for errors and detect whether the data has been corrupted during transmission. Here’s how CRC works:

Data word to be sent – 100100
Key – 1101 [ Or generator polynomial x³ + x² + 1]
Sender Side:

The remainder is 001 and hence the encoded data sent is 100100001.

Receiver Side:
Code word received at the receiver side 100100001

The remainder is all zeros. Hence, the data received has no error.

CRC is widely used in various networking protocols, data storage systems, and communication applications. It offers a high level of error detection capability, but it should be noted that CRC is primarily for error detection, not correction. If error correction is needed, more advanced error-correcting codes, such as Reed-Solomon codes, are employed.

How Does Checksum Work?

A checksum is a simple and effective way to ensure data integrity during transmission or storage. It works by calculating a unique value, often a sum or mathematical function, based on the data being checked. This value, known as the checksum, is then sent or stored along with the data. This method makes use of the Checksum Generator on the Sender side and the Checksum Checker on the Receiver side.

Example – 
If the data unit to be transmitted is 10101001 00111001, the following procedure is used at the Sender site and Receiver site. 

10101001 subunit 1
00111001 subunit 2
11100010 sum (using 1s complement)
00011101 checksum (complement of sum)

So data transmitted to the receiver is: 10101001 00111001+ 00011101 (Data + Checksum)

Receiver Side:

10101001 subunit 1
00111001 subunit 2
00011101 checksum
11111111 sum
00000000 sum’s complement

Result is zero, it means no error.

Self Evaluation

• Why do byte stuffing is used in data communication?
• What is the primary purpose of bit parity in error detection?
• How does CRC differ from other error detection techniques like bit parity and checksum?
• What is the purpose of a checksum in data communication?