# 19.4: Using the Parity-Check Matrix For Decoding

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

Notation

A binary linear code is of type $$(n, k)$$ (or we say $$\mathcal{C}$$ is an $$(n, k)$$ code) if its generator matrix $$G = \left[ \begin{array}{ll} I_k \\ A \end{array} \right]$$ is an $$n \times k$$ matrix. In other words, $$G$$ encodes messages of length $$k$$ as codewords of length $$n$$, which means that the number of check bits is $$n−k$$. We usually use $$r$$ to denote the number of check bits, so $$r = n − k$$. Then $$A$$ is an $$r \times k$$ matrix.

Exercise $$\PageIndex{1}$$

How many codewords are there in a binary linear code of type $$(n, k)$$?

Definition: Parity-Check Matrix

If $$G = \left[ \begin{array}{ll} I_k \\ A \end{array} \right]$$ is the generator matrix of a binary linear code $$\mathcal{C}$$, and $$A$$ is an $$r \times k$$ matrix (so $$\mathcal{C}$$ is of type $$(k + r, k)$$), then the parity-check matrix of $$\mathcal{C}$$ is

$P = [A \;\; I_r].$

Example $$\PageIndex{1}$$

1) For the code $$\mathcal{C}$$ of Example 19.3.2, the matrix $$A$$ is $$2 \times 3$$, so $$r = 2$$. Therefore, the parity-check matrix of $$\mathcal{C}$$ is

$$P = [A \;\; I_r] = [A\;\; I_2] = \left[ \begin{array}{ll} 1\;\;0\;\;1\;\;1\;\;0 \\ 0\;\;1\;\;1\;\;0\;\;1 \end{array} \right]$$.

2) For a single parity check-bit, as in Example 19.3.1, we have $$A = [1\;\; 1\;\; 1]$$. This is a $$1 \times 3$$ matrix, so $$r = 1$$. Therefore, the parity-check matrix of the code is

$$P = [A\;\;I_r] = [A\;\; I_1] = [1\;\; 1\;\; 1\;\; 1]$$

(since $$I_1 = [1]$$).

Exercise $$\PageIndex{2}$$

Suppose the generator matrix of the binary linear code $$\mathcal{C}$$ is

$$\left[ \begin{array}{ll} 1\;\;0\;\;0\;\;0 \\ 0\;\;1\;\;0\;\;0 \\ 0\;\;0\;\;1\;\;0 \\ 0\;\;0\;\;0\;\;1 \\ 1\;\;0\;\;1\;\;1 \\ 1\;\;0\;\;0\;\;1 \\ 0\;\;1\;\;1\;\;1 \end{array} \right]$$

What is the parity-check matrix of this code?

The parity-check matrix can be used to check whether a message we received is a valid codeword:

Proposition $$\PageIndex{1}$$

A column vector x is a codeword if and only if $$Px = 0$$.

Proof

$$(⇒)$$ Since $$x$$ is a codeword, we have $$x = Gm$$ for some ($$k$$-bit) message $$m$$. This means that

$x = Gm = \left[ \begin{array}{ll} I_k \\ A \end{array} \right] m = \left[ \begin{array}{ll} m \\ Am \end{array} \right]$

Then

$Px = [A \;\; I_r] \left[ \begin{array}{ll} m \\ Am \end{array} \right] = [Am + Am] = [2Am] ≡ 0 (\text{mod } 2).$

$$(⇐)$$ Suppose $$Px = 0$$. Write $$x = \left[ \begin{array}{ll} m \\ y \end{array} \right]$$, where

• $$m$$ is the first $$k$$ rows of $$x$$, and
• $$y$$ is the remaining $$r = n − k$$ rows of $$x$$.

Then

$0 = Px = [A \;\;I_r] \left[ \begin{array}{ll} m \\ y \end{array} \right] = [Am + y].$

This means $$y = −Am = Am (\text{mod } 2)$$, so

$x = \left[ \begin{array}{ll} m \\ y \end{array} \right] = \left[ \begin{array}{ll} m \\ Am \end{array} \right] = \left[ \begin{array}{ll} I-k \\ A \end{array} \right] m = Gm$

so $$x ∈ \mathcal{C}$$.

Example $$\PageIndex{3}$$

Here is a simple illustration of Proposition 19.4.1. For the code in which every codeword is required to have an even number of $$1$$s, Example 19.4.1(2) tells us that the parity-check matrix is $$P = [1\;\; 1\;\; 1\;\; 1]$$. Hence, for any $$4$$-bit string $$x_1x_2x_3x_4$$, we have

$$Px = [1\;\;1\;\;1\;\;1] \left[ \begin{array}{ll} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right] = [x_1 + x_2 + x_3 + x_4].$$

This is $$0 (\text{mod } 2)$$ if and only if there are an even number of $$1$$s in $$x$$, which is what it means to say that $$x$$ is a codeword.

Example $$\PageIndex{4}$$

Use the parity-check matrix to determine whether each of these words is in the code $$\mathcal{C}$$ of Example 19.3.2:

$$11111, 10101, 00000, 11010.$$

Solution

From Example 19.4.1(1), we know that the parity-check matrix of this code is

$$P = \left[ \begin{array}{ll} 1\;\;0\;\;1\;\;1\;\;0 \\ 0\;\;1\;\;1\;\;0\;\;1 \end{array} \right].$$

We have:

• $$P = \left[ \begin{array}{ll} 1\\1\\1\\1\\1 \end{array} \right] = \left[ \begin{array}{ll} 1 · 1 + 0 · 1 + 1 · 1 + 1 · 1 + 0 · 1 \\ 0 · 1 + 1 · 1 + 1 · 1 + 0 · 1 + 1 · 1 \end{array} \right] = \left[ \begin{array}{ll} 1\\1 \end{array} \right] \neq \left[ \begin{array}{ll} 0\\0 \end{array} \right]$$, so $$11111$$ is not a codeword.
• $$P = \left[ \begin{array}{ll} 1\\0\\1\\0\\1 \end{array} \right] = \left[ \begin{array}{ll} 1 · 1 + 0 · 0 + 1 · 1 + 1 · 0 + 0 · 1 \\ 0 · 1 + 1 · 0 + 1 · 1 + 0 · 0 + 1 · 1 \end{array} \right] = \left[ \begin{array}{ll} 0\\0 \end{array} \right]$$, so $$10101$$ is a codeword.
• $$P = \left[ \begin{array}{ll} 0\\0\\0\\0\\0 \end{array} \right] = \left[ \begin{array}{ll} 1 · 0 + 0 · 0 + 1 · 0 + 1 · 0 + 0 · 0 \\ 0 · 0 + 1 · 0 + 1 · 0 + 0 · 0 + 1 · 0 \end{array} \right] = \left[ \begin{array}{ll} 0\\0 \end{array} \right]$$, so $$00000$$ is a codeword.
• $$P = \left[ \begin{array}{ll} 1\\1\\0\\1\\0 \end{array} \right] = \left[ \begin{array}{ll} 1 · 1 + 0 · 1 + 1 · 0 + 1 · 1 + 0 · 0 \\ 0 · 1 + 1 · 1 + 1 · 0 + 0 · 1 + 1 · 0 \end{array} \right] = \left[ \begin{array}{ll} 0\\1 \end{array} \right] \neq \left[ \begin{array}{ll} 0\\0 \end{array} \right]$$, so $$11010$$ is not a codeword.

(These answers can be verified by looking at the list the elements of \mathcal{C} in the solution of Example 19.3.2.)

It is evident from the parity-check matrix whether a code corrects every single-bit error:

Theorem $$\PageIndex{1}$$

A binary linear code $$\mathcal{C}$$ can correct every single-bit error if and only if the columns of its parity-check matrix are all distinct and nonzero.

Proof

Suppose a codeword $$x$$ is transmitted, but the ith bit gets changed, so a different string $$y$$ is received. Let ei be the string that is all $$0$$s, except that the $$i^{\text{th}}$$ bit is $$1$$, so $$y = x+e_i$$. Then

$P_y = P(x + e_i) = P_x + Pe_i = 0 + Pe_i = P_ei$

is the $$i^{\text{th}}$$ column of $$P$$.

Therefore, if all the columns of $$P$$ are nonzero, then $$P_y$$ is nonzero, so the receiver can detect that there was an error. If, in addition, all of the columns of $$P$$ are distinct, then $$P_y$$ is equal to the $$i^{\text{th}}$$ column of $$P$$, and not equal to any other column, so the receiver can conclude that the error is in the ith bit. Changing this bit corrects the error.

Conversely, if either the $$i^{\text{th}}$$ column of $$P$$ is zero, or the $$i^{\text{th}}$$ column is equal to the $$j^{\text{th}}$$ column, then either $$Pe_i = 0$$ or $$Pe_i = Pe_j$$. Therefore, when the codeword $$00 . . . 0$$ is sent, and an error changes the $$i^{\text{th}}$$ bit, resulting in the message $$e_i$$ being received, either $$Pe_i = 0$$, so the receiver does not detect the error (and erroneously concludes that the message $$e_i$$ is what was sent), or cannot tell whether the error is in the $$i^{\text{th}}$$ bit (and message $$0$$ was sent) or the error is in the $$j^{\text{th}}$$ bit (and message $$e_i + e_j$$ was sent). In either case, this is a single-bit error that cannot be corrected.

Exercise $$\PageIndex{3}$$

The parity-check matrix of the binary linear code $$\mathcal{C}$$ is

$$P = \left[ \begin{array}{ll} 0\;\;1\;\;1\;\;1\;\;0 \\ 1\;\;0\;\;1\;\;0\;\;1 \end{array} \right].$$

Can $$\mathcal{C}$$ correct all single-bit errors?

The proof of Theorem 19.4.1 shows how to correct any single-bit error (when it is possible):

## General Method.

Assume the word $$y$$ has been received. Calculate $$P_y$$.

• If $$P_y = 0$$, then $$y$$ is a codeword. Assume there were no errors, so $$y$$ is the codeword that was sent.
• Now suppose $$P_y \neq 0$$.
• If $$P_y$$ is equal to the $$i^{\text{th}}$$ column of $$P$$, then let $$x = y+e_i$$. (In other words, create $$x$$ by changing the $$i^{\text{th}}$$ bit of $$y$$ from $$0$$ to $$1$$ or vice-versa.) Then $$x$$ is a codeword. Assume it is the codeword that was sent.
• If $$P_y$$ is not equal to any of the columns of $$P$$, then at least two of the bits of $$y$$ are wrong. Do not try to correct the error.

Example $$\PageIndex{5}$$

Suppose the parity-check matrix of a binary linear code is

$$P = \left[ \begin{array}{ll} 1\;\;1\;\;1\;\;1\;\;0\;0 \\ 1\;\;0\;\;1\;\;0\;\;1\;0 \\ 1\;\;1\;\;0\;\;0\;\;0\;\;1 \end{array} \right].$$

Decode each of the following received words:

$$111000, 101001, 001101.$$

Solution

Let $$P$$ be the given parity-check matrix. Then:

$$P = \left[ \begin{array}{ll} 1\\1\\1\\0\\0\\0 \end{array} \right] = \left[ \begin{array}{ll} 1\\0\\0 \end{array} \right]$$. This is the $$4^{\text{th}}$$ column of $$P$$, so changing the $$4^{\text{th}}$$ bit corrects the error. This means that the received word $$111000$$ decodes as $$111\underline{1}00$$.

$$P = \left[ \begin{array}{ll} 1\\0\\1\\0\\0\\1 \end{array} \right] = \left[ \begin{array}{ll} 0\\0\\0 \end{array} \right]$$. This is $$0$$, so there is no error. This means that the received word $$101001$$ decodes as $$101001$$.

$$P = \left[ \begin{array}{ll} 0\\0\\1\\1\\0\\1 \end{array} \right] = \left[ \begin{array}{ll} 0\\1\\1 \end{array} \right]$$. This is not any of the columns of $$P$$, so there are at least two errors. Therefore, we cannot decode the received word $$001101$$.

Exercise $$\PageIndex{4}$$

1) The parity-check matrix of a certain binary linear code is

$$P = \left[ \begin{array}{ll} 1\;\;0\;\;1\;\;0\;\;1\;\;0\;\;0\;\;0 \\ 1\;\;0\;\;0\;\;1\;\;0\;\;1\;\;0\;\;0 \\ 0\;\;1\;\;0\;\;1\;\;0\;\;0\;\;1\;\;0 \\ 0\;\;1\;\;1\;\;1\;\;0\;\;0\;\;0\;\;1 \end{array} \right].$$

(a) Decode each of the following received words: $$10001111$$, $$11110000$$, $$01111101$$.

(b) Find the generator matrix of the code.

2) The parity check matrix of a certain binary linear code is

$$P = \left[ \begin{array}{ll} 1\;\;1\;\;0\;\;1\;\;0\;0 \\ 0\;\;1\;\;1\;\;0\;\;1\;0 \\ 1\;\;0\;\;1\;\;0\;\;0\;\;1 \end{array} \right].$$

(a) Can the code correct all single-bit errors?

(b) Decode each of the following received words: $$001001$$, $$110011$$, $$000110$$

Example $$\PageIndex{6}$$

Let

$$P = \left[ \begin{array}{ll} 1\;\; 1\;\; 1\;\; 1\;\; 1\;\; 1\;\; 1\;\; 0\;\; 0\;\; 0\;\; 0 \\ 1\;\; 1\;\; 1\;\; 1\;\; 0\;\; 0\;\; 0\;\; 1 \;\;1\;\; 1\;\; 0 \\ 1\;\; 1 \;\;0\;\; 0 \;\;1 \;\;1 \;\;0 \;\;1\;\;1\;\; 0\;\; 1\\ 1 \;\;0 \;\;1 \;\;0\;\; 1\;\; 0 \;\;1 \;\;1\;\; 0\;\; 1\;\; 1 \end{array} \right].$$

This is a $$4 \times 11$$ matrix whose columns list all of the binary vectors of length $$4$$ that have at least two $$1$$s. The corresponding $$4 \times 15$$ parity-check matrix $$P = [A\;\;I_4]$$ lists all $$2^4 − 1 = 15$$ nonzero binary vectors of length $$4$$ (without repetition), so the resulting binary linear code can correct all single-bit errors.

The corresponding generator matrix $$G = \left[ \begin{array}{ll} I_{11} \\ A \end{array} \right].$$ is a $$15 \times 11$$ matrix, so it takes an $$11$$-bit message, and adds only $$15 − 11 = 4$$ check bits. This is much more efficient than the triplerepetition code of Example 19.1.3, which would have to add $$22$$ check bits to detect every single-bit error in an $$11$$-bit message.

Note

Generalizing Example 19.4.6, a binary linear code is called a Hamming code if the columns of its parity-check matrix $$P = [A\;\; I_r]$$ are a list of all the $$2^r − 1$$ nonzero binary vectors of length $$r$$ (in some order, and without repetition). Every Hamming code can correct all single-bit errors. Because of their high efficiency, Hamming codes are often used in real-world applications. But they only correct single-bit errors, so other binary linear codes (which we will not discuss) need to be used in situations where it is likely that more than one bit is wrong.

Exercise $$\PageIndex{5}$$

1) Explain how to make a binary linear code of type $$(29, 24)$$ that corrects all single-bit errors.

2) Explain why it is impossible to find a binary linear code of type $$(29, 25)$$ that corrects all single-bit errors.

3) For each $$k ≤ 20$$, find the smallest possible number $$r$$ of check bits in a binary linear code that will let you send $$k$$-bit messages and correct all single-bit errors. (That is, for each $$k$$, we want a code of type $$(n, k)$$ that corrects all single-bit errors, and we want $$r = n − k$$ to be as small as possible.)

4) What is the smallest possible number $$r$$ of check bits in a binary linear code that will let you send $$100$$-bit messages and correct all single-bit errors?

This page titled 19.4: Using the Parity-Check Matrix For Decoding is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Joy Morris.