Hamming distance and weight importance; syndrome decoding

Importance of Hamming distance and weight

• Hamming weight (number of 1s) and Hamming distance (number of differing positions) measure how far codewords are apart.
• For a linear code, minimum distance $d_{min}$ = minimum non-zero weight, so it is found easily.
• $d_{min}$ sets the error-control power of the code: it detects up to $d_{min}-1$ errors and corrects up to $\lfloor(d_{min}-1)/2\rfloor$ errors.
• Decoders choose the codeword at minimum Hamming distance from the received word (maximum-likelihood for a binary symmetric channel).

Syndrome decoding in linear block codes

For a code with generator $G=[I_k\mid P]$ and parity-check matrix $H=[P^T\mid I_{n-k}]$, every codeword satisfies $\mathbf{c}H^T=\mathbf{0}$. A received word is $\mathbf{r}=\mathbf{c}\oplus\mathbf{e}$, where $\mathbf{e}$ is the error pattern. The syndrome is

$$\mathbf{s}=\mathbf{r}H^T=\mathbf{c}H^T\oplus\mathbf{e}H^T=\mathbf{e}H^T$$

so it depends only on the error, not on the sent codeword.

Steps:

1. Compute $\mathbf{s}=\mathbf{r}H^T$.
2. If $\mathbf{s}=\mathbf{0}$, accept $\mathbf{r}$ as the codeword.
3. Otherwise look up the coset leader (most likely error pattern, usually single-bit) with that syndrome; for a single error in bit $i$, $\mathbf{s}$ equals the $i$-th column of $H$.
4. Correct: $\hat{\mathbf{c}}=\mathbf{r}\oplus\mathbf{e}$.

Example: (6,3) code

$$H=\begin{bmatrix}1&0&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\end{bmatrix}$$

Syndrome table (single errors):

Message 101 gives codeword $\mathbf{c}=101011$. Suppose $\mathbf{r}=100011$ (bit 3 flipped).

$$\mathbf{s}=\mathbf{r}H^T=\text{col}_1\oplus\text{col}_5\oplus\text{col}_6=(1,0,1)\oplus(0,1,0)\oplus(0,0,1)=(1,1,0)$$

From the table, $\mathbf{e}=001000$, so $\hat{\mathbf{c}}=100011\oplus001000=101011$, message 101 recovered.