Hamming weight and distance; (7,4) cyclic code for 1011

Hamming weight

The Hamming weight $w(\mathbf{c})$ of a code vector is the number of non-zero (1) elements in it.

Example: $w(1011100)=4$, $w(0000000)=0$.

Hamming distance

The Hamming distance $d(\mathbf{c}_1,\mathbf{c}_2)$ between two code vectors of equal length is the number of positions in which they differ. It equals the weight of their modulo-2 sum: $d(\mathbf{c}_1,\mathbf{c}_2)=w(\mathbf{c}_1\oplus\mathbf{c}_2)$.

Example: $\mathbf{c}_1=1011100$, $\mathbf{c}_2=1111111$; $\mathbf{c}_1\oplus\mathbf{c}_2=0100011$, so $d=3$.

The smallest distance between any two codewords is the minimum distance $d_{min}$; for a linear code it equals the smallest non-zero weight. A code detects up to $d_{min}-1$ errors and corrects up to $\lfloor (d_{min}-1)/2\rfloor$. For the (7,4) cyclic Hamming code $d_{min}=3$: it detects 2 and corrects 1 error.

(7,4) cyclic code for data 1011

Given $g(x)=x^3+x^2+1$, $n-k=3$. Convention: leftmost bit = highest power, so $d(x)=x^3+x+1$. Modulo-2 arithmetic.

Non-systematic form: $c(x)=d(x)g(x)$

$$\begin{aligned} c(x)&=(x^3+x+1)(x^3+x^2+1)\\ &=x^6+x^5+x^3\;+\;x^4+x^3+x\;+\;x^3+x^2+1\\ &=x^6+x^5+x^4+x^3+x^2+x+1 \end{aligned}$$

Non-systematic code vector: 1111111.

Systematic form:

1. $x^3d(x)=x^6+x^4+x^3$
2. Divide by $g(x)$:

              x^3 + x^2
          -------------------------
x^3+x^2+1 ) x^6 +     x^4 + x^3
            x^6 + x^5 +       x^3
            -----------------------
                  x^5 + x^4
                  x^5 + x^4 +       x^2
                  -------------------
                                    x^2

3. Remainder $p(x)=x^2$, parity bits $= 100$.
4. $c(x)=x^6+x^4+x^3+x^2$.

Systematic code vector: 1011 100 (message, then parity).

Check: $c(x)=(x^3+x^2)g(x)$, so $c(x)$ is divisible by $g(x)$ and is a valid codeword.