in Computer Networks edited by
10,785 views
34 votes
34 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$
in Computer Networks edited by
10.8k views

2 Comments

is this the  approach to solve this?

 i got too many combinations and choose minimum among them

or alternate way ?
2
2
Odd parity (error) is in 1 row and 3 columns.

So, we need to correct 3 * 1 = 3 bits.

Is this approach fine?
0
0

8 Answers

38 votes
38 votes
Best answer
$$\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&\boxed0&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}&\boxed{\bf{0}}&\bf{1}&\boxed{\bf{1}}\\
\hline\end{array}$$

Here, we need to change minimum $3$ bits, and by doing it we get correct parity column wise and row wise (Correction marked by boxed number)

C is answer
edited by

4 Comments

Check rowwise and column wise addition and ckeck which bit is giving error.

Nothing like minimum and maximum here. Just if addition of bit not giving correct result,change that bit
0
0
What does [r4][d0] represent in this scheme ? Is it checking d0 column or r4 row ?
0
0
22 votes
22 votes

OTHER WAY

2 Comments

is this way correct @Pragy Agarwal

0
0

 question is about error detection not correction so whatever way the table becomes valid is correct the minimum value is gonna stay 3

0
0
12 votes
12 votes
Answer: C

(r1, d5) should be 1.

(r4, d2) should be 0.

(r4, d0) should be 1.

3 Comments

it will be (r1,d0),(r4,d2),,(r4,d5) right?
4
4
(r4,d5) should be 1. Isn`t the answer should be option d?
0
0
i am not able understand the solution ,can anyone explain it in detalis
1
1
7 votes
7 votes

Here we have odd parity at row r1 and columns d5,d2 and d0.

Now since only 1 row shows error it can be (r1,d0) or (r1,d2) or (r1,d5)-----> any one of the three possible choices.

suppose it is (r1,d2).

Now still we are left with two errors at d0 and d5 but there is no error in any other row. It means error is at same row but two columns d0 and d5 and hence row parity could not detect it.

example- it could be r2,d0 and r2,d5 or r3,d0 and r3,d5 or any such choice.

so we can have minimum three bit error here.

Answer-  C

edited by

1 comment

Once you draw the 2D matrix and correspondingly lookout for even parity on rows and columns respectively, we can get the idea. For maximum too, is it 3 or the given data would be efficient?
0
0
Answer:

Related questions