Short note: Syndrome calculation in linear systematic block code

In a linear systematic $(n,k)$ block code, $G=[I_k\mid P]$ and the parity-check matrix is $H=[P^T\mid I_{n-k}]$, so every codeword obeys $\mathbf{c}H^T=\mathbf{0}$. The syndrome of a received vector $\mathbf{r}$ is the $(n-k)$-bit vector

$$\mathbf{s}=\mathbf{r}H^T$$

Properties

• Writing $\mathbf{r}=\mathbf{c}\oplus\mathbf{e}$: $\mathbf{s}=\mathbf{e}H^T$, i.e. it depends only on the error pattern.
• $\mathbf{s}=\mathbf{0}$: no detectable error. $\mathbf{s}\neq\mathbf{0}$: error present.
• For a single error in bit $i$, $\mathbf{s}$ = $i$-th column of $H$, so the error is located directly.
• All error patterns in one coset of the standard array share one syndrome; the coset leader is taken as the error.

Calculation

In systematic form, $\mathbf{s}$ = (parity bits recomputed from the received message bits) $\oplus$ (received parity bits).

 r = [ received msg | received parity ]
         |                 |
   [recompute parity]      |
         |                 |
         +------(XOR)------+--> syndrome s

Example, $(6,3)$ code with $H=\begin{bmatrix}1&0&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\end{bmatrix}$ and $\mathbf{r}=100011$:

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

This equals column 3, so bit 3 is wrong; corrected word 101011. For cyclic codes, the syndrome is the remainder of $r(x)/g(x)$, computed with a shift register.