edited by
15,316 views
39 votes
39 votes

Data transmitted on a link uses the following $2D$ parity scheme for error detection:
Each sequence of $28$ bits is arranged in a $4\times 7$ matrix (rows $r_0$ through $r_3$, and columns $d_7$  through $d_1$) and is padded with a column $d_0$ and row $r_4$ of parity bits computed using the Even parity scheme. Each bit of column $d_0$ (respectively, row $r_4$) gives the parity of the corresponding row (respectively, column). These $40$ bits are transmitted over the data link.

$$\small \begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline
&\bf{d_7}&\bf{d_6}&\bf{d_5}&\bf{d_4}&\bf{d_3}&\bf{d_2}&\bf{d_1}&\bf{d_0}\\
\hline
\bf{r_0}&0&1&0&1&0&0&1&\bf{1}\\\hline
\bf{r_1}&1&1&0&0&1&1&1&\bf{0}\\\hline
\bf{r_2}&0&0&0&1&0&1&0&\bf{0}\\\hline
\bf{r_3}&0&1&1&0&1&0&1&\bf{0}\\\hline
\bf{r_4}&\bf{1}&\bf{1}&\bf{0}&\bf{0}&\bf{0}&\bf{1}&\bf{1}&\bf{0}\\
\hline\end{array}$$

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

  1. $1$
  2. $2$
  3. $3$
  4. $4$
edited by

8 Answers

3 votes
3 votes

There will be two possibilities...

CASE 1:

  d7 d6 d5 d4 d3 d2 d1 d0
r0   0   1   0   1   0   0   1   1
r1   1    1   0   0   1   1   1   0
r2   0   0      0    1   0   1   0   0
r3   0   1   1   0   1   0   1   0
r4   1   1   0   0   0   1   1   0

CASE 2:

  d7 d6 d5 d4 d3 d2 d1 d0
r0   0   1   0   1   0   0   1   1
r1   1    1   0   0   1   1   1   0
r2   0   0      0    1   0   1   0   0
r3   0   1   1   0   1   0   1   0
r4   1   1   0   0   0   1   1   0

so, in either cases minimum three 3-bits are corrupted.

edited by
2 votes
2 votes
It is 2D parity scheme and generally we check for 1D parity scheme, i.e., either row and column, so in 2D parity scheme we need to check both row as well as column.

And it is given this is even parity so, whichever column and row is not even parity there is corruption happend

So if you look carefully column d5 it is odd parity so there is one corruption similarly at d2 and in last d0.

So make it even 2D parity we need to change atleast 3 bits

So option C is correct.
1 votes
1 votes
Can anyone provide any source to read this topic as I'm not getting the question???
Answer:

Related questions

54 votes
54 votes
8 answers
2
Ishrat Jahan asked Oct 29, 2014
11,795 views
Host $X$ has IP address $192.168.1.97$ and is connected through two routers $R1$ and $R2$ to an­other host $Y$ with IP address $192.168.1.80$. Router $R1$ has IP address...