The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+30 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
asked in Computer Networks by Boss (19.1k points)
edited by | 4.9k views
can any one have reference for this
How cn we sure which bits to be considered as parity and data bits??

And what method?

7 Answers

+66 votes
Best answer

Let $X_1, X_2$ and $X_3$ are data bits, and $C_1, C_2, C_3$ and $C_4$ are parity check bits.

Given transmitted codewords are
$$\begin{array}{|c|c|c|c|c|c|c|} \hline \textbf {$X _1$} & \textbf {$X_2$} &\text {$X_3$} & \textbf {$C_1$}& \textbf {$C_2$}& \textbf {$C_3$}& \textbf{$C_4$} \\\hline \text{0 }& \text{1} & \text{0} & \text{1} & \text{0} & \text{1}& \text{1} \\\hline \text{1 }& \text{0} & \text{0} & \text{1} & \text{1} & \text{0}& \text{1} \\\hline  \text{1 }& \text{1} & \text{1} & \text{0} & \text{0} & \text{0}& \text{1} \\\hline \end{array}$$
By inspection, we can find the rule for generating each of the parity bits –
$$\begin{array}{|c|c|c|} \hline \textbf {$X _1$} & \textbf {$X_2$} &\text {$X_3$} & \textbf {$X_1$} \oplus  \textbf {$X_2$}&\textbf {$X_1$} \oplus  \textbf {$X_3$}& \textbf {$X_2$} \oplus  \textbf {$X_3$}& \textbf {$X_1$} \oplus  \textbf {$X_2$} \oplus \textbf{$X_3$} \\\hline \color{blue}{\text{0}}& \color{blue}{\text{1}} &\color{blue}{\text{0}} & \text{1} & \text{0} & \text{1}& \text{1} \\\hline 
\color{blue}{\text{1}} & \color{blue}{\text{0}} &\color{blue}{\text{0}} & \text{1} & \text{1} & \text{0}& \text{1} \\\hline  
\color{blue}{\text{1}} & \color{blue}{\text{1}} & \color{blue}{\text{1}} & \text{0} & \text{0} & \text{0}& \text{1} \\\hline \end{array}$$

Now we can not only eliminate options, we can also find the set of all eight code words using $X_1, X_2$ and $X_3$.

$$\begin{array}{|c|c|c|} \hline \textbf {$X _1$} & \textbf {$X_2$} &\text {$X_3$} & \textbf {$X_1$} \oplus  \textbf {$X_2$}&\textbf {$X_1$} \oplus  \textbf {$X_3$}& \textbf {$X_2$} \oplus  \textbf {$X_3$}& \textbf {$X_1$} \oplus  \textbf {$X_2$} \oplus \textbf{$X_3$} \\\hline \text{0 }& \text{0} & \text{0}  \\\hline \text{0 }& \text{0} & \text{1}  \\\hline\text{0 }& \text{1} & \text{0} & \text{1} & \text{0} & \text{1}& \text{1} \\\hline  \text{0 }& \text{1} & \text{1}  \\\hline \text{1 }& \text{0} & \text{0} & \text{1} & \text{1} & \text{0}& \text{1} \\\hline \text{1 }& \text{0} & \text{1}   \\\hline  \text{1 }& \text{1} & \text{0}   \\\hline  \text{1 }& \text{1} & \text{1} & \text{0} & \text{0} & \text{0}& \text{1} \\\hline \end{array}$$

We can fill all remaining entries above :)

Now I am directly writing answer, Option A is correct choice !

answered by Boss (17.4k points)
edited by
Thanks Great answer .
Welcome :)
Wonderful explanation

Is the rule for generating each of the parity bits same for all ????

Why do we necessarily assume that 4 bits from LSB are parity bits? It can also be in some other format, correct?
How will I be able to think this logic during the exam?
@sachin mittal sir

sir i have a small doubt that what happen if we use some other rules like C4= x1 or x2 then given codeword satisfy this rules but option A is not satisfying
Perfect Answer
@sachin sir aapnay flat kr diya
is this the only possible approach??

@vaibhav singh 3 sir we can do it by calculating hamming distance between the codeword 

+36 votes

The simplest way to solve this is to use XOR property of codewords which says that XOR of two codewords is itself a codeword.
Upon XORing 1st and 3rd codeword we get another codeword 1011010, which is III .
And on XORing this new generated codeword with 2nd codeword given we get 0010111, which is I.

Hence Answer = A

answered by Active (1.5k points)
but this property is only used for linear codes right?

We can not just apply XOR, bcoz this is not linear block code.

There has to some rule for generating each of the parity checks.

Similar to question 2 here or question 1 here

+27 votes

I had tried a new method hope this is less intuitive and more calculative.

In all valid codewords, the hamming distance between any two valid codewords remains constant.

Example say if we have a set of 16 valid codewords, then between any two valid codewords in this set of 16, the hamming distance would be same.

The given codewords are

0101011( Let's Say A), 1001101 (let's say B) and 1110001 ( say C)

For finding the hamming distance between any two codewords, perform XOR operation of both and find the number of 1's present in the result.
 A⊕B = 1100110 (Hamming distance is 4)

B⊕C=0111100 (Hamming distance is 4)

A⊕C=1011010(Hamming distance is 4)

So, in our given code system, all codewords are at a hamming distance of 4. 

Any new valid codeword must also have a hamming distance of 4 from these 3(A, B and C) valid codewords.

Now considering each option one by one

(I) 0010111 (Let's call it D)

A⊕ D=111100 (Hamming distance =4)

B⊕D=1011010 (Hamming distance =4)

C⊕D = 1100110 (Hamming distance =4)

This new codeword (D) has same hamming distance with the present codewords. Hence, this is a valid codeword.

(II)0110110 (Assume is as E)

  A⊕E=0011101 (Hamming distance = 4)

B⊕E = 1111011 (Hamming distance = 6)

Now, Stop here as this codeword E has a hamming distance of 6 with codeword B. But it should have same hamming distance with all the valid codewords.

So, Choice (II) is surely Invalid.

(III) 1011010 (Let's call it F)

A⊕F = 1110001 (Hamming distance =4)

B⊕F= 0010111 (Hamming distance =4)

C⊕F=0101011 (Hamming distance =4)

Yes, this is a valid codeword.

(IV)0111010 (Let's call it G)

A⊕G=0010011 (Hamming distance =3)

This is an invalid codeword.

So, clearly, our answer is option A

answered by Boss (25.5k points)
thanks a lot ! ... gr8 explanation
Is hamming distance is present in syllabus or out of syllabus?
I don't know but you should know this concept because it helps in solving other type of problems too
Thanks sir
This is the best way to answer these questions. If we check the distance between 1 & 2, 2 & 3, 1 ,& 3 we get hamming distance as 4. Therefore all code words at distance 4 from these codes will be valid and with distance less than this will be invalid.

@Ayush. Nice answer. Thank you :) . There are typos in $A\oplus D$ of (I) and $A\oplus G$ of (IV).  Can you please provide any good reference for the statement :-

"In all valid codewords, the hamming distance between any two valid codewords remains constant."

@ankitgupta-See it's like this. All valid codewords are separated by suppose 'd' hamming distance.From a codeword $C_1$ you can get another codeword $C_2$ if you change 'd' bits in $C_1$. Therefore any codewords obtained by changing upto d-1 bits in any codewords can be detected as invalid codewords and the reason why you must have read

"To detect error minimum hamming distance='d+1' "

However, if in a codeword you change "d" bits, error won't be detected, but I think in this question, all invalid codewords are indeed at a hamming distance less than d.
@Ayush. Thank you :)

@Ayush Upadhyaya in ii hamming distance is 4 or 6 which is greater than min how you eliminate this option?

how can you conclude hamming distance should be same?

+8 votes

This is nice Question. I'm giving probable answer, which seems best to me Though do comment if you feel there is any mistake.

010 1 0 1 1 => Here 1 is Even parity for 01 (starting 2 char of 010)

                         Here 0  is Even parity for 010 (First & last characters of 010)

                         Here 1 is Even parity for 010 (Last 2 character of 010)

Finally last 1 is Even parity for total string 010 1 0 1 => 1.

Same way you can do for 1001101 and 1110001.

If you try for using similar test for

I. 0010111             II. 0110110         III. 1011010             IV. 0111010

Then I & III pass in test. So answer is A .

answered by Boss (43.6k points)
please  explain in simple manner
i also answered with same idea :)
I am not getting this pls explain
0 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



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.
answered by (207 points)
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!

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.

answered by (83 points)
edited by
–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
answered by Active (2.6k points)
Can you please explain how did you get 0010111 as the 4th string of the set ....?
please explain it.
for 1 and 3rd the hamming distance is 4 for rest it is less than that and hence only A
someone plz explain elaborately

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
49,447 questions
53,651 answers
70,912 users