Methods of error detection Revision Notes

When data is sent from one device to another, it passes through various physical media and electronic components. During this journey, the data can be corrupted or changed unintentionally. Verifying data after transmission ensures that the received information matches what was originally sent, maintaining data integrity.

Without verification, errors could go unnoticed, leading to incorrect processing, faulty decisions, or system failures. For example, if a bank transaction amount is altered during transmission, it could cause financial discrepancies. Therefore, verification is a critical step in reliable communication systems.

• Verification confirms data accuracy after transmission.
• Prevents undetected errors from causing problems.
• Essential for trustworthy communication and data processing.

Errors during data transmission can take several forms: data loss, data gain, and data alteration. Data loss occurs when bits or entire segments of data fail to arrive at the destination. Data gain means extra bits are added mistakenly, which were not part of the original message. Data alteration involves bits being changed from their original state, such as a 0 flipping to a 1 or vice versa.

Each type of error can disrupt the meaning of the data. For example, if a binary message '1010' loses a bit and becomes '110', the information content changes, potentially causing incorrect outcomes.

• Data loss: missing bits or segments.
• Data gain: extra unintended bits added.
• Data alteration: bits changed from original values.

One of the main causes of transmission errors is interference, which includes any unwanted signals that disrupt the data being sent. Interference can come from electromagnetic sources like radio waves, electrical equipment, or even physical obstacles.

Noise is a type of interference that randomly affects the signal, causing bits to flip or be lost. For example, static on a telephone line can cause errors in the transmitted data. The longer or more complex the transmission path, the higher the chance of interference affecting the data.

Understanding interference helps in designing systems with error detection and correction methods to maintain data integrity.

• Interference disrupts signal quality during transmission.
• Sources include electromagnetic signals and physical obstacles.
• Noise causes random bit errors by altering signals.

When errors occur and are not detected or corrected, the integrity of the data is compromised. This means the received data no longer accurately represents the original information. In critical systems, such as medical devices or financial transactions, this can lead to serious consequences.

Data integrity issues can cause software crashes, incorrect outputs, or security vulnerabilities. Therefore, systems often include verification steps and error-handling protocols to detect and manage errors promptly.

For example, a corrupted software update transmitted without verification could cause a device to malfunction.

• Errors compromise data integrity and reliability.
• Undetected errors can cause system failures or incorrect results.
• Verification and error handling protect against these risks.

In summary, verifying data after transmission is essential because errors such as data loss, gain, or alteration can occur due to interference and noise. Recognizing these causes helps in implementing effective error detection and correction techniques.

For instance, consider sending the binary message '1101011' over a wireless link. Interference might flip one bit, changing it to '1101111'. Without verification, the receiver would accept incorrect data. With verification, the error can be detected and corrected or the data retransmitted, ensuring accuracy.

This process is fundamental in all digital communication systems to maintain trustworthiness and functionality.

• Verification detects errors caused by interference.
• Example: bit flip in binary message due to noise.
• Ensures reliable and accurate data communication.

When data is transmitted between devices, errors can occur due to interference, noise, or hardware faults. Detecting these errors is essential to ensure the data received is the same as the data sent. Various methods exist to detect errors, each with different complexity and reliability. This note covers three common methods: parity checks, checksums, and echo checks.

• Errors can alter bits during transmission, causing data corruption.
• Error detection methods help identify when data has been corrupted.
• Detecting errors allows systems to request retransmission or take corrective action.

Parity checking is a simple method that adds an extra bit, called a parity bit, to a group of data bits. This parity bit is set to make the total number of 1s either odd or even, depending on the chosen parity scheme.

In an even parity check, the parity bit is set so that the total number of 1s in the data plus the parity bit is even. For example, if the data bits are 1011001 (which has four 1s), the parity bit would be 0 to keep the total number of 1s even (4 + 0 = 4).

In an odd parity check, the parity bit is set so that the total number of 1s is odd. Using the same data bits 1011001, the parity bit would be 1 to make the total number of 1s five (4 + 1 = 5).

• Parity bit ensures total 1s are odd or even depending on scheme.
• Receiver checks parity bit against received data to detect errors.
• If parity does not match expected odd/even count, an error is detected.

Instead of adding a parity bit to each individual byte, parity can be applied to blocks of data or entire bytes, called parity bytes. This involves calculating parity bits for each byte in a block, allowing detection of errors within larger data sets.

For example, in a block of four bytes, each byte can have its own parity bit appended, forming a parity byte. This method improves error detection capability over single parity bits, especially for larger transmissions.

Parity bytes help identify which byte in a block contains an error, aiding in error localisation.

• Parity bytes extend parity checking to multiple bytes.
• Each byte in a block has its own parity bit.
• Improves error detection and localisation in larger data transmissions.

A checksum is a value calculated by summing the binary values of segments of data before transmission. This sum is sent along with the data.

At the receiving end, the same calculation is performed on the received data. If the calculated checksum matches the transmitted checksum, the data is assumed to be error-free.

For example, if data segments are 1101 (13 decimal) and 1010 (10 decimal), the checksum is 23 decimal. The receiver sums the received segments and compares to 23. A mismatch indicates an error occurred during transmission.

• Checksum is the sum of data segments sent with the data.
• Receiver recalculates checksum to verify data integrity.
• Mismatch between checksums indicates transmission error.

Echo checking involves sending data from the sender to the receiver, which then sends the exact data back to the sender.

The sender compares the echoed data with the original data sent. If they match, the data is assumed to be correct; if not, an error is detected.

This method is simple but can be time-consuming and is mainly used in systems where immediate verification is required.

• Data is sent and then echoed back to sender.
• Sender compares echoed data with original.
• Mismatch indicates an error in transmission.

When entering numerical data, errors such as mistyping or digit transposition can occur. A check digit is an additional digit added to the end of a number that helps detect these errors. It is calculated from the other digits using a specific algorithm. When the number is later entered or scanned, the check digit is recalculated and compared to the original. If they do not match, an error is detected, prompting correction before further processing.

This method provides a simple and effective way to verify data integrity without requiring complex error-checking systems. It is widely used in systems where accurate data entry is critical, such as product identification and book cataloguing.

• Check digits detect errors in data entry by verifying the integrity of the number.
• They are calculated from the other digits using a defined algorithm.
• Mismatch between calculated and original check digit indicates an error.

The calculation of a check digit depends on the system used. A common approach is to multiply each digit by a weight, sum the results, and then apply a modulus operation to find the check digit.

For example, in the ISBN-10 system, the first nine digits are multiplied by weights from 10 down to 2, summed, and the remainder when divided by 11 determines the check digit. If the remainder is 10, the check digit is represented by 'X'.

Consider the ISBN-10 number: 0-306-40615-?. The calculation is: (0×10) + (3×9) + (0×8) + (6×7) + (4×6) + (0×5) + (6×4) + (1×3) + (5×2) = 0 + 27 + 0 + 42 + 24 + 0 + 24 + 3 + 10 = 130. Then, 130 mod 11 = 9. The check digit is 11 - 9 = 2. So the full ISBN is 0-306-40615-2.

• Check digit calculation often involves weighted sums and modulus operations.
• ISBN-10 uses weights 10 to 2 and modulus 11 for its check digit.
• Example: Calculated check digit for 0-306-40615 is 2, completing the ISBN.

ISBNs uniquely identify books and rely on check digits to ensure accuracy. The older ISBN-10 format uses the method described above, while the newer ISBN-13 format uses a different calculation involving weights of 1 and 3 alternately and modulus 10.

For ISBN-13, each digit is multiplied alternately by 1 and 3, summed, and the check digit is the number that makes the total a multiple of 10.

For example, for ISBN-13: 978-0-306-40615-?, the calculation is: (9×1)+(7×3)+(8×1)+(0×3)+(3×1)+(0×3)+(6×1)+(4×3)+(0×1)+(6×3)+(1×1)+(5×3) = 9+21+8+0+3+0+6+12+0+18+1+15 = 93. The next multiple of 10 after 93 is 100, so the check digit is 100 - 93 = 7. The full ISBN-13 is 978-0-306-40615-7.

• ISBNs use check digits to verify book identifiers.
• ISBN-10 uses modulus 11 with weighted sums; ISBN-13 uses modulus 10 with alternating weights 1 and 3.
• Check digits prevent errors in book identification and ordering.

Barcodes encode product information and include check digits to verify scanning accuracy. The Universal Product Code (UPC) barcode uses a check digit calculated by summing digits in odd positions multiplied by 3, adding the sum of digits in even positions, and then finding the number that makes the total a multiple of 10.

For example, for the UPC code 03600029145?, the calculation is: (0+6+0+2+1+5)×3 + (3+0+0+9+4) = (14)×3 + 16 = 42 + 16 = 58. The next multiple of 10 after 58 is 60, so the check digit is 60 - 58 = 2. The full UPC is 036000291452.

This check digit helps detect errors from misreads or damaged barcodes during scanning, ensuring correct product identification at checkout.

• Barcodes use check digits to verify scanned data.
• UPC check digit calculation involves weighted sums of odd and even positioned digits.
• Check digits help detect scanning errors and prevent incorrect product processing.

To verify data accuracy, the system recalculates the check digit from the entered digits and compares it to the provided check digit. If they match, the data is accepted as likely correct; if not, an error is flagged.

This verification step is automatic in barcode scanners and software handling ISBNs, reducing human error and improving reliability.

Check digits do not guarantee error detection for all possible mistakes but significantly reduce common errors such as single-digit errors and some transpositions.

• Verification involves recalculating and comparing the check digit.
• Matching check digits indicate likely correct data entry.
• Check digits detect many but not all types of errors, improving data reliability.

In digital communication, data is sent in packets from a sender to a receiver. However, errors can occur due to noise, interference, or signal loss, causing data to be corrupted or lost. An Automatic Repeat Request (ARQ) system is a protocol designed to ensure that the receiver obtains the data exactly as sent, despite these errors. It achieves this by using feedback from the receiver to the sender, allowing the sender to know whether to resend data packets or proceed with new ones.

• ARQ is a feedback-based error control method.
• It ensures data integrity by detecting errors and requesting retransmission if needed.
• Commonly used in network communications and data links.

When the receiver correctly receives a data packet without errors, it sends a positive acknowledgment, known as an ACK, back to the sender. This ACK signals that the packet was received accurately and that the sender can proceed to transmit the next packet. The use of ACKs prevents unnecessary retransmissions and helps maintain efficient communication.

For example, if a sender transmits packet number 5 and receives an ACK for packet 5, it knows the packet arrived intact and can send packet 6 next.

• ACK confirms successful receipt of a data packet.
• Prevents redundant retransmission of correct data.
• Helps maintain the flow of data transmission.

If the receiver detects an error in the received packet, such as a mismatch in parity or checksum, it sends a negative acknowledgment, called a NACK, to the sender. The NACK informs the sender that the packet was corrupted or incomplete and must be resent. This mechanism ensures that errors are corrected by retransmission rather than ignored.

For instance, if packet 7 arrives with errors, the receiver sends a NACK for packet 7, prompting the sender to resend that packet until it is received correctly.

• NACK indicates a corrupted or missing packet.
• Triggers retransmission of the affected data packet.
• Ensures data integrity by correcting errors through repetition.

Timeouts are a critical component of ARQ systems. After sending a packet, the sender waits for an acknowledgment within a specified time period called the timeout interval. If no ACK or NACK is received before the timeout expires, the sender assumes the packet or acknowledgment was lost and retransmits the packet. This prevents the sender from waiting indefinitely and helps recover from lost packets or acknowledgments.

For example, if the sender transmits packet 10 but does not receive any acknowledgment within 2 seconds (timeout period), it resends packet 10 to ensure delivery.

• Timeout defines how long the sender waits for an acknowledgment.
• Prevents indefinite waiting due to lost packets or acknowledgments.
• Ensures timely retransmission to maintain communication flow.

The ARQ process can be summarised in these steps: the sender transmits a data packet and starts a timer. The receiver checks the packet for errors. If correct, it sends an ACK; if incorrect, it sends a NACK. If the sender receives an ACK, it sends the next packet. If it receives a NACK or the timer expires (timeout), it resends the same packet.

Example: A sender transmits packet 3. The receiver detects an error and sends a NACK. The sender resends packet 3. This time, the receiver sends an ACK. The sender then proceeds to packet 4.

This cycle continues until all packets are correctly received, ensuring reliable data transmission.

• Sender transmits packet and waits for ACK/NACK.
• Receiver sends ACK if packet is correct, NACK if incorrect.
• Sender resends packet on NACK or timeout.
• Process repeats until all data is correctly received.