Show that a binary perfect linear $[n,k,d]$ code is generated by its words of minimal weight.

Question

Question

Show that a binary perfect linear $[n,k,d]$ code is generated by its words of minimal weight.

What I have so far

We can try to solve this by induction on the weight of the words in the code.

Induction base: if a word has weight $d$, then it generates itself and has minimal weight.

Induction step: now suppose that we know that for every word of weight $l>d$ we know that it is generated by words of minimal weight. We now look at the words of weight $l+1$.

This is the hardest step of the proof and I'm stuck here. Any suggestions?

Answer 1

Ok, so $d=2t+1$.

A plan of attack for the inductive step. Justify everything.

1. Let $x$ be a codeword of weight $\ell+1$. Let $y$ be a vector formed by selecting $t+1$ of the $1$s in $x$, and setting the rest of the components to zero. In other words, $y$ has weight $t+1$, and $d(y,x)=\ell-t$.
2. Perfectness implies that there exists a codeword $z$ such that $d(y,z)\le t$. Then $z$ must have the minimum weight $2t+1$.
3. It follows that the codeword $x-z$ has weight $\le \ell$. The induction step follows from this.