Error Detection & Correction - Free MCQ Practice Test with solutions, GATE

CRC uses more math like multiplication and binary division.

Cyclic redundancy check is more efficient than parity check.

CRC is more powerful and it can detect various kind of errors like 2 bit errors.

Error can be detected and corrected by adding additional information that is by adding redundancy bits.

The correct answer is "option b".
CONCEPT:
CRC stands for Cyclic Redundancy Check, is an error-detecting code used to detect errors in the frame received.
CRC is used to detect errors in the Data link layer.
Key Points
Steps to perform CRC on the sender side:
String of n 0’s is appended to the data unit to be transmitted.
Where, n -> number of bits in CRC divisor - 1
Binary division is performed of data unit with the CRC divisor.
The remainder obtained after division is called CRC.
Append CRC at last of data units.
CALCULATION:
STEP1: 
No. of bits in divisor - 4 bits, append 3 0's to data bits
Data bits after appending 0's - 100111001000
STEP2:
Binary division of 100111001000 with 1011:
                                           _____________

                                1011  ) 100111001000  ( 101000001

                                     ⊕   1011

                                          ----------

                                              01011

                                          ⊕   1011

                                           -----------------

                                                       1000

                                                  ⊕  1011

                                                     ------------

                                                          011

STEP 3:
Append CRC 011 at last of data unit → 100111001011.
Hence, the correct answer is "option b".

Parity check

• It is a simple way to add redundancy bits to the packets such that the total number of 1's is even (or odd).
• Single parity check: a single bit is appended to the end of each frame, the bit is 1 if the data portion of the frame has an odd number of 1's. Otherwise, it is 0.

Checksum

• This is a block code method where a checksum is created based on the data values in the data blocks to be transmitted using some algorithm and appended to the data.
• When the receiver gets this data, a new checksum is calculated and compared with the existing checksum. A non-match indicates an error.

Cyclic redundancy check (CRC) 

• It is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data.
• Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents

Therefore All of the Option is the correct answer

Error detection is accomplished by using a Frame Check Sequence (FCS) method like Parity, Checksum Calculation or Cyclic Redundancy Check (CRC).
∴ Hence the correct answer is the Cyclic Redundancy Code.

A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents.
Example
Polynomial is:  x⁵ + x⁴ + x² +1
A polynomial higher degree is 5, so append 5 0’s to the message bits.
Message: 1010001101 00000
Divisor polynomial in bits = 110101

Concept:
Properties of Linear Block Codes (LBC)
1) The sum of two codewords is a code word
2) The sum of a code word with itself is the zero codewords.
3) The sum of any codeword and an error vector corresponding to one error is not a code word
Analysis:
By property 1
C₁ = 0011
C₂ = 0101
C₃ = 1010
C₁ ⊕ C₂ = [0011] ⊕ [0101] = 0110
C₁ ⊕ C₃ = [0011] ⊕ [1010] = 1001
C₂ ⊕ C₃ = [0101] ⊕ [1010] = 1111
so option (D) is not a code word of LBC.

Backward error correction

• It also is known as Automatic Repeat ReQuest, ARQ.
• It uses feedback from the receiver to the transmitter: the receiver signals to the transmitter whether a block of data was received correctly or not.
• Backward Error Correction algorithms include: Parity bits, CRC (Cyclic Redundancy Check) & LRC (Longitudinal Redundancy Check)
• In Data Link Control, backward error correction is used for error correction.

Parity check

• It is a simple way to add redundancy bits to the packets such that the total number of 1's is even (or odd).
• Single parity check: a single bit is appended to the end of each frame, the bit is 1 if the data portion of the frame has odd number of 1's. Otherwise, it is 0.

Checksum

• This is a block code method where a checksum is created based on the data values in the data blocks to be transmitted using some algorithm and appended to the data.
• When the receiver gets this data, a new checksum is calculated and compared with the existing checksum. A non-match indicates an error.

Cyclic redundancy check (CRC) 

• It is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data.
• Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents.