Error detection (parity, CRC, checksum) in Computer Networks - Step-by-Step Execution

Concept Flow - Error detection (parity, CRC, checksum)

Data to send

↓

Add error detection code

↓

Send data + code

↓

Receive data + code

↓

Check error detection code

↓

Accept

Data is sent with extra bits for error checking. Receiver uses these bits to detect errors and decide if data is correct or needs resending.

Execution Sample

Computer Networks

Data bits: 1011001
Parity bit: 1 (even parity)
Send: 10110011
Receiver checks parity
If parity matches, accept data

This example shows adding a parity bit to data and checking it at the receiver to detect errors.

Analysis Table

Step	Data bits	Parity bit	Parity Check Result	Action
1	1011001	Calculate parity bit (even parity)	Parity bit = 1	Append parity bit to data
2	10110011	Received parity bit = 1	Check parity of received bits	Parity matches, no error detected
3	10110001 (error introduced)	Received parity bit = 1	Check parity of received bits	Parity mismatch, error detected
4	-	-	-	Request resend or error correction

💡 Error detected when parity check fails, triggering resend or correction

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
Data bits	1011001	1011001	10110011	10110001	10110001 (with error)
Parity bit	N/A	1	1	1	1
Parity check result	N/A	N/A	Match	Mismatch	Mismatch

Key Insights - 3 Insights

Why does the parity bit help detect errors?

The parity bit makes the total number of 1s even (or odd). If a single bit flips during transmission, the parity will not match, signaling an error (see execution_table step 3).

Can parity detect all errors?

No, parity can detect only an odd number of bit errors. If two bits flip, parity may still match, missing the error.

What happens if an error is detected?

The receiver requests the sender to resend the data or uses error correction methods (see execution_table step 4).

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the parity check result?

A Parity matches, no error detected

B Parity mismatch, error detected

C Parity bit not calculated

D Data bits are incorrect

💡 Hint

Check the 'Parity Check Result' column at step 2 in execution_table

At which step does the error get detected according to the execution_table?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for 'Parity mismatch' in the 'Parity Check Result' column

If the parity bit was not added, how would the error detection change?

A Errors would still be detected reliably

B Errors might not be detected at all

C More errors would be introduced

D Data size would increase

💡 Hint

Refer to the role of parity bit in variable_tracker and execution_table

Concept Snapshot

Error detection adds extra bits (parity, CRC, checksum) to data.
Parity bit makes total 1s even or odd to detect single-bit errors.
CRC uses polynomial division for stronger error detection.
Checksum sums data parts to detect errors.
Receiver checks these codes to accept or request resend.

Full Transcript

Error detection methods add extra bits to data before sending. Parity bit ensures the total number of 1s is even or odd, helping detect single-bit errors. CRC uses a mathematical division method to detect more complex errors. Checksum adds parts of data to detect errors. When data arrives, the receiver checks these codes. If they match, data is accepted. If not, the receiver asks for resend or corrects errors. This process helps keep data accurate during transmission.

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