Parity Checks as Equations for a Code
A linear code over a finite field is a subspace of vectors of a fixed length. A parity-check matrix records linear equations that every codeword must satisfy. These equations provide a direct test: multiply a candidate word by the matrix, using arithmetic in the field. The result, called the syndrome, is zero for codewords. For a received word, a nonzero syndrome certifies that the word is not a codeword, though a zero syndrome does not always certify that no error occurred.
Throughout, let \(p\) be prime and use the field \(\mathbb{F}_p\), where addition and multiplication are performed modulo \(p\). A word of length \(n\) is a column vector in \(\mathbb{F}_p^n\). A linear code \(C\) of length \(n\) is a subspace of \(\mathbb{F}_p^n\). In particular, it contains \(\mathbf{0}\) and is closed under addition and scalar multiplication.
Each row of \(\mathbf{H}\) supplies one linear equation, or parity check. If the \(i\)-th row is \((h_{i1},\dots,h_{in})\), its check on \(\mathbf{x}\) is \(h_{i1}x_1+\cdots+h_{in}x_n=0\) in \(\mathbb{F}_p\). A word is a codeword exactly when it passes every row’s check. The number of rows need not be the dimension of the code: some checks can be redundant without changing the null space.
Proof. By the definition of a parity-check matrix, \(C=\operatorname{Nul}\mathbf{H}\). By the definition of the null space, \(\mathbf{x}\in\operatorname{Nul}\mathbf{H}\) if and only if \(\mathbf{H}\mathbf{x}=\mathbf{0}\). Substituting the first equality into the second gives the claimed equivalence. \(\square\)
Every Linear Code Has a Parity-Check Matrix
The definition requires that the code be the null space of the chosen matrix. Such a matrix exists for every linear code in \(\mathbb{F}_p^n\). The construction makes explicit why parity checks can describe an entire subspace, not just a particular list of examples.
Proof. Choose a basis \(\mathbf{c}_1,\dots,\mathbf{c}_k\) of \(C\). Extend it to a basis of \(\mathbb{F}_p^n\) by considering the standard basis vectors \(\mathbf{e}_1,\dots,\mathbf{e}_n\) in order and appending each one that is not already in the span of the vectors collected so far. The resulting list is independent, since each appended vector is outside the span of its predecessors. It spans the whole space, since every standard basis vector is either in the resulting span already or is appended. Write the added vectors as \(\mathbf{u}_1,\dots,\mathbf{u}_m\). Every \(\mathbf{x}\in\mathbb{F}_p^n\) has a unique expression in this basis: \(\mathbf{x}=\sum_{i=1}^k a_i\mathbf{c}_i+\sum_{j=1}^m b_j\mathbf{u}_j\). For each \(j\), define \(\phi_j(\mathbf{x})=b_j\), the coefficient of \(\mathbf{u}_j\). Uniqueness of coordinates makes this well-defined, and adding vectors or multiplying by a field scalar adds or scales their coordinates, so \(\phi_j\) is linear. Because \(\mathbf{x}=\sum_{\ell=1}^n x_\ell\mathbf{e}_\ell\), linearity gives \(\phi_j(\mathbf{x})=\sum_{\ell=1}^n x_\ell\phi_j(\mathbf{e}_\ell)\). Thus \(\phi_j\) is multiplication by the row \((\phi_j(\mathbf{e}_1),\dots,\phi_j(\mathbf{e}_n))\). Put these rows into \(\mathbf{H}\). Then \(\mathbf{H}\mathbf{x}=\mathbf{0}\) exactly when all the coefficients \(b_j\) are zero, which holds exactly when \(\mathbf{x}\in\operatorname{span}\{\mathbf{c}_1,\dots,\mathbf{c}_k\}=C\). Therefore \(C=\operatorname{Nul}\mathbf{H}\). If \(C=\mathbb{F}_p^n\), there are no added vectors and \(\mathbf{H}\) has zero rows; its null space is the whole space. \(\square\)
Worked Codeword Test Over \(\mathbb{F}_2\)
Worked Example: Find the Words That Pass Two Checks
Let \(\mathbb{F}_2=\{0,1\}\), with arithmetic modulo \(2\), and take \(\mathbf{H}=\begin{bmatrix}1&1&0&1\\0&1&1&1\end{bmatrix}\). Determine its null space and check whether \(\mathbf{c}=(1,0,1,1)^{\top}\) is a codeword.
For \(\mathbf{x}=(x_1,x_2,x_3,x_4)^{\top}\), the equation \(\mathbf{H}\mathbf{x}=\mathbf{0}\) gives two equations in \(\mathbb{F}_2\): \(x_1+x_2+x_4=0\) and \(x_2+x_3+x_4=0\). Set \(a=x_2\) and \(b=x_4\). Since the additive inverse of every element in \(\mathbb{F}_2\) equals itself, the equations give \(x_1=a+b\) and \(x_3=a+b\). Therefore the words in the null space are exactly \(\mathbf{x}=(a+b,a,a+b,b)^{\top}\), where \(a,b\in\mathbb{F}_2\).
For the proposed word, multiply by each row, reducing modulo \(2\): \(1+0+0+1=2=0\) and \(0+0+1+1=2=0\) in \(\mathbb{F}_2\). Thus \(\mathbf{H}\mathbf{c}=(0,0)^{\top}\), so \(\mathbf{c}\) is in the null space and is a codeword.
Check: taking \(a=0\) and \(b=1\) in the null-space description gives \((a+b,a,a+b,b)^{\top}=(1,0,1,1)^{\top}\), as required.
What a Syndrome Says About an Error
Suppose a codeword \(\mathbf{c}\in C\) is sent and a vector \(\mathbf{e}\in\mathbb{F}_p^n\) is added during transmission. The vector \(\mathbf{e}\) is the error pattern, and the received word is \(\mathbf{r}=\mathbf{c}+\mathbf{e}\). The syndrome of \(\mathbf{r}\) can be expressed using the error alone, because the transmitted word passes every check.
Proof. By linearity of matrix multiplication, \(\mathbf{H}\mathbf{r}=\mathbf{H}(\mathbf{c}+\mathbf{e})=\mathbf{H}\mathbf{c}+\mathbf{H}\mathbf{e}\). Since \(\mathbf{c}\in C=\operatorname{Nul}\mathbf{H}\), we have \(\mathbf{H}\mathbf{c}=\mathbf{0}\), and hence \(\mathbf{H}\mathbf{r}=\mathbf{H}\mathbf{e}\). This syndrome is nonzero exactly when \(\mathbf{H}\mathbf{e}\ne\mathbf{0}\), which, by \(C=\operatorname{Nul}\mathbf{H}\), holds exactly when \(\mathbf{e}\notin C\). The zero vector belongs to every subspace, so a nonzero syndrome also implies \(\mathbf{e}\ne\mathbf{0}\): an error occurred. \(\square\)
Worked Example: A Received Word With Nonzero Syndrome
Use the binary matrix from the previous example. Let \(\mathbf{c}=(1,0,1,1)^{\top}\) be transmitted, and suppose an error changes the second coordinate, so \(\mathbf{e}=(0,1,0,0)^{\top}\). Find the received word and its syndrome.
Add the vectors in \(\mathbb{F}_2^4\): \(\mathbf{r}=\mathbf{c}+\mathbf{e}=(1,1,1,1)^{\top}\). Multiply by the first row of \(\mathbf{H}\): \(1+1+0+1=3=1\) modulo \(2\). Multiply by the second row: \(0+1+1+1=3=1\) modulo \(2\). Therefore \(\mathbf{H}\mathbf{r}=(1,1)^{\top}\), which is nonzero.
The error itself has the same syndrome: the second column of \(\mathbf{H}\) is \((1,1)^{\top}\), and \(\mathbf{H}\mathbf{e}=(1,1)^{\top}\). This agrees with the theorem. The nonzero syndrome detects that the received word is not a codeword; this calculation alone does not establish a general rule for uniquely identifying an error.
Check: \(\mathbf{H}\mathbf{c}=(0,0)^{\top}\), so \(\mathbf{H}(\mathbf{c}+\mathbf{e})=\mathbf{0}+\mathbf{H}\mathbf{e}=(1,1)^{\top}\), as calculated directly.
Why a Zero Syndrome Can Miss an Error
A zero syndrome says that the received word satisfies every parity check. It does not, by itself, say that the received word is the one that was sent. The theorem identifies the exact condition: the syndrome is zero precisely when the error vector belongs to \(C\). A nonzero error that is itself a codeword can therefore turn one codeword into another without violating any check.
Worked Example: A Nonzero Error With Zero Syndrome
Work over \(\mathbb{F}_3\) and let \(\mathbf{H}=\begin{bmatrix}1&1&1\end{bmatrix}\). The code consists of vectors whose coordinates sum to zero modulo \(3\). Take the transmitted codeword \(\mathbf{c}=(1,2,0)^{\top}\) and the nonzero error \(\mathbf{e}=(1,2,0)^{\top}\).
First check the transmitted word: \(\mathbf{H}\mathbf{c}=1+2+0=3=0\) in \(\mathbb{F}_3\), so \(\mathbf{c}\in C\). The error is also nonzero and satisfies \(\mathbf{H}\mathbf{e}=1+2+0=3=0\), so \(\mathbf{e}\in C\). The received word is \(\mathbf{r}=\mathbf{c}+\mathbf{e}=(2,4,0)^{\top}=(2,1,0)^{\top}\) in \(\mathbb{F}_3^3\). Its syndrome is \(\mathbf{H}\mathbf{r}=2+1+0=3=0\).
Thus an error occurred even though the received word has zero syndrome. In fact, \(\mathbf{r}\) is another codeword: its coordinates sum to zero modulo \(3\). The checks detect whether a word lies outside the code, not whether it is the particular codeword that was transmitted.
Check: the error is nonzero, but \(\mathbf{H}\mathbf{e}=0\); the identity \(\mathbf{H}\mathbf{r}=\mathbf{H}\mathbf{c}+\mathbf{H}\mathbf{e}=0+0=0\) confirms the computed syndrome.
Common Pitfall: Forgetting the Field
Every matrix product in this topic is computed in \(\mathbb{F}_p\), not in the integers. For the binary codeword \(\mathbf{c}=(1,0,1,1)^{\top}\) above, the two row sums as integers are \(2\) and \(2\). A wrong calculation reports \(\mathbf{H}\mathbf{c}=(2,2)^{\top}\) and concludes that the syndrome is nonzero. The correction is to reduce each component modulo \(2\): \((2,2)^{\top}=(0,0)^{\top}\) in \(\mathbb{F}_2^2\). The word passes both checks.
Keep three conclusions distinct. A zero syndrome means the word belongs to the code. A nonzero syndrome means the word does not belong to the code. If the word was formed by adding an error to a codeword, a nonzero syndrome proves that the error is nonzero; a zero syndrome only says that the error belongs to the code, and that error could still be nonzero.
Check Your Understanding
Use arithmetic in the specified field throughout. For syndrome questions, state what the result does and does not establish.
- For \(\mathbf{H}=\begin{bmatrix}1&1&1\end{bmatrix}\) over \(\mathbb{F}_2\), test whether \((1,1,0)^{\top}\) is a codeword.
- Over \(\mathbb{F}_2\), compute the syndrome of \((1,0,1,0)^{\top}\) using the \(2\times4\) matrix in the examples.
- If \(\mathbf{r}=\mathbf{c}+\mathbf{e}\) and \(\mathbf{c}\in\operatorname{Nul}\mathbf{H}\), show that the syndrome of \(\mathbf{r}\) equals \(\mathbf{H}\mathbf{e}\).
- Give a reason, using the null-space definition, that a nonzero syndrome rules out \(\mathbf{r}\in C\).
- For the \(\mathbb{F}_3\) example, explain why the zero syndrome does not imply that the error vector was zero.
