Why the minimum distance of a binary code of length $\geq 3$ is at least 3

Question

Let C a binary code of length $n \geq 3$ with generator polynomial $g(x) \neq 1$, where n is the smallest positive integer for which $g(x)~|~x^n + 1$. Show that C has a minimum distance at least 3.

---

I'm using the fact that a minimum distance of 3 is equivalent to saying the weight of $v + w$ is at least 3, with $v$ and $w$ any element of C with $v \neq w$.

I've considered a proof by contradiction, where I showed that it could not be true for minimum distance 0. I got stuck at showing it could not be true for minimum distance 1 and 2. For 1, I got to the point where I wanted to use that $\exists~i$ between 0 and n such that $v + w = x^i$.

I thought of using that $\exists~h, j \in R_n := \mathbb{F_2}[x]/(x^n + 1)$ such that $$v + w = h \cdot g + j \cdot g = g \cdot (h + j)$$

and $g~|~x^n + 1.$

The preknowlegde that I have is from one basic course in coding. Hamming codes were covered, as well as MacWilliams identity. Is there anyone who could help form a connection between my ideas and the statement to be shown?

Answer 1

The codewords are polynomials of the form $c(x)=g(x)m(x)$ of degree $<n$. Here $m(x)\in\Bbb{F}_2[x]$ can be any polynomial as long as $c(x)$ satisfies the degree constraint.

Hint:

• If $c(x)$ has weight one, then $c(x)=x^a$ for some $a, 0\le a<n$.
• If $c(x)$ has weight two, then $c(x)=x^a+x^b$ for some $a,b$ with $0\le a<b<n$.

Is either of these possible? Keep in mind that factorization of polynomials over a field is unique.