The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
2.9k views

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$
asked in Computer Networks by Boss (19.1k points)
edited by | 2.9k views
+2
is this the  approach to solve this?

 i got too many combinations and choose minimum among them

or alternate way ?

7 Answers

+26 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
answered by Veteran (61k points)
edited by
+2

@Prashant but it will be (r1,d0),(r4,d2),(r4,d5) 

0
R1d5 R1d1 R1do will also do the work.

Three corrupted columns and one corrupted row will be handled by this
0
Please provide material to read about this topic. I am unabe to understand this question
+9 votes
Answer: C

(r1, d5) should be 1.

(r4, d2) should be 0.

(r4, d0) should be 1.
answered by Boss (34k points)
+3
it will be (r1,d0),(r4,d2),,(r4,d5) right?
0
(r4,d5) should be 1. Isn`t the answer should be option d?
+3 votes

OTHER WAY

answered by Active (2.2k points)
0 votes
option c is correct ,toggle these ones

1.r0-d5

2.r0-d0

3.r1-d2
answered by (275 points)
0 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

answered by Boss (14.7k points)
edited by
–1 vote
3 option c
answered by Active (3.3k points)
–2 votes
here the parity bits can also be corrupted, so they asked minimun so when we correct (r0,d0) to 0 and (r0,d5) to 1 then the minimun errors i found are 2, so the answer will be B, correct me if i am wrong
answered by Boss (11k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,065 questions
47,661 answers
147,308 comments
62,381 users