0
$\begingroup$

Let $C$ be the binary linear code with the following generator matrix

$G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix}$

The support of a codeword is the set of coordinate positions in which the code word has nonzero entries. Let $w$ $\in C$ be a code word of weight $4$. Show that there is no code word of weight $3$ in $C$ whose support is a subset of the support of $w$.

I think I have worked out that the codewords of weight $4$ in $C$ are: $\{(1001011),(0010111),(0111001),(0101110),(1100101),(1110010),(1011100)\}$ so does this mean that the support is $\{(1,4,6,7),(3,5,6,7),(2,3,4,7)$ and so on..$\}$? Then the codewords of weight $3$ are $\{(1101000),(0110100),(0011010),(0001101),(1000110),(1010001),(010001)\}$ ? with support of $\{(1,2,4),(2,3,5),(3,4,5)$ and so on..$\}$?

I'm not sure if this is right so far? But this is as far as I can get and do not know what to do next to show that there is no code word of weight $3$ in $C$ whose support is a subset of the support of $w$.

$\endgroup$
1
$\begingroup$

If a codeword of weight 3 existed whose support was a subset of a codeword of weight 4, then you must have a codeword of weight 1 (since the difference of codewords is also a code word).

A codeword of weight 1 has one 1 and the rest zeros. Now, can you show that these don't exist?

$\endgroup$
  • $\begingroup$ Can I say that a codeword of weight 1 doesn't exist because $C$ has a minimum distance of 3? $\endgroup$ – harry55 Feb 26 '17 at 21:15
  • $\begingroup$ Also I can't quite get my head around why if a codeword of weight 3 existed whose support was a subset of a codeword of weight 4, then you must have a codeword of weight 1 I know you say the difference of codewords is also a code word but I can't see the link between this and supports/subsets $\endgroup$ – harry55 Feb 26 '17 at 22:24
  • $\begingroup$ Your code is a linear code (so sums/differences of codewords are also codewords). Take the difference of a codeword of weight 4 and the supposed codeword of weight 3. The codeword of weight 4 has ones in 4 positions, and the supposed codeword of weight 3 has ones in 3 of the 4 positions. So, when you do codeword of weight 4 - codeword of weight 3, you get a codeword which is 1 in the support of weight 4 codeword but not in support of weight 3 codeword and zero otherwise. so it has weight 1. $\endgroup$ – Batman Feb 26 '17 at 22:47
  • $\begingroup$ If you show that C has minimum distance 3, then you're done by combining it with what I've stated: adding/subtracting the supposed codeword of weight 3 with the codeword of weight 4 would give you a weight 1 codeword. The existence of this contradicts distance 3. $\endgroup$ – Batman Feb 26 '17 at 22:48
  • $\begingroup$ Sorry I'm still finding it quite hard to visualise. As an example when I do a weight 4 codeword - a weight 3 codeword, I get 1001011-1101000. Which gives 0100011, weight 3 not weight 1? Could you give an example so I can see how you get weight 1? $\endgroup$ – harry55 Feb 26 '17 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.