Skip to main content

Section 19.4 Using the parity-check matrix for decoding

Notation 19.4.1.

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

How many codewords are there in a binary linear code of type \((n,k)\text{?}\)

Definition 19.4.3.

If \(G = \begin{bmatrix}I_k \\ A \end{bmatrix}\) is the generator matrix of a binary linear code \(\code\text{,}\) and \(A\) is an \(r \times k\) matrix (so \(\code\) is of type \((k + r, k)\)), then the parity-check matrix of \(\code\) is

\begin{equation*} P = [A \ I_r ]\text{.} \end{equation*}

  1. For the code \(\code\) of Example 19.3.5, the matrix \(A\) is \(2 \times 3\text{,}\) so \(r = 2\text{.}\) Therefore, the parity-check matrix of \(\code\) is

    \begin{equation*} P = [A \ I_r ] = [A \ I_2 ] = \begin{bmatrix}1 \amp 0 \amp 1 \amp 1 \amp 0 \\ 0 \amp 1 \amp 1 \amp 0 \amp 1 \end{bmatrix}\text{.} \end{equation*}

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

    \begin{equation*} P = [A \ I_r ] = [A \ I_1 ] = [ 1 \ 1 \ 1 \ 1] \end{equation*}

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

Suppose the generator matrix of the binary linear code \(\code\) is

\begin{equation*} \begin{bmatrix}1\amp 0\amp 0\amp 0\\ 0\amp 1\amp 0\amp 0\\ 0\amp 0\amp 1\amp 0\\ 0\amp 0\amp 0\amp 1\\ 1\amp 0\amp 1\amp 1\\ 1\amp 0\amp 0\amp 1\\ 0\amp 1\amp 1\amp 1 \end{bmatrix}\text{.} \end{equation*}

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:

\(\boldsymbol{(\Rightarrow)}\) Since \(x\) is a codeword, we have \(x = Gm\) for some (\(k\)-bit) message \(m\text{.}\) This means that

\begin{equation*} x = Gm = \begin{bmatrix}I_k \\ A \end{bmatrix} m = \begin{bmatrix}m \\ Am \end{bmatrix}\text{.} \end{equation*}

Then

\begin{equation*} Px = [A \ I_r ] \begin{bmatrix}m \\ Am \end{bmatrix} = \begin{bmatrix}Am + Am \end{bmatrix} = \begin{bmatrix}2 Am \end{bmatrix} \equiv 0 \pmod{2}\text{.} \end{equation*}

\(\boldsymbol{(\Leftarrow)}\) Suppose \(Px = 0\text{.}\) Write \(x = \begin{bmatrix}m \\ y \end{bmatrix}\text{,}\) where

  • \(m\) is the first \(k\) rows of \(x\text{,}\) and

  • \(y\) is the remaining \(r = n-k\) rows of \(x\text{.}\)

Then

\begin{equation*} 0 = Px = [A \ I_r ] \begin{bmatrix}m \\ y \end{bmatrix} = \begin{bmatrix}Am + y \end{bmatrix}\text{.} \end{equation*}

This means \(y = -Am = Am \pmod{2}\text{,}\) so

\begin{equation*} x = \begin{bmatrix}m \\ y \end{bmatrix} = \begin{bmatrix}m \\ Am \end{bmatrix} = \begin{bmatrix}I_k \\ A \end{bmatrix} m = Gm\text{,} \end{equation*}

so \(x \in \code\text{.}\)

⬛

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

\begin{equation*} P x = [ 1 \ 1 \ 1 \ 1] \begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = [x_1 + x_2 + x_3 + x_4 ]\text{.} \end{equation*}

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

Use the parity-check matrix to determine whether each of these words is in the code \(\code\) of Example 19.3.5:

\begin{equation*} 11111, \ 10101, \ 00000, \ 11010\text{.} \end{equation*}
Solution

From Example 19.4.4.1, we know that the parity-check matrix of this code is

\begin{equation*} P = \begin{bmatrix}1 \amp 0 \amp 1 \amp 1 \amp 0 \\ 0 \amp 1 \amp 1 \amp 0 \amp 1 \end{bmatrix}\text{.} \end{equation*}

We have:

  • \(P \begin{bmatrix}1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix}1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 \\ 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 \end{bmatrix} = \begin{bmatrix}1 \\ 1 \end{bmatrix} \neq \begin{bmatrix}0 \\ 0 \end{bmatrix}\text{,}\) so \(11111\) is not a codeword.

  • \(P \begin{bmatrix}1 \\ 0 \\ 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix}1 \cdot 1 + 0 \cdot 0 + 1 \cdot 1 + 1 \cdot 0 + 0 \cdot 1 \\ 0 \cdot 1 + 1 \cdot 0 + 1 \cdot 1 + 0 \cdot 0 + 1 \cdot 1 \end{bmatrix} = \begin{bmatrix}0 \\ 0 \end{bmatrix}\text{,}\) so \(10101\) is a codeword.

  • \(P \begin{bmatrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix}1 \cdot 0 + 0 \cdot 0 + 1 \cdot 0 + 1 \cdot 0 + 0 \cdot 0 \\ 0 \cdot 0 + 1 \cdot 0 + 1 \cdot 0 + 0 \cdot 0 + 1 \cdot 0 \end{bmatrix} = \begin{bmatrix}0 \\ 0 \end{bmatrix}\text{,}\) so \(00000\) is a codeword.

  • \(P \begin{bmatrix}1 \\ 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix}1 \cdot 1 + 0 \cdot 1 + 1 \cdot 0 + 1 \cdot 1 + 0 \cdot 0 \\ 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 + 0 \cdot 1 + 1 \cdot 0 \end{bmatrix} = \begin{bmatrix}0 \\ 1 \end{bmatrix} \neq \begin{bmatrix}0 \\ 0 \end{bmatrix}\text{,}\) so \(11010\) is not a codeword.

(These answers can be verified by looking at the list the elements of \(\code\) in the solution of Example 19.3.5.)

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

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

\begin{equation*} Py = P(x + e_i) = Px + P e_i = 0 + Pe_i = P e_i \end{equation*}

is the \(i\)th column of \(P\text{.}\)

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

Conversely, if either the \(i\)th column of \(P\) is zero, or the \(i\)th column is equal to the \(j\)th column, then either \(P e_i = 0\) or \(Pe_i = P e_j\text{.}\) Therefore, when the codeword \(00\ldots0\) is sent, and an error changes the \(i\)th bit, resulting in the message \(e_i\) being received, either \(Pe_i = 0\text{,}\) 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\)th bit (and message \(0\) was sent) or the error is in the \(j\) th bit (and message \(e_i + e_j\) was sent). In either case, this is a single-bit error that cannot be corrected.

⬛

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

\begin{equation*} P = \begin{bmatrix}0\amp 1\amp 1\amp 1\amp 0 \\ 1\amp 0\amp 1\amp 0\amp 1 \end{bmatrix}\text{.} \end{equation*}

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

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

General Method.

Assume the word \(y\) has been received. Calculate \(Py\text{.}\)

  • If \(Py = 0\text{,}\) then \(y\) is a codeword. Assume there were no errors, so \(y\) is the codeword that was sent.

  • Now suppose \(Py \neq 0\text{.}\)

    • If \(Py\) is equal to the \(i\)th column of \(P\text{,}\) then let \(x = y + e_i\text{.}\) (In other words, create \(x\) by changing the \(i\)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 \(Py\) is not equal to any of the columns of \(P\text{,}\) then at least two of the bits of \(y\) are wrong. Do not try to correct the error.

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

\begin{equation*} \begin{bmatrix}1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \\ 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \\ 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \end{bmatrix}\text{.} \end{equation*}

Decode each of the following received words:

\begin{equation*} 111000, \ 101001, \ 001101\text{.} \end{equation*}
Solution

Let \(P\) be the given parity-check matrix. Then:

  • \(P \begin{bmatrix}1\\1\\1\\0\\0\\0 \end{bmatrix} = \begin{bmatrix}1 \\ 0 \\ 0 \end{bmatrix} \text{.}\)
    This is the \(4\)th column of \(P\text{,}\) so changing the \(4\)th bit corrects the error. This means that the received word \(111000\) decodes as \(111\underline100\text{.}\)

  • \(P \begin{bmatrix}1\\0\\1\\0\\0\\1 \end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ 0 \end{bmatrix}\text{.}\)
    This is \(0\text{,}\) so there is no error. This means that the received word \(101001\) decodes as \(101001\text{.}\)

  • \(P \begin{bmatrix}0\\0\\1\\1\\0\\1 \end{bmatrix} = \begin{bmatrix}0 \\ 1 \\ 1 \end{bmatrix}\text{.}\)
    This is not any of the columns of \(P\text{,}\) so there are at least two errors. Therefore, we cannot decode the received word \(001101\text{.}\)

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

    \begin{equation*} \begin{bmatrix}1\amp 0\amp 1\amp 0\amp 1\amp 0\amp 0\amp 0 \\ 1\amp 0\amp 0\amp 1\amp 0\amp 1 \amp 0\amp 0\\ 0\amp 1\amp 0\amp 1\amp 0\amp 0\amp 1\amp 0 \\ 0\amp 1\amp 1\amp 1\amp 0\amp 0\amp 0\amp 1 \end{bmatrix}\text{.} \end{equation*}

    1. Decode each of the following received words: \(10001111, ~ 11110000, ~ 01111101 \text{.}\)

    2. Find the generator matrix of the code.

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

    \begin{equation*} \begin{bmatrix}1\amp 1\amp 0\amp 1\amp 0\amp 0 \\ 0\amp 1\amp 1\amp 0\amp 1\amp 0 \\ 1\amp 0\amp 1\amp 0\amp 0\amp 1 \end{bmatrix}\text{.} \end{equation*}

    1. Can the code correct all single-bit errors?

    2. Decode each of the following received words: \(001001, ~ 110011, ~ 000110 \text{.}\)

Let

\begin{equation*} A = \begin{bmatrix} 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \\ 1 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \\ 1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 1 \amp 1 \amp 0 \amp 1 \\ 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 0 \amp 1 \amp 1 \end{bmatrix} . \end{equation*}

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 = \begin{bmatrix}I_{11} \\ A \end{bmatrix}\) 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 triple-repetition code of Example 19.1.6, which would have to add \(22\) check bits to detect every single-bit error in an \(11\)-bit message.

Remark 19.4.14.

Generalizing Example 19.4.13, 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.

  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 \le 20\text{,}\) 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\text{,}\) 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?