edited by
18,643 views
47 votes
47 votes

Consider a parity check code with three data bits and four parity check bits. Three of the Code Words are $0101011, 1001101$ and $1110001.$ Which of the following are also code words?

  1. $0010111$
  2. $0110110$
  3. $1011010$
  4. $0111010$
  1. I and III
  2. I, II and III
  3. II and IV
  4. I, II, III and IV
edited by

7 Answers

1 votes
1 votes
Answer is option A.

 

Since in question it has given 3 code words so clearly it's indicating there is some pattern there so,

When you clearly see

P1: 0101011

P2:1001101

P3:1110001

So when you'll calculate hamming distance (no. Of unmatched bits) between p1 and p2 it come out to be 4. So does in p2 and p3 and p1 and p3 also.

Similar in option 1 and 3 there hamming distance is also 4. So option A is correct.
0 votes
0 votes

Here is another approach to look at the question.

3 data bits and 4 parity check bits. Isn't that overkill for error detection? We can pretty much send the same 3 bits again with an additional parity bit to establish which 3 data bits had an error.

So could this be a self-correcting hamming code?

For a self correcting hamming code, with 3 data bits (up to 4 data bits), we need an additional 3 parity bits. That still comes out to be 3+3=6. However, the problem with hamming codes is that they cannot tell if a double-bit error caused the modification or a single bit error. It assumes that it was a single bit error and the auto-correct mechanism gives us wrong data (in case more bits were modified). Adding 1 extra parity bit solves that to some extent. 3+3+1 = 7! https://en.wikipedia.org/wiki/Hamming_code
 

Just casually looking at the last bits of the codewords will tell you that they are even parity bits. Let us call them [Pa] as they are a single additional parity bit at the end.
[D3], [D5] and [D6] should be data bits. Remaining:  [P1],[P2] and [P4] should be the parity bits used for correction.


The codewords should therefore look like: [P1][P2][D3][P4][D5][D6][Pa].
The hamming code part should only be [P1][P2][D3][P4][D5][D6]

For even parities (which seems to be the norm here): 
[P1] = [D3]⊕[D5]  (D7 does not exist!)
[P2] = [D3]⊕[D6]  (D7 does not exist!)
[P4] = [D5]⊕[D6]  (D7 does not exist!)

This holds for all the codewords provided. And it holds for I and III only. The correct answer should therefore be A.

edited by
–3 votes
–3 votes
We need to test first for fourth string of this set..We find it as “0010111”
Now the set has been of size 4,,so now our search must go on with comparing these 4 strings with all other strings. Next string, which satisfies this constraint is “1011010”.

hence A
Answer:

Related questions