Syndrome is Zero iff Vector is Codeword

From ProofWiki
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Syndrome_is_Zero_iff_Vector_is_Codeword&oldid=388071"