Significance of dmin; (7,4) cyclic code for 1101 with g(x) = 1 + x + x²

Significance of $d_{min}$

The minimum Hamming distance $d_{min}$ is the smallest number of positions in which any two codewords differ (for a linear code, the smallest non-zero codeword weight). It fixes the power of the code:

• Detects up to $s$ errors if $d_{min}\ge s+1$.
• Corrects up to $t$ errors if $d_{min}\ge 2t+1$, i.e. $t=\lfloor(d_{min}-1)/2\rfloor$.

For a (7,4) Hamming code $d_{min}=3$: detects 2, corrects 1 error.

Note on the generator polynomial

A generator for a (7,4) cyclic code must have degree $n-k=3$ and divide $x^7+1=(1+x)(1+x+x^3)(1+x^2+x^3)$. The printed $g(x)=1+x+x^2$ has degree 2 and does not divide $x^7+1$, so it is taken as a misprint of the standard $g(x)=1+x+x^3$.

Message $(m_0m_1m_2m_3)=1101$, ascending powers:

$$m(x)=1+x+x^3$$

Non-systematic code vector

$$\begin{aligned} c(x)&=m(x)g(x)=(1+x+x^3)(1+x+x^3)\\ &=1+x^2+x^6\quad(\text{cross terms cancel in mod 2: }(a+b+c)^2=a^2+b^2+c^2) \end{aligned}$$

$(c_0c_1\dots c_6)$ = 1010001

Systematic code vector

$$x^3m(x)=x^3+x^4+x^6$$

Divide by $g(x)=1+x+x^3$:

              x^3
          -----------------------
x^3+x+1 ) x^6 + x^4 + x^3
          x^6 + x^4 + x^3
          ---------------
                          0

Remainder $b(x)=0$, parity bits $(b_0b_1b_2)=000$.

$$c(x)=b(x)+x^3m(x)=x^3+x^4+x^6$$

$(b_0b_1b_2\,m_0m_1m_2m_3)$ = 000 1101

This happens because $m(x)$ itself equals $g(x)$, so $x^3m(x)$ is already a multiple of $g(x)$.

Both have weight 3, equal to $d_{min}$ of the code.