Data transmitted on a link uses the following 2D parity scheme for error…

2008

Data transmitted on a link uses the following 2D parity scheme for error detection:
Each sequence of 28 bits is arranged in a 4×7 matrix (rows r0 through r3, and columns d7 through d1) and is padded with a column d0 and row r4 of parity bits computed using the Even parity scheme. Each bit of column d0 (respectively, row r4) gives the parity of the corresponding row (respectively, column). These 40 bits are transmitted over the data link.

image.png



The table shows data received by a receiver and has n corrupted bits. What is the mini­mum possible value of n?

Answer: C. 3Answer: 3 corrupted bits. Method to determine the minimum number of corrupted bits: Compute row parity mismatches: For each row, XOR the seven data bits and…

  1. A.

    1

  2. B.

    2

  3. C.

    3

  4. D.

    4

Attempted by 149 students.

Show answer & explanation

Correct answer: C

Answer: 3 corrupted bits.

Method to determine the minimum number of corrupted bits:

  • Compute row parity mismatches: For each row, XOR the seven data bits and compare with the transmitted row parity bit. Count how many rows do not match. From the received table this count is 3.

  • Compute column parity mismatches: For each column, XOR the four data bits and compare with the transmitted column parity bit. Count how many columns do not match. From the received table this count is 3.

  • Key insight: Flipping a single data bit toggles the parity of exactly one row and exactly one column. To correct k mismatched rows and l mismatched columns you need at least max(k, l) bit flips, because each flip fixes at most one row mismatch and one column mismatch.

  • Apply to this case: k = 3 mismatched rows and l = 3 mismatched columns, so the minimum number of flips required is max(3, 3) = 3. When k = l you can choose the three flipped bits at the three intersections of the mismatched rows and columns to fix all mismatches simultaneously.

Therefore the minimum possible value of n (number of corrupted bits) is 3.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…