Dark Mode

14,293 views

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?

- $0010111$
- $0110110$
- $1011010$
- $0111010$

- I and III
- I, II and III
- II and IV
- I, II, III and IV

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 !

1

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

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

2

http://www.seas.upenn.edu/~tcom501/Other/t501_midterm_spring00.pdf link is not working.. Can you provide working link..

0

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 .