Error Detection in Data Link Layer (ET: 2.5 hours)
Topic Wise Question Bank
Error Detection
    • 1
      Error Detection Error Detection
      Error Detection in Data Link Layer
      Data Link Layer
      Error Detection is the process of identifying whether the data received by a receiver has been corrupted during transmission. In a computer network, data may be changed or corrupted while traveling through a communication medium. Therefore, reliable communication requires mechanisms to detect and, when necessary, correct these errors.
      Transmission Error: When data is transmitted from one network node to another, the data may be corrupted because of noise, interference, signal problems, or other transmission issues. The errors caused during data transmission are called Transmission Errors.
      Error Control in OSI Model: Error control is mainly associated with the Data Link Layer and Transport Layer of the OSI model. These layers provide mechanisms for detecting and/or handling errors to support reliable data communication.
      Types of Transmission Errors
      There are mainly two types of transmission errors:
      • Bit Error
      • Burst Error
      1. Bit Error: A bit error occurs when only one bit of a data unit is changed during transmission. It is also called a Single-Bit Error.
      Example:
      Sender sends: 00000010
      Receiver receives: 00001010
      Here, only one bit has changed from 0 to 1. Therefore, this is a Bit Error.
      2. Burst Error: A burst error occurs when two or more bits within a data unit are affected or corrupted during transmission.
      The important point is that the burst length is measured from the first corrupted bit to the last corrupted bit, including all bits between them, whether every bit in between is actually corrupted or not.
      For example, if the first corrupted bit occurs at position 3 and the last corrupted bit occurs at position 10, the burst length is 8 bits.
      Error Detection: Error detection is the process by which the receiver determines whether the received data contains an error. The receiver normally does not have a copy of the original message, so additional information must be transmitted along with the original data.
      To make error detection possible, the sender adds some extra bits to the original data. These extra bits are called Redundant Bits or Redundancy.
      Basic Error Detection Process:
      Original Data → Generator → Redundant Bits → Data + Redundancy → Transmission → Receiver → Checker → Accept / Reject
      At the sender side, a generating function or algorithm calculates the redundant information from the original message. The redundant bits are then appended to the original data and transmitted to the receiver.
      At the receiver side, a checking function or algorithm examines the received data and calculates or verifies the redundancy. The result is compared with the expected value.
      If the check indicates that the data is correct, the receiver accepts the data. If an error is detected, the receiver rejects or discards the data and may request retransmission depending on the protocol.
      Redundancy: Redundancy means adding extra information to the original data so that the receiver can detect or correct transmission errors.
      For example, if the sender has a message, it passes the message through a generating algorithm. The algorithm produces redundant bits. These redundant bits are appended to the original message and the complete data is transmitted through the communication medium.
      The receiver separates or processes the received information using a checking algorithm. If the calculated check matches the expected check, the data is considered valid. Otherwise, an error is detected.
      Error Detection vs Error Correction
      Error Detection: Error detection determines whether an error has occurred in the received data. It generally results in a simple decision: Accept if the data is valid or Reject if an error is detected.
      Error Correction: Error correction attempts to recover the correct data after detecting an error. It is more complex than simple error detection.
      There are two common approaches to error correction:
      • Retransmission: The receiver detects an error and requests the sender to retransmit the entire data unit.
      • Error-Correcting Code: Additional redundancy allows the receiver to identify and automatically correct certain types of errors without retransmission.
      Important: Both error detection and error correction require some form of redundancy because the receiver needs additional information to determine whether the received data is correct and, in some systems, to determine how to correct it.
      Error Detection Techniques
      There are four commonly discussed error detection techniques in data communication:
      • Vertical Redundancy Check (VRC)
      • Longitudinal Redundancy Check (LRC)
      • Checksum
      • Cyclic Redundancy Check (CRC)
      1. Vertical Redundancy Check (VRC): VRC is an error detection technique that adds an additional parity bit to a group of data bits. The parity bit is used to make the number of 1s either even or odd, depending on the selected parity scheme. VRC is commonly known as the Parity Check.
      2. Longitudinal Redundancy Check (LRC): LRC organizes data into rows and columns and adds redundancy based on the bits in each column. It can detect certain errors that may not be detected by a simple parity check.
      3. Checksum: In the checksum technique, the sender divides the data into fixed-size units and performs arithmetic operations on those units to generate a checksum value. The checksum is transmitted along with the data. The receiver performs a similar calculation and compares the result to determine whether an error has occurred.
      4. Cyclic Redundancy Check (CRC): CRC is a powerful error detection technique based on binary polynomial division. The sender performs a calculation using a predefined generator polynomial and appends the resulting remainder to the data. The receiver performs a similar calculation to determine whether the received data has been corrupted.
      CRC and Checksum are widely used error detection mechanisms in computer networks and communication protocols. CRC is particularly effective at detecting burst errors.

    • 2
      Error Detection Parity
      Explain Parity Bit. How error is detected by Parity Biit?
      Data Link Layer
      Parity Bit: A parity bit is an additional bit added to a data sequence to detect errors during data transmission. It is the simplest type of error-detecting code.
      There are two types of parity: Even Parity and Odd Parity.
      Even Parity: The parity bit is selected so that the total number of 1s in the transmitted code, including the parity bit, becomes even.
      Example:
      Data = 10101
      Number of 1s = 3 (odd)
      Therefore, parity bit = 1
      Transmitted code = 101011
      Total number of 1s = 4 (even)
      Odd Parity: The parity bit is selected so that the total number of 1s in the transmitted code, including the parity bit, becomes odd.
      Example:
      Data = 10101
      Number of 1s = 3 (odd)
      Therefore, parity bit = 0
      Transmitted code = 101010
      Total number of 1s = 3 (odd)
      Error Detection: At the receiver side, a parity checker checks the number of 1s in the received code. If the required parity is not maintained, an error is detected.
      Example: Suppose even parity is used and the transmitted code is 101011. If one bit changes during transmission and the receiver gets 101001, the number of 1s becomes 3, which is odd. Therefore, the receiver detects an error.
      Important Points:
      • Parity can detect odd numbers of bit errors.
      • Parity cannot detect an even number of bit errors.
      • A parity bit can detect an error, but it cannot identify the exact location of the error.
      • Therefore, a simple parity bit cannot correct the error.

    • 3
      Error Detection Checksum
      Error Detection Technique : Checksum
      Data Link Layer
      What is Checksum?
      Checksum is an Error Detection Technique used in computer networks to detect whether data has been corrupted during transmission. At the sender side, the original data is divided into fixed-size blocks, the blocks are added together, and the One's Complement of the final sum is calculated as the checksum. The checksum is then appended to the original data and transmitted to the receiver.
      How Checksum Works:
      1. Divide the Data: Divide the original message into equal-sized blocks of n bits.
      2. Add the Blocks: Add all the blocks using binary addition.
      3. Wrap the Carry: If an extra carry is produced, add that carry back to the least significant bit of the result. This is called End-Around Carry.
      4. Find One's Complement: Invert every bit of the final sum. 0 becomes 1 and 1 becomes 0.
      5. Generate Checksum: The resulting value is the checksum.
      6. Append and Transmit: Append the checksum to the original data and send the complete information to the receiver.
      7. Receiver Verification: The receiver adds all received data blocks, including the checksum, using the same carry wrap-around method.
      8. Accept or Reject: If the final result contains all 1s, the data is considered error-free and accepted. Otherwise, an error is detected and the data is rejected.

    • 4
      Error Detection Checksum
      Example & Performance of Checksum
      Data Link Layer
      Example: Suppose the original data is:
      10011001111000100010010010000100
      Assume the data is divided into four 8-bit blocks:
      10011001111000100010010010000100
      Step 1 — Add the Blocks:
      10011001
11100010
00100100
10000100
-----------------
00100011
+     10
---------------
00100101
      The resulting 8-bit sum is: 00100101
      Step 2 — One's Complement(invert): 00100101→ 11011010 (It is Checksum)
      Step 3 — Transmitted Data:
      The sender appends the checksum to the original data: 1101101010011001111000100010010010000100
      Step 4 — Receiver Verification:
      The receiver adds all four data blocks and the received checksum. If the final result is: 11111111
      then the receiver assumes that no transmission error has been detected and accepts the data. otherwise rejected.

      Performance of Checksum
      • Simple and easy to implement.
      • Requires relatively little computational overhead.
      • Can detect many single-bit, multiple-bit, and burst errors.
      • Widely used in network and communication protocols.
      Limitation: Checksum cannot detect every possible error. If certain bit errors occur in such a way that their effects cancel each other during the addition, the final checksum may remain unchanged and the error can go undetected.

    • 5
      Error Detection CRC
      CRC and Step of CRC
      Data Link Layer
      CRC (Cyclic Redundancy Check) is an error-detection technique used in the Data Link Layer to detect whether data has been corrupted during transmission.
      Steps of CRC Process
      Choose a Generator Polynomial — Sender and receiver agree on a binary divisor called the Generator.
      Append Zeros — Add n-1 zeros to the original data, where n is the number of bits in the generator.
      Binary Division — Divide the resulting bit sequence by the generator using XOR division.
      Find Remainder — The remainder obtained from the division is called the CRC.
      Create Codeword — Append the CRC remainder to the original data.
      Transmit — Send the resulting data + CRC to the receiver.

      Receiver Checks — Receiver divides the received codeword by the same generator.
      Check Remainder:
      Remainder = 0 → No error detected.
      Remainder ≠ 0 → Error detected.

      Shortcut:
      Data → Append Zeros → XOR Division → CRC Remainder → Append CRC → Transmit → Divide → Check Remainder

    • 6
      Error Detection CRC
      Find the CRC for the data blocks 100100 with the divisor 1101?
      Data Link Layer

    • 7
      Error Detection CRC
      Receiver received data 100100001 and the divisor is 1101 , Check the received Data will be accepted or not.
      Data Link Layer

    • 8
      Error Detection CRC
      The message 11001001 is to be transmitted using CRC polynomial x3+1 to protect it from errors. Find the message that should be transmitted.
      Data Link Layer

Hamming Code Error Detection and Correction
1. Finding the Number of Redundant Bits (r)

Given Data (m): 1011 → Length of data, $m = 4$

Formula: 2r ≥ m + r + 1

For r = 1: 21 ≥ 4 + 1 + 1 ⇒ 2 ≥ 6 (False)
For r = 2: 22 ≥ 4 + 2 + 1 ⇒ 4 ≥ 7 (False)
For r = 3: 23 ≥ 4 + 3 + 1 ⇒ 8 ≥ 8 (True)

Selected r = 3. Total bits = $m + r = 4 + 3 = 7$ bits.

2. Bit Positions and Parity Bit Calculation (Even Parity)

Place parity bits at positions that are powers of 2 (1, 2, 4):

7654321
101R31R2R1

Binary Position Table

PositionR3 (4)R2 (2)R1 (1)
0000
1 (R1)001
2 (R2)010
3011
4 (R3)100
5101
6110
7111

Parity Bit Values

Bit Coverages:

  • R1 covers positions (1, 3, 5, 7)
  • R2 covers positions (2, 3, 6, 7)
  • R3 covers positions (4, 5, 6, 7)

Even Parity Calculation:

R1 → (R1, Bit3, Bit5, Bit7) → (R1, 1, 1, 1) ⇒ R1 = 1 (to make count of 1s even)

R2 → (R2, Bit3, Bit6, Bit7) → (R2, 1, 0, 1) ⇒ R2 = 0 (already even)

R3 → (R3, Bit5, Bit6, Bit7) → (R3, 1, 0, 1) ⇒ R3 = 0 (already even)

Final Transmitted Hamming Code:

7654321
1010101

Transmitted Data: 1010101

3. Error Detection on Received Data

Received Data: 1110101

7654321
1110101

Even Parity Check:

P1 (Positions 1, 3, 5, 7) → bits (1, 1, 1, 1) → Total 1s = 4 (Even) ⇒ 0

P2 (Positions 2, 3, 6, 7) → bits (0, 1, 1, 1) → Total 1s = 3 (Odd) ⇒ 1

P3 (Positions 4, 5, 6, 7) → bits (0, 1, 1, 1) → Total 1s = 3 (Odd) ⇒ 1

Error Location Calculation:

Syndrome Bits: (P3, P2, P1) = (1, 1, 0)2

Binary (110)2 = 1 × 22 + 1 × 21 + 0 × 20 = 4 + 2 + 0 = 6

Conclusion: Yes, there is an error! The error is located at Bit Position 6.

Correcting bit position 6 from 1 to 0 restores the original data: 1010101.

Topic Wise Question Bank
All Topics
    • ☆
      1
      Computer NetworkError Detection
      Explain the logic of a "Checksum". How is it used to verify data integrity during file transfer?
      Combined Bank, AP-22, 26 | Assistant Programmer

      Logic of a Checksum

      A checksum is a small, fixed-size value calculated from a block of data using a mathematical algorithm. It represents a summary of the data and is used to detect errors that may occur during data transmission or storage.

      How a Checksum Works

      1) The sender divides the data into fixed-size blocks (such as bytes or words).
      2) These blocks are added together (or processed using a checksum algorithm).
      3) The final result is the checksum value, which is sent along with the data.

      Verification During File Transfer

      • The receiver recalculates the checksum from the received data using the same algorithm.
      • The newly calculated checksum is compared with the checksum sent by the sender.
      • If both values match, the data is assumed to be intact.
      • If they do not match, it indicates that the data was corrupted during transmission.

      Purpose

      Checksums provide a simple and fast way to ensure data integrity, helping detect transmission errors in file transfers.


    • ☆
      2
      Data CommunicationError Detection
      CRC is a redundancy error technique used to determine the error. Suppose the original data is 11100 and divisor is 1001
      CB, AP, 23 | Assistant Programmer

      Solution:

      Step 1: Represent Data and Divisor in Polynomial Form

      Data (11100):

      x4 + x3 + x2

      Divisor (1001):

      x3 + 1

      Step 2: Append Zeros to the Original Data

      Since the divisor is 4 bits, we append 3 zeros to the original data (one less than the number of bits in the divisor). The new data is:

      Data after appending zeros: 11100000

      Step 3: Perform Binary Division

      Now we divide the modified data 11100000 by the divisor 1001.

      Division Process:


          11111                  ← Quotient
-----------------------------
11100000             ← Dividend (data with zeros)
1001                 ← Divisor
----------------------
1110000
1001
----------------
111000
1001
---------------
11100
1001
------------
1110
1001
------------
111

      Step 4: Determine the Transmitted Value

      The remainder 111 is the CRC code. To get the transmitted value, append the remainder to the original data:

      Original data: 11100
      Remainder: 111

      Transmitted Value: 11100111


    • ☆
      3
      Data CommunicationError Detection
      Explain parity method for error detection. Write down the bit strings of "Delta" using ASCII.
      BB, AME, 23 | AME/ANE/AE

      Parity Bit and Error Detection

      During data transmission, electrical noise may change the logic level of a signal, causing errors. To detect such errors, a parity bit (an extra bit 0 or 1) is added to the original data.

      Even Parity Method: The sender counts the number of 1s in the data. If the count is odd, the parity bit is set to 1 to make the total number of 1s even. If the count is already even, the parity bit is set to 0. The receiver again counts the number of 1s (including the parity bit). If the total is even, the data is assumed correct; otherwise, an error is detected.

      Example: Suppose the data 1101 is transmitted with parity bit 1. If due to noise the receiver gets 1111, the total number of 1s becomes odd. Hence, the receiver detects an error and may request retransmission.

      ASCII Code for “Delta”

      CharacterDecimal ASCII8-bit Binary
      D6801000100
      e10101100101
      l10801101100
      t11601110100
      a9701100001

      The complete binary bit stream for “Delta” is:
      01000100 01100101 01101100 01110100 01100001


  • Briefly explain Error Detection Technique in Data Link Layer . (Key Point)
  • Find the CRC for 1110010101 with the divisor x3+x2+1?
  • Suppose we want to transmit the message 11001001 and protect it from errors using the CRC polynomial x3+1. Use polynomial long division to determine the message that should be transmitted. Corrupt the left-most third bit of the transmitted message and show that the error is detected by the receiver using CRC technique.
  • Suppose the sender wants to transmit 4 frames of 8 bits each: 11001100, 10101010, 11110000, and 11000011. Find the Checksum,

    and also Verify if Receiver1 Received Data as :1100110010101010111100001100001111010011

    Is received data is error free or not? Explain your Answer.

PRACTICE MODE
Error Control
0 of 48 answered
Error Control 48 questions
Q1
Error Control

Which layer of the OSI model is mainly responsible for error control at the frame level?

Q2
Error Control

Which of the following is a type of transmission error?

Q3
Error Control

Which error occurs when only one bit of a data unit is changed?

Q4
Error Control

What is a burst error?

Q5
Error Control

If the first corrupted bit is at position 3 and the last corrupted bit is at position 10, what is the burst length?

Q6
Error Control

What is the main purpose of error detection?

Q7
Error Control

What are the extra bits added to data for error detection called?

Q8
Error Control

Which of the following is NOT an error-detection technique?

Q9
Error Control

What does VRC stand for?

Q10
Error Control

VRC is commonly known as what?

Q11
Error Control

What does a parity bit do?

Q12
Error Control

In even parity, the total number of 1s including the parity bit should be:

Q13
Error Control

In odd parity, the total number of 1s including the parity bit should be:

Q14
Error Control

Data = 10101. Using even parity, what is the parity bit?

Q15
Error Control

Data = 10101. Using odd parity, what is the parity bit?

Q16
Error Control

If even parity is used and the received code contains an odd number of 1s, what does the receiver conclude?

Q17
Error Control

Parity checking can reliably detect:

Q18
Error Control

Simple parity checking cannot detect:

Q19
Error Control

Can a simple parity bit identify the exact position of an error?

Q20
Error Control

Can a simple parity bit correct an error?

Q21
Error Control

What does LRC stand for?

Q22
Error Control

LRC organizes data mainly into:

Q23
Error Control

What is the main idea behind a checksum?

Q24
Error Control

In the checksum method, data is divided into:

Q25
Error Control

Which operation is commonly used to generate the checksum from the final sum?

Q26
Error Control

What is an end-around carry in checksum calculation?

Q27
Error Control

During receiver verification of a checksum, what result indicates error-free data?

Q28
Error Control

If the checksum verification result is not all 1s, the receiver should conclude that:

Q29
Error Control

Which error-detection technique uses binary polynomial division?

Q30
Error Control

What does CRC stand for?

Q31
Error Control

In CRC, what is the binary divisor called?

Q32
Error Control

If the generator has n bits, how many zeros are appended to the original data before CRC division?

Q33
Error Control

What operation is primarily used in CRC binary division?

Q34
Error Control

What is the remainder obtained from CRC division called?

Q35
Error Control

After calculating the CRC remainder, what is appended to the original data?

Q36
Error Control

At the receiver, the received codeword is divided by:

Q37
Error Control

In CRC, a remainder of zero at the receiver generally means:

Q38
Error Control

In CRC, a non-zero remainder at the receiver means:

Q39
Error Control

Find the CRC for data 100100 using divisor 1101. How many zeros should be appended before division?

Q40
Error Control

For data 100100 and divisor 1101, the data before CRC division becomes:

Q41
Error Control

Data 11100 is to be transmitted using CRC with divisor 1001. How many zeros are appended?

Q42
Error Control

For data 11100 and divisor 1001, the dividend used for CRC division is:

Q43
Error Control

For data 11100 with divisor 1001, if the CRC remainder is 111, what is the transmitted codeword?

Q44
Error Control

Which error-detection technique is particularly effective for detecting burst errors?

Q45
Error Control

What is the main difference between error detection and error correction?

Q46
Error Control

Which of the following is a method of error correction through retransmission?

Q47
Error Control

Which statement about redundancy is correct?

Q48
Error Control

Which sequence correctly represents the basic error-detection process?

Leave a Comment

WhatsApp Telegram Messenger