ISRO CS 2023 Q.22: solution and answer

Official answer: CSource: ISRO's revised and final answer key of 16 February 2024

1. A single parity bit (odd or even) only checks whether the number of 1s has the required parity. Flipping two bits changes the count of 1s by an even amount, so the parity is unchanged and the error goes unnoticed.

2. So options (a) and (b) detect only an odd number of bit errors (single, triple, and so on). They cannot detect double errors.

3. An XOR checksum is the bitwise XOR of the data words, which is a longitudinal parity check. If two bits flip in the same bit position of two different words, the XOR is unchanged, so such double errors are missed. Option (d) is therefore not guaranteed to detect double errors.

4. A CRC treats the data as a polynomial and divides it by a generator $G(x)$. An error pattern $E(x)$ goes undetected only if $G(x)$ divides $E(x)$.

5. A double-bit error has the form $E(x)=x^i(x^k+1)$, where $k$ is the distance between the two flipped bits. Since $x^i$ shares no factor with $G(x)$ when $G(0)=1$, the error is missed only if $G(x)$ divides $x^k+1$. For a well-chosen generator, such as one with a primitive factor, the smallest such $k$ is large, so $G(x)$ divides $x^k+1$ only for $k$ at least that period. Any frame shorter than this period therefore has every double-bit error detected.

6. Generators used in practice, such as those of CRC-16 and CRC-32, are chosen this way, so for ordinary frame lengths every double-bit error is caught.

7. Hence the method used to detect double errors is the CRC, option (c).