Syndrome is Zero iff Vector is Codeword
Theorem
Let $C$ be a linear $\tuple {n, k}$-code whose master code is $\map V {n, p}$
Let $G$ be a (standard) generator matrix for $C$.
Let $P$ be a standard parity check matrix for $C$.
Let $w \in \map V {n, p}$.
Then the syndrome of $w$ is zero if and only if $w$ is a codeword of $C$.
Proof
Let $G = \paren {\begin{array} {c|c} \mathbf I & \mathbf A \end{array} }$.
Let $c \in \map V {n, p}$.
Then, by definition of $G$, $c$ is a codeword of $C$ if and only if $c$ is of the form $u G$, where $u \in \map V {k, p}$.
Thus $c \in C$ if and only if:
\(\ds c\) | \(=\) | \(\ds u G\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds u \paren {\begin{array} {c | c} \mathbf I & \mathbf A \end{array} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\begin{array} {c | c} u & v \end{array} }\) |
where:
- $v = u \mathbf A$
- $\paren {\begin{array} {c|c} u & v \end{array} }$ denotes the $1 \times n$ matrix formed from the $k$ elements of $u$ and the $n - k$ elements of $v$.
Let $w \in \map V {n, p}$.
$w$ can be expressed in the form:
- $w = \paren {\begin{array} {c|c} u_1 & v_1 \end{array} }$
where $u_1 \in \map V {k, p}$.
The syndrome of $v$ is then calculated as:
\(\ds \map S v\) | \(=\) | \(\ds \paren {\begin{array} {c | c} -\mathbf A^\intercal & \mathbf I \end{array} } w^\intercal\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\begin{array} {c | c} -\mathbf A^\intercal & \mathbf I \end{array} } \paren {\begin{array} {c | c} u_1^\intercal & v_1^\intercal \end{array} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds -\mathbf A^\intercal u_1^\intercal + v_1^\intercal\) |
It follows that the syndrome of $w$ is zero if and only if $w$ is the concatenation of $u_1$ and $v_1$, where:
- $v_1^\intercal = \mathbf A^\intercal u_1^\intercal = \paren {u_1 \mathbf A}^\intercal$
Thus the syndrome of $w$ is zero if and only if $w$ is a codeword of $C$.
$\blacksquare$
Sources
- 1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $6$: Error-correcting codes: Proposition $6.20$