i got too many combinations and choose minimum among them

or alternate way ?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+20 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 minimum possible value of $n$?

- $1$
- $2$
- $3$
- $4$

+29 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

&\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

0

R1d5 R1d1 R1do will also do the work.

Three corrupted columns and one corrupted row will be handled by this

Three corrupted columns and one corrupted row will be handled by this

0

for more info about 2D parity check

http://faculty.ycp.edu/~dhovemey/fall2005/cs375/lecture/11-16-2005.html

0

What if we just correct r1d5 I think everthever will fall in to place. All rows and columns will give correct parity won't they??

0

@vupadhayayx86 ....bro you have to again check table after r1d5 correcting . and you will get again corrupted bit.

better follow rule

1. First find all corrupted bit column wise, row wise and

2. check first Row wise and column wise from corrupted bit entry then correct it. (bcz of this condition you can correct 2 bit using 1 bit(entry only )

3. at last check again is there any corrupted bit.

+11 votes

+3 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**

+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.

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.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,937 questions

52,337 answers

182,398 comments

67,820 users