in Computer Networks edited by
14,293 views
46 votes
46 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
in Computer Networks edited by
14.3k views

3 Comments

can any one have reference for this
1
1
How cn we sure which bits to be considered as parity and data bits??

And what method?
11
11
0
0

7 Answers

92 votes
92 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 !

edited by

4 Comments

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

2
2
how do we know that least significant 4 bits are for parity and rest for data? What if they are jumbled up?
1
1
Made Easy copied this answer in their Previous Year Book or it may be other way round
0
0
110 votes
110 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

4 Comments

90+ upvotes v 80+ upvotes and this is not best answer. Update your Algorithms gateoverflow
0
0
Great explaination Ayush Bhaiya :)
0
0
Thank you sir .
0
0
45 votes
45 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
 

4 Comments

but this property is only used for linear codes right?
2
2

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

2
2
0
0
edited by
@Sachin Mittal 1 they have given in question parity check code. Parity check codes are also one type of linear block codes right?
0
0
8 votes
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 .

4 Comments

please  explain in simple manner
0
0
edited by
i also answered with same idea :)
1
1
I am not getting this pls explain
0
0

please  explain in simple way 

@Akash Kanase

0
0
Answer:

Related questions