Error detection (parity, CRC, checksum) in Computer Networks - Full Explanation

Introduction

When data travels from one place to another, it can get changed by mistakes or noise. Detecting these errors quickly helps computers know if the data is correct or needs to be sent again.

Explanation

Parity

Parity adds a single extra bit to a group of data bits to make the total number of 1s either even or odd. This helps detect if one bit has changed during transmission. It is simple but can only detect an odd number of errors.

Parity uses one extra bit to check if data has an odd number of errors.

Checksum

A checksum adds up all the data values in a message and sends this sum along with the data. The receiver adds the data again and compares it to the checksum to find errors. It can detect many errors but might miss some if errors cancel out.

Checksum sums data values to find errors by comparing sums at sender and receiver.

Cyclic Redundancy Check (CRC)

CRC treats data as a long binary number and divides it by a fixed binary number called a polynomial. The remainder of this division is sent with the data. The receiver does the same division and checks the remainder to detect errors. CRC is very good at finding common errors.

CRC uses division by a fixed number to create a strong error-detecting code.

Real World Analogy

Imagine sending a letter with a secret code that helps the receiver know if any words got smudged or changed during delivery. Different codes catch different kinds of mistakes, from simple typos to complex smudges.

Parity → A simple yes/no check like counting if the number of red balls in a bag is odd or even

Checksum → Adding up the prices of items on a shopping list to check if the total bill matches

Cyclic Redundancy Check (CRC) → Using a special math puzzle on the letter that only fits if no words were changed

Diagram

Diagram

┌───────────────┐       ┌───────────────┐       ┌───────────────┐
│   Sender      │       │   Channel     │       │   Receiver    │
│               │──────▶│ (Data + Code) │──────▶│               │
│ Data + Parity │       │               │       │ Check Parity  │
│ Data + Checksum│      │               │       │ Checksum Calc │
│ Data + CRC    │       │               │       │ Check CRC     │
└───────────────┘       └───────────────┘       └───────────────┘

This diagram shows data sent from sender to receiver with added error detection codes passing through a channel.

Key Facts

Parity bit → A single bit added to data to make the number of 1s even or odd for error detection.

Checksum → A value calculated by adding data parts to detect errors during transmission.

Cyclic Redundancy Check (CRC) → An error-detecting code using polynomial division to find errors in data.

Error detection → The process of finding mistakes in data after transmission.

Common Confusions

Parity can detect all errors in data.

Parity can detect all errors in data. Parity only detects errors if an odd number of bits are wrong; it misses errors with an even number of bit changes.

Checksum always guarantees error-free data.

Checksum always guarantees error-free data. Checksum can miss errors if multiple errors cancel each other out, so it is not foolproof.

CRC is the same as checksum.

CRC is the same as checksum. CRC uses polynomial division and is more powerful and reliable than simple checksum methods.

Summary

Error detection helps find mistakes in data sent over networks to ensure accuracy.

Parity uses one bit to check for odd errors, checksum sums data values, and CRC uses math division for strong error detection.

Each method has strengths and weaknesses, with CRC being the most reliable among the three.

Practice

1. What is the main purpose of error detection methods like parity, CRC, and checksum in data communication?

easy

A. To find mistakes in data transmission

B. To increase the speed of data transfer

C. To compress data for storage

D. To encrypt data for security

Solution

1. Step 1: Understand the role of error detection

   Error detection methods are designed to identify errors that occur during data transmission.

2. Step 2: Compare options with the purpose

   Only To find mistakes in data transmission correctly states that these methods find mistakes in data transmission, while others describe unrelated functions.

3. Final Answer:

   To find mistakes in data transmission -> Option A

4. Quick Check:

   Error detection = Find mistakes [OK]

Hint: Error detection finds transmission mistakes fast [OK]

Common Mistakes:

• Confusing error detection with data encryption
• Thinking error detection speeds up data transfer
• Mixing error detection with data compression

2. Which of the following correctly describes a parity bit?

easy

A. A bit added to make the total number of 1s even or odd

B. A bit used to encrypt data

C. A bit that compresses the data size

D. A bit that stores the checksum value

Solution

1. Step 1: Define parity bit function

   A parity bit is added to data to ensure the total number of 1s is either even or odd, helping detect errors.

2. Step 2: Match options with definition

   A bit added to make the total number of 1s even or odd matches this definition exactly; other options describe unrelated functions.

3. Final Answer:

   A bit added to make the total number of 1s even or odd -> Option A

4. Quick Check:

   Parity bit = Even/Odd 1s check [OK]

Hint: Parity bit counts 1s to check even or odd [OK]

Common Mistakes:

• Thinking parity bit encrypts data
• Confusing parity bit with checksum
• Assuming parity bit compresses data

3. Consider a data block with bits: 1101011. If even parity is used, what should be the parity bit added?

medium

A. 0

B. Depends on checksum

C. 1

D. Cannot determine without CRC

Solution

1. Step 1: Count the number of 1s in the data block

   The bits are 1 1 0 1 0 1 1. Counting 1s: 1+1+0+1+0+1+1 = 5 ones.

2. Step 2: Determine parity bit for even parity

   Since 5 is odd, to make total number of 1s even, parity bit must be 1.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   Odd 1s + parity 1 = even total [OK]

Hint: Count 1s; parity bit makes total even [OK]

Common Mistakes:

• Counting zeros instead of ones
• Choosing parity bit 0 when 1 is needed
• Confusing parity with checksum or CRC

4. A checksum is calculated by summing data bytes and sending the result. If the receiver's checksum does not match, what is the likely problem?

medium

A. Data was compressed incorrectly

B. Data was corrupted during transmission

C. Data was encrypted with wrong key

D. Data was sent too fast

Solution

1. Step 1: Understand checksum purpose

   Checksum verifies data integrity by comparing sums at sender and receiver.

2. Step 2: Interpret checksum mismatch

   If checksums differ, data was likely corrupted or changed during transmission.

3. Final Answer:

   Data was corrupted during transmission -> Option B

4. Quick Check:

   Checksum mismatch = Data corruption [OK]

Hint: Checksum mismatch means data error [OK]

Common Mistakes:

• Assuming compression or encryption caused checksum error
• Ignoring data corruption possibility
• Thinking transmission speed affects checksum

5. A data packet uses CRC with a generator polynomial of x^3 + x + 1. If the data bits are 1011, which CRC remainder bits should be appended to detect errors?

hard

A. '000' after dividing data by polynomial

B. '000' because CRC always appends zeros

C. '111' after adding parity bit

D. '100' after dividing data by polynomial

Solution

1. Step 1: Understand CRC calculation

   CRC divides data appended with zeros by the generator polynomial and uses the remainder as CRC bits.

2. Step 2: Perform division for data 1011 and polynomial x^3+x+1

   Dividing 1011 (with 3 zeros appended) by polynomial gives remainder 100.

3. Final Answer:

   '100' after dividing data by polynomial -> Option D

4. Quick Check:

   CRC remainder = '100' [OK]

Hint: CRC remainder from polynomial division is appended [OK]

Common Mistakes:

• Confusing CRC remainder with parity bits
• Assuming CRC always appends zeros
• Skipping polynomial division step