Finding cosets and coset leaders of [6,3] code

Question

I was given a generator matrix:

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

From there I was able to find that the code C is:

$$ C = \{\{0 0 0 0 0 0\}, \{1 0 0 1 1 1\}, \{0 1 0 1 0 1\}, \{0 0 1 0 1 1\}, \{1 1 0 0 1 0\}, \{1 0 1 1 0 0\}, \{0 1 1 1 1 0\}, \{1 1 1 0 0 0\}\} $$

I am trying to find the cosets and coset leaders. I know that the following will be coset leaders:

$$ \{000000\}, \{000001\}, \{000010\}, \{000100\}, \{001000\}, \{010000\}, \{100000\} $$

However, based on the [n, k] code, I know I should have 8 coset leaders. How do I go about finding the final one that is missing? Is there an algorithm for it?

Answer 1

After the automatic start of listing all the vectors of weight $<d_{min}/2$ this task often involves a bit of case-by-case analysis. I'm not sure if there is an efficient general algorithm. Just go about it systematically starting from the low weight end. For my research I once needed to classify and enumerate the coset leaders of the Reed-Muller code $R(5,2)$, and I recall it being a fun exercise.

The next possible weight of a coset leader is two. There are $\binom62=15$ vectors of weight two. Let's denote by $x_i$ the vector with five zeros and a single $1$ at position $i$, $i=1,2,\ldots,6$. No vector of weight two is in the coset $C$, so we check those in $x_i+C, i=1,\ldots,6$. We get them by adding a codeword of weight three to $x_i$, so we go through the four weight three codewords $010101$, $001011$, $110010$, $101100$ ($111000$ is not a codeword, the sum of all three rows of the generator matrix is $111001$).

• $x_1+C$ has $010010$ and $001100$,
• $x_2+C$ has $000101$ and $100010$,
• $x_3+C$ has $000011$ and $100100$,
• $x_4+C$ has $010001$ and $101000$,
• $x_5+C$ has $001001$ and $110000$,
• $x_6+C$ has $010100$ and $001010$.

We see that the list is missing the weight two vectors $$y_1=100001,y_2=011000,y_3=000110.$$ They must thus all be the leaders of the remaining coset. In particular, they must belong to the same coset. Indeed, $$ \begin{aligned} y_1+y_2&=111001\in C\quad \text{(the correction in my comment)}\\ y_1+y_3&=100111\in C \end{aligned} $$ proving that $y_2,y_3\in y_1+C$.

Whenever the weight of a coset $\ge d_{min}/2$ we cannot expect a coset to have a unique leader. This remaining coset has three leaders.

---

An afterthought. This code is gotten by shortening a perfect $[7,4,3]$ binary Hamming code $C^+$ with generator matrix $$ G^+ =\begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{bmatrix}$$ in the last bit position. Because $C^+$ is a perfect single-error-correcting code, the entire space $\{0,1\}^7$ is covered by $C^+$ itself together with the seven weight one cosets $x_i+C^+, i=1,2,\ldots,7$. The three weight two words that are leaders of the remaining coset of $C$ are gotten by shortening the seventh bit from $x+x_7$ where $x$ ranges over those weight three words of $C^+$ that have the seventh bit on.