Hamming weight and distance; validate code 100011

Hamming weight

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

Example: $w(101011)=4$, $w(100011)=3$.

Hamming distance

The Hamming distance $d(\mathbf{c}_1,\mathbf{c}_2)$ is the number of positions in which two code vectors differ, $d=w(\mathbf{c}_1\oplus\mathbf{c}_2)$.

Example: $\mathbf{c}_1=101011$, $\mathbf{c}_2=100011$, $\mathbf{c}_1\oplus\mathbf{c}_2=001000$, so $d=1$.

Validating the received vector

A received vector is a valid codeword only if the syndrome $\mathbf{s}=\mathbf{r}H^T=\mathbf{0}$.

$$H=\begin{bmatrix}1&0&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\end{bmatrix},\qquad \mathbf{r}=(1\,0\,0\,0\,1\,1)$$

The 1s of $\mathbf{r}$ are at positions 1, 5, 6, so add columns 1, 5 and 6 of $H$:

$$\mathbf{s}=(1\ 1\ 0)\neq\mathbf{0}$$

The received vector 100011 is not a valid codeword; it contains an error.

Correction (single error)

The syndrome $110$ matches column 3 of $H$ $(1,1,0)^T$, so the 3rd bit is in error: $\mathbf{e}=001000$.

$$\hat{\mathbf{c}}=\mathbf{r}\oplus\mathbf{e}=100011\oplus001000=101011$$

Check: columns 1, 3, 5, 6 sum to $(1+1+0+0,\ 0+1+1+0,\ 1+0+0+1)=(0,0,0)$, so 101011 is valid. Corrected message (first 3 bits): 101.