GATE IT 2008 | Question: 66

Question

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$?

• A. $1$
• B. $2$
• C. $3$
• D. $4$

Comments

Gate 2008 pyq CN | Data transmitted on a link uses the following 2D parity scheme for error detecti

---

$\textbf{Parity-based error detection has a minimum Hamming distance of 2, which means:}$

• $\text{Single bit-flip errors can be detected.}$
• $\text{But, 0 bit-flips can be corrected.}$
   

 

• $\text{However, this question is technically asking: in how many MINIMUM bit-flips can we make the received data a valid codeword?}$

 

• $\textbf{There can be multiple ways to flip bits in order to satisfy the even parity condition.}$
• $\text{BUT, we cannot determine which valid codeword was originally transmitted, since the errors cannot be uniquely corrected.}$

 

• $\text{Therefore, in real life, it is possible that more than 3 bits actually got flipped.}$
• $\text{However, the number of flipped bits must be odd, because each bit flip toggles the parity (even/odd).}$
   

---

i hope this will help link 

Answer 1

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

Comments

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

---

R1d5 R1d1 R1do will also do the work.

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

---

Please provide material to read about this topic. I am unabe to understand this question

---

for more info about 2D parity check

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

---

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??

---

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

---

@Prashant. @Arjun @VIDYADHAR SHELKE 1 @vupadhayayx86 @kavya kamish upadhya @mehul vaidya @Sherrinford @Golam Murtuza @sushmita @Arvnd @scholaraniket @srestha

Why Option C (3) is Correct? We need to find minimum possible value of corrupted bits (n), which is 1. Moreover, 3 bit errors can go undetected. Hence, we can detect upto three bit errors that can occur anywhere in the table. 

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

---

@ayushsomani 

Can you make the matrix correct by changing only $1$ bit? 

In order to fix the matrix, minimum $3$ corrections are required, so minimum no. of corrupted bits are $3$. 

And the undetected part you mentioned from the link, doesn't mean that every 3 bit error will go undetected. It says it can go undetected, which is not the case in our question. 

 

right?

 

---

@ayushsomani  "We need to find minimum possible value of corrupted bits (n)," means ....................it is required to change minimum 3 bits . so that you will get correct answer .    

---

@toxicdesire @VIDYADHAR SHELKE 1

Got it. Thanks. 

But, still we cannot detect more than 3 bits in any case. Correct me, if i am wrong. Using Minimum is looking horror to me. Such a pathetic use of Language to confuse easily. 

---

@srestha ma'am am i correct?

As par my knowledge  2D Matrix can detect "Maximum = MIn(row,column)" errors ....because here is clue that 2 bits should not be change in same row or column  and correct 1 bits only.....

---

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

---

The archive of link provided by @kavya and @ayush:

https://web.archive.org/web/20180704111824/http://faculty.ycp.edu/~dhovemey/fall2005/cs375/lecture/11-16-2005.html

---

What does [r4][d0] represent in this scheme ? Is it checking d0 column or r4 row ?

---

Can someone explain how he got to know that he need to change (r1,d5), (r4, d2), (r4,d0)? I am not able to understand this pinned short answer.

---

find where intersection lies..

---

in r1 d5 it should be 1 not zero in the image you havent corrected that please edit the answer @GO Classes

---

we can change

(r1, d2) to 0

(r4, d5) to 1
(r4, d0) to 1

right???

or am i missing out anything???
 

Answer 2

OTHER WAY

Comments

is this way correct @Pragy Agarwal

---

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

Answer 3

Answer: C

(r1, d5) should be 1.

(r4, d2) should be 0.

(r4, d0) should be 1.

Comments

it will be (r1,d0),(r4,d2),,(r4,d5) right?

---

(r4,d5) should be 1. Isn`t the answer should be option d?

---

i am not able understand the solution ,can anyone explain it in detalis

---

It's very easy once you read this, 

They had mentioned even bit parity, means no. of 1's should be even 

Check each row and each column, 

U will find that, no. of 1's are odd in 

            r1, d0, d2, d5  .............means there is error here & we need to fix it

 

Method 1 :  Try different combinations of turning 0 to 1 and 1 to 0

                   to make even no. of 1's in each column and each row 

Because of it, u may find here different answers.  And among all, find Minimum.

 

Method 2 : After spending some time, the trick I got to know is, 

There is only one condition that need to be satified for using this method, 

Condition :-  All the errors in either row or column must be of same bit,

              means  All must be  Odd  or   All must be Even   but not both.

 

Example, here all  r1, d0, d2, d5  are Odd, means no. of 1's is odd

Hence, we can use this method,

Now,  Trick is 

        Minimum no. of errors  =    max (row, column)  

                                                =    max ( 1, 3 )   ...........r0 is row, d0, d2, d5  are columns

                                                =    3

Answer 4

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

Comments

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?

Answer 5

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.

Answer 6

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.