Skip to main content

Section Solutions for Chapter 19

Solution to Exercise 19.1.5

The only string with an odd number of \(\displaystyle 1\)s is \(\displaystyle 10101\text{,}\) so it is not an allowable message, but all of the others are allowed.

Solutions to Exercise 19.2.5

19.2.5.1 The only such word is “math.”

19.2.5.3 There are many possibilities, such as “bats,” “gash,” and “many.”

19.2.5.5 We have answered this in each solution given above.

Solutions to Exercise 19.2.6

19.2.6.2 Proof. Let \(\displaystyle x\) and \(\displaystyle y\) be words of the same length. We have \(\displaystyle d(x,y)=0\) if and only if \(\displaystyle x\) and \(\displaystyle y\) differ in no positions. This means that \(\displaystyle x\) must have the same entry as \(\displaystyle y\) in every position, which means \(\displaystyle x=y\text{.}\) ◾

19.2.6.4 Proof. Let \(\displaystyle x\text{,}\) \(\displaystyle y\text{,}\) and \(\displaystyle z\) be words of the same length. Suppose that \(\displaystyle d(x,z)=k\text{,}\) so that \(\displaystyle x\) and \(\displaystyle z\) differ in \(\displaystyle k\) positions. Suppose that \(\displaystyle d(x,y)=i\text{,}\) so \(\displaystyle y\) differs from \(\displaystyle x\) in \(\displaystyle i\) positions. If \(\displaystyle i \ge k\) then since \(\displaystyle d(y,z) \ge 0\) by Exercise 19.2.6.1, we have \(\displaystyle d(x,z) \le d(x,y)+d(y,z)\text{.}\) Otherwise, there must be some list of at least \(\displaystyle k-i\) positions in which \(\displaystyle x\) differs from \(\displaystyle z\) but does not differ from \(\displaystyle y\text{.}\) In each of these positions, since \(\displaystyle y\) has the same entry as \(\displaystyle x\text{,}\) \(\displaystyle y\) must have a different entry than \(\displaystyle z\text{.}\) Therefore \(\displaystyle d(y,z) \ge k-i\text{.}\) Now \(\displaystyle d(x,y)+d(y,z)\ge i+k-i=k=d(x,z)\text{,}\) completing the proof. ◾

Solutions to Exercise 19.2.10

19.2.10.3 The minimum distance is \(\displaystyle 2\text{.}\) To see this, first note that \(\displaystyle d(01011, \ul{10}011) = 2\text{,}\) so the minimum distance is no more than \(\displaystyle 2\text{.}\) Since each of the nonzero codewords has exactly three \(\displaystyle 1\)s, its distance from \(\displaystyle 00000\) is \(\displaystyle 3\text{,}\) and its distance to any other nonzero codeword is greater than \(\displaystyle 1\text{,}\) because changing a single bit will change the number of \(\displaystyle 1\)s. So the minimum distance is at least \(\displaystyle 2\text{.}\)

Solutions to Exercise 19.2.13

19.2.13.2

  1. The code can detect \(\displaystyle 5\) errors, but not \(\displaystyle 6\) (because the number of errors detected must be less than the minimum distance).

  2. The code can correct \(\displaystyle 2\) errors (because \(\displaystyle 2\times 2 \lt 6\text{,}\) but \(\displaystyle 2 \times 3 \not\lt 6\)).

Solutions to Exercise 19.3.6

19.3.6.1 Since
\begin{equation*} G = \begin{bmatrix}I_k \\ A \end{bmatrix} = \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 1 \amp 0 \amp 0 \\ 1 \amp 0 \amp 0 \amp 1 \end{bmatrix}\text{,} \end{equation*}
we have
\begin{align*} G \begin{bmatrix} 0\\ 1\\ 0\\ 1 \end{bmatrix} \amp = \begin{bmatrix} 0\\ 1\\ 0\\ 1\\ 1\\ 1 \end{bmatrix} , \amp G \begin{bmatrix} 0\\ 0\\ 1\\ 0 \end{bmatrix} \amp = \begin{bmatrix} 0\\ 0\\ 1\\ 0\\ 0\\ 0 \end{bmatrix} , \amp G \begin{bmatrix} 1\\ 1\\ 1\\ 0 \end{bmatrix} \amp = \begin{bmatrix} 1\\ 1\\ 1\\ 0\\ 0\\ 1 \end{bmatrix} \text{.} \end{align*}
This means that \(\displaystyle 0101\) encodes as \(\displaystyle 010111\text{,}\) \(\displaystyle 0010\) encodes as \(\displaystyle 001000\text{,}\) and \(\displaystyle 0010\) encodes as \(\displaystyle 111001\text{.}\)

Solution to Exercise 19.4.5

Since \(\displaystyle G = \begin{bmatrix}I_k \\ A \end{bmatrix}\text{,}\) and the given matrix \(\displaystyle G\) has \(\displaystyle 4\) columns, we must have \(\displaystyle k = 4\text{,}\) so \(\displaystyle I_k = I_4\) has \(\displaystyle 4\) rows. Therefore, \(\displaystyle A\) is all but the first \(\displaystyle 4\) rows of \(\displaystyle G\text{,}\) which means
\begin{equation*} A = \begin{bmatrix}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*}
Since \(\displaystyle A\) is a \(\displaystyle 3 \times 4\text{,}\) matrix, we have \(\displaystyle r = 3\text{,}\) so the parity-check matrix is
\begin{equation*} P = [A \ I_r] = [A \ I_3 ] = \begin{bmatrix}1\amp 0\amp 1\amp 1\amp 1\amp 0\amp 0\\ 1\amp 0\amp 0\amp 1\amp 0\amp 1\amp 0\\ 0\amp 1\amp 1\amp 1\amp 0\amp 0\amp 1 \end{bmatrix}\text{.} \end{equation*}

Solutions to Exercise 19.4.12

19.4.12.2

  1. Yes, all six columns of the parity-check matrix are different from each other (and none of them are all \(\displaystyle 0\)), so Theorem 19.4.9 tells us that the code can correct all single-bit errors.

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

    • \(\displaystyle \displaystyle P \begin{bmatrix}0\\0\\1\\0\\0\\1 \end{bmatrix} = \begin{bmatrix}0 \\ 1 \\ 0 \end{bmatrix}. \begin{matrix} \text{ This is the th column of }P\text{, so changing the th bit corrects}\\ \text{the error. The received word }001001\text{ decodes as }0010\underline11. \end{matrix}\)

    • \(\displaystyle \displaystyle P \begin{bmatrix}1\\1\\0\\0\\1\\1 \end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ 0 \end{bmatrix}. \begin{matrix}\text{ This is }0\text{, so there is no error. The received word }110011\text{ decodes}\\ \text{as }110011.\end{matrix}\)

    • \(\displaystyle \displaystyle P \begin{bmatrix}0\\0\\0\\1\\1\\0 \end{bmatrix} = \begin{bmatrix}1 \\ 1 \\ 0 \end{bmatrix}. \begin{matrix}\text{ This is the nd column of }P\text{, so changing the nd bit corrects the} \\ \text{error. The received word }000110\text{ decodes as }0\underline10110.\end{matrix} \)

Solutions to Exercise 19.4.15

19.4.15.1 There are \(\displaystyle 2^5 - 1 = 31\) different nonzero \(\displaystyle 5\)-bit strings. Of these \(\displaystyle 31\) strings, \(\displaystyle 5\) of them have only one \(\displaystyle 1\text{.}\) Thus, there are \(\displaystyle 31 - 5 = 26\) different nonzero strings with at least two \(\displaystyle 1\)s. Therefore, we can make a \(\displaystyle 5 \times 24\) matrix \(\displaystyle A\text{,}\) such that the columns of \(\displaystyle A\) are \(\displaystyle 24\) different binary column vectors with at least two \(\displaystyle 1\)s in each column (because there are \(\displaystyle 26\) different possible columns to choose from, and we need only \(\displaystyle 24\) of them). The columns of the resulting parity-check matrix \(\displaystyle P = [A \ I_5]\) are all nonzero and distinct, so Theorem 19.4.9 tells us that the resulting binary linear code can correct every single-digit error.

Furthermore, since \(\displaystyle P\) is \(\displaystyle 5 \times 24\text{,}\) we know that \(\displaystyle r = 5\) and \(\displaystyle k = 24\text{.}\) Since \(\displaystyle r = n - k\text{,}\) this implies \(\displaystyle n = k + r = 24 + 5 = 29\text{.}\) So the code is of type \(\displaystyle (n,k) = (29, 24)\text{,}\) as desired.

19.4.15.3 Suppose \(\displaystyle P\) is the the parity-check matrix of a binary linear code of type \(\displaystyle (n,k)\) that corrects all single-bit errors, and let \(\displaystyle r = n-k\text{.}\) Then Theorem 19.4.9 tells us that the columns of \(\displaystyle P\) must be distinct (and nonzero). However, \(\displaystyle P\) is \(\displaystyle r \times n\text{,}\) and \(\displaystyle n = k + r\text{,}\) so it has \(\displaystyle k+r\) columns of length \(\displaystyle r\text{,}\) and there are only \(\displaystyle 2^r - 1\) different possible nonzero columns of length \(\displaystyle r\text{.}\) Therefore, we must have \(\displaystyle k + r \le 2^r - 1\text{.}\) Conversely, if this inequality is satisfied, then we can construct a \(\displaystyle k \times (k + r)\) parity-check matrix whose columns are all distinct and nonzero. Thus, the smallest possible number of check bits is the smallest value of \(\displaystyle r\) that satisfies the inequality \(\displaystyle k + r \le 2^r - 1\text{.}\)

Thus:

  • \(\displaystyle r = 2\) check bits suffice for \(\displaystyle k = 1\text{,}\) because \(\displaystyle k + r = 1 + 2 = 3 = 2^2 - 1 = 2^r - 1\text{.}\) (But \(\displaystyle r = 1\) check bit does not suffice, because \(\displaystyle k + r \ge 1 + 1 = 2 > 2^1 -1 = 2^r - 1\text{.}\))

  • \(\displaystyle r = 3\) check bits suffice for \(\displaystyle k = 2,3,4\text{,}\) because \(\displaystyle k + r \le 4 + 3 = 7 = 2^3 - 1 = 2^r - 1\text{.}\) (But \(\displaystyle r = 2\) check bits do not suffice, because \(\displaystyle k + r \ge 2 + 2 = 4 > 2^2 -1 = 2^r - 1\text{.}\))

  • \(\displaystyle r = 4\) check bits suffice for \(\displaystyle 5 \le k \le 11\text{,}\) because \(\displaystyle k + r \le 11 + 4 = 15 = 2^4 - 1 = 2^r - 1\text{.}\) (But \(\displaystyle r = 3\) check bits do not suffice, because \(\displaystyle k + r \ge 5 + 3 = 8 > 2^3 -1 = 2^r - 1\text{.}\))

  • \(\displaystyle r = 5\) check bits suffice for \(\displaystyle 12 \le k \le 20\text{,}\) because \(\displaystyle k + r \le 20 + 5 = 25 \lt 31 = 2^5 - 1 = 2^r - 1\text{.}\) (But \(\displaystyle r = 4\) check bits do not suffice, because \(\displaystyle k + r \ge 12 + 4 = 16 > 2^4 -1 = 2^r - 1\text{.}\))

Solutions to Exercise 19.5.3

19.5.3.1 Using Proposition 19.5.2, we have \(\displaystyle v=10\text{,}\) \(\displaystyle k-2=4\) so that \(\displaystyle k=6\text{,}\) and \(\displaystyle \lambda=1\text{.}\) The question is asking us for \(\displaystyle b\text{.}\) Using \(\displaystyle bk(k-1)=\lambda v(v-1)\) gives \(\displaystyle 30b=90\) so \(\displaystyle b=3\text{.}\) Such a code will have only \(\displaystyle 3\) words.