Chapter 3 Linear Block Codes

3.1

Find, by trial and error, a set of four binary codewords of length three such that each word is at least a distance of $2$ from every other word.

Solution:

Consider the following 4 code words:

$$(0,0,0) \\ (1,0,1) \\ (0,1,1) \\ (1,1,0) \\ $$

$\square$

3.2

Find a set of $16$ binary words of length $7$ such that each word is at least a distance of $3$ from every other word. Hint: Hamming code.

Solution:

From section 1.9, equation (1.35), consider

$$[0,0,0,0,0,0,0] \\ [1,1,0,1,0,0,0] \\ [0,1,1,0,1,0,0] \\ [1,0,1,1,1,0,0] \\ [0,0,1,1,0,1,0] \\ [1,1,1,0,0,1,0] \\ [0,1,0,1,1,1,0] \\ [1,0,0,0,1,1,0] \\ [0,0,0,1,1,0,1] \\ [1,1,0,0,1,0,1] \\ [0,1,1,1,0,0,1] \\ [1,0,1,0,0,0,1] \\ [0,0,1,0,1,1,1] \\ [1,1,1,1,1,1,1] \\ [0,1,0,0,0,1,1] \\ [1,0,0,1,0,1,1] \\ $$

$\square$

3.3

Perhaps the simplest of all codes is the binary parity check code, a $(n,n−1)$code, where $k= n−1$. Given a message vector $𝐦 = (m_0,m_1, ...,m_{k−1})$, the codeword is $𝐜 = (m_0,m_1, ...,m_{k−1},b)$, where $b = \sum_{j = 0}^{k-1} m_j$ (arithmetic in $GF(2)$) is the parity bit. Such a code is called an even parity code, since all codewords have even parity — an even number of 1 bits.

(a) Determine the minimum distance for this code.

It's a linear block code, so from Theorem 3.4, we have $d_{\min} = 𝑤_{\min}$. It's not possible for a codeword to have only one $1$, so $d_{\min} = 𝑤_{\min} = 2$.

(b) How many errors can this code correct? How many errors can this code detect?

It cannot correct any error, but it can detect 1 bit error.

(c) Determine a generator matrix for this code.

Then generator matrix is an $(n-1) \times n$ matrix, the left part is an identity matrix, while the last column is all one.

(d) Determine a parity check matrix for this code.

Solution:

The parity check matrix is

$$H = [1, 1, \cdots, 1]$$

$\square$

3.4

For the $(n,1)$ repetition code, determine a parity check matrix.

Solution:

The generator matrix of the $(n,1)$ repetition code is

$$G = \begin{bmatrix} 1 & 1 & \cdots & 1 \end{bmatrix}$$

Let

$$H = \begin{bmatrix} 1 & 0 & \cdots & 0 & 1 \\ 0 & 1 & \cdots & 0 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 1 \\ \end{bmatrix}$$

Each row of $H$ is linearly independent, also we have $G H^T = 0$.

So $H$ is a parity check matrix.

$\square$

3.6

Let $\mathcal{C}_1$ be an $(n_1,k,d_1)$ binary linear systematic code with generator $G_1 = [P_1 \quad I_k]$. Let $\mathcal{C}_2$ be an $(n_2,k,d_2)$ binary linear systematic code with generator $G_2 = [P_2 \quad I_k]$. Form the parity check matrix for an $(n_1 +n_2,k)$ code as

$$H = \begin{bmatrix} & P_1^T \\ I_{n_1 + n_2 -k} & I_k \\ & P_2^T \\ \end{bmatrix}$$

Show that this code has minimum distance at least $d_1 +d_2$.

Proof:

From theorem 3.15, we have

$$\begin{align*} d_1 &\leq n_1 - k + 1\\ d_2 &\leq n_2 - k + 1\\ \end{align*}$$

We would like to prove taking any $d_1 + d_2 - 1$ columns from $H$ they must be linearly independent.

Note that

$$\begin{align*} d_1 + d_2 - 1 &\leq n_1 + n_2 - 2k + 1 \\ &\leq n_1 + n_2 - k \end{align*}$$

3.7

The generator matrix for a code over $GF(2)$is given by

$$G = \begin{bmatrix} 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ \end{bmatrix}$$

Find a generator matrix and parity check matrix for an equivalent systematic code.

Solution: We will do the generator matrix first since I only finished section 3.2.

Substract the 3rd row from the 2nd row, we have

$$\begin{bmatrix} 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ \end{bmatrix}$$

Swap the 4th and 5th row, we have

$$\begin{bmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ \end{bmatrix}$$

The substract the 1st row from the 3rd row

$$\begin{bmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ \end{bmatrix}$$

That's an generator matrix for an equivalent systematic code.

Another one from only row operations.

Substract 1st row from the 2nd row

$$\begin{bmatrix} 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ \end{bmatrix}$$

Then substract 2nd row from the 1st row

$$\begin{bmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ \end{bmatrix}$$

Then substract 3rd row from the 1st row

$$\begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ \end{bmatrix}$$

$\square$

3.8

The generator and parity check matrix for a binary code $\mathcal{C}$ are given by

$$\tag{3.23} G = \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 & 1 & 0\\ \end{bmatrix} \quad H = \begin{bmatrix} 1 & 1 & 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 0 & 1 & 1\\ \end{bmatrix}$$

This code is small enough that it can be used to demonstrate several concepts from throughout the chapter.

(a) Verify that H is a parity check matrix for this generator.

Proof:

What we need to do is to verify $G H^T = 0$. We calculate its 1st row as an example.

$$\begin{align*} G_{1,.} H^T_{.,1} &= 1×1+0×1+1×0+0×1+1×1+1×0 = 1+1=0 \\ G_{1,.} H^T_{.,2} &= 1×1+0×0+1×1+0×0+1×1+1×1 = 1+1+1+1=0 \\ G_{1,.} H^T_{.,3} &= 1×0+0×1+1×0+0×0+1×1+1×1 = 1+1=0 \\ \end{align*}$$

Furthurmore, the rows in $H$ are linearly independent. If

$$a_1 H_{1,.} + a_2 H_{2,.} + a_3 H_{3,.} = 0$$

If we look at column 4, we must have $a_1 = 0$. If we look at column 3, we must have $a_2 = 0$. Then $a_3$ must also be $0$.

$\square$

(b) Draw a logic diagram schematic for an implementation of an encoder for the nonsystematic generator G using ”and” and ”xor” gates.

Solution: I will just use verilog code instead of diagram schematic.

wire [2:0] msg;
wire [5:0] codeword;

assign codeword[0] = msg[0];
assign codeword[1] = msg[1] ^ msg[2];
assign codeword[2] = msg[0] ^ msg[1] ^ msg[2];
assign codeword[3] = msg[1];
assign codeword[4] = msg[0] ^ msg[2];
assign codeword[5] = msg[0] ^ msg[1];

$\square$

(d) List the vectors in the orthogonal complement of the code (that is, the vectors in the dual code $\mathcal{C}^{\perp}$)

Solution:

We have shown in part (a) that rows in $H$ are linearly independent, so they form a basis of $\mathcal{C}^{\perp}$. Then the vectors are

$$a_1 H_{1,.} + a_2 H_{2,.} + a_3 H_{3,.}$$

$\square$

(h) Using the generator matrix in (3.23), find the codeword with $𝐦 = [1,1,0]$ as message bits.

Solution: It's

$$c = m G = [1, 1, 0, 1, 1, 0]$$

$\square$

3.9

Let a binary systematic $(8,4)$ code have parity check equations

$$\begin{align*} c_0 &= m_1 + m_2 + m_3 \\ c_1 &= m_0 + m_1 + m_2 \\ c_2 &= m_0 + m_1 + m_3 \\ c_3 &= m_0 + m_2 + m_3 \\ \end{align*}$$

Answer the following:

(a) Determine the generator matrix $G$ for this code in systematic form. Also determine the parity check matrix $H$.

Solution:

$$G = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ \end{bmatrix}$$

In fact, $G G^T = 0$, so $H = G$.

$\square$

(b) Using Theorem 3.13, show that the minimum distance of this code is 4.

Proof:

Let $H = G$. First, take 4 columns, e.g., $1, 2, 5, 8$, and they are linearly dependent.

And any 3 columns are linearly independent. So $d_{\min} = 4$.

$\square$

(d) List the vectors in the orthogonal complement of the code (that is, the vectors in the dual code $\mathcal{C}^{\perp}$).

3.10

Show that a self-dual code has a generator matrix $G$ which satisfies $G G^T = 0$.

Proof:

Let $\mathcal{C}$ be a self-dual code, so $\mathcal{C}^{\perp} = \mathcal{C}$. Since the row of $G$ is a basis of $\mathcal{C}$, then the row of $G$ is also a basis of $\mathcal{C}^{\perp}$. That means $H = G$.

Since we have $G H^T = 0$ then we have $G G^T = 0$.

$\square$

3.20

Find the lower bound on required redundancy for the following codes.

(a) A single-error correcting binary code of length $7$.

Solution:

We use the equation

$$r \ge \log_{q} V_q(n, t).$$

In this case, $n = 7, q = 2, t = 1$.

So

$$\begin{align*} V_q(n,t) &= \sum_{j = 0}^{t} \binom{n}{j} (q-1)^{j} \\ &= \binom{7}{0} + \binom{7}{1} \\ &= 1 + 7 \\ &= 8 \end{align*}$$

So

$$r \ge \log_{2} 8 = 3$$

$\square$

(b) A single-error correcting binary code of length $15$.

We use the equation

$$r \ge \log_{q} V_q(n, t).$$

In this case, $n = 15, q = 2, t = 1$.

So

$$\begin{align*} V_q(n,t) &= \sum_{j = 0}^{t} \binom{n}{j} (q-1)^{j} \\ &= \binom{15}{0} + \binom{15}{1} \\ &= 1 + 15 \\ &= 16 \end{align*}$$

So

$$r \ge \log_{2} 16 = 4$$

$\square$

(c) A triple-error correcting binary code of length 23.

Solution:

We use the equation

$$r \ge \log_{q} V_q(n, t).$$

In this case, $n = 23, q = 2, t = 3$.

So

$$\begin{align*} V_q(n,t) &= \sum_{j = 0}^{t} \binom{n}{j} (q-1)^{j} \\ &= \binom{23}{0} + \binom{23}{1} + \binom{23}{2} + \binom{23}{3} \\ &= 1 + 23 + 253 + 1771 \\ &= 2048 \end{align*}$$

So

$$r \ge \log_{2} 2048 = 11$$

$\square$

(d) A triple-error correcting $4$-ary code (i.e., $q = 4$) of length $23$.

Solution:

We use the equation

$$r \ge \log_{q} V_q(n, t).$$

In this case, $n = 23, q = 4, t = 3$.

So

$$\begin{align*} V_q(n,t) &= \sum_{j = 0}^{t} \binom{n}{j} (q-1)^{j} \\ &= \binom{23}{0} \cdot 3^0 + \binom{23}{1} \cdot 3^1 + \binom{23}{2} \cdot 3^2 + \binom{23}{3} \cdot 3^3 \\ &= 1 + 69 + 2,277 + 47,817 \\ &= 50,164 \end{align*}$$

So

$$r \ge \log_{4} 50,164 > 7$$

So $r = 8$.

$\square$

3.21

Show that all odd-length binary repetition codes are perfect.

Proof:

First assume the length of the odd-length binary repetition code is $n = 2k+1$, then since it maps $1$-bit message to $2k+1$-bit codeword, the redundancy $r$ is $2k$.

Then we calculate the hamming bound. In this case, $n = 2k+1, q = 2, t = k$.

$$\begin{align*} V_q(n,t) &= \sum_{j = 0}^{t} \binom{n}{j} (q-1)^{j} \\ &= \binom{2k+1}{0} + \binom{2k+1}{1} + \cdots + \binom{2k+1}{k} \\ &= \frac{1}{2} 2 ^{2k+1} \\ &= 2 ^ {2k} \end{align*}$$

The hamming bound is $\log_{2} 2 ^{2k} = 2k = r$.

So it's a perfect code.

$\square$

3.22

Show that Hamming codes achieve the Hamming bound.

Proof:

For the $(7,4)$ Hamming code, it can correct $1$ bit error, so $t = 1$ and $n = 7, q = 2$,

So

$$\begin{align*} V_q(n,t) &= \sum_{j = 0}^{t} \binom{n}{j} (q-1)^{j} \\ &= \binom{7}{0} + \binom{7}{1} \\ &= 8 \\ \end{align*}$$

Then $\log_{2} 8 = 3$.

On the other hand,

$r = n - \log_{2} M = 7 - 4 = 3$.

So Hamming codes achieve the Hamming bound.

$\square$

3.25

Let $G$ be the generator matrix of an $(n,k)$ binary code $\mathcal{C}$ and let no column of $G$ be all zeros. Arrange all the codewords of $\mathcal{C}$ as rows of a $2^k ×n$ array.

(a) Show that no column of the array contains only zeros.

Let $M$ be a $2^k \times k$ matrix, each row is one of the $2^k$ messages.

And let $C = MG$, what we need to prove is that no column of $C$ is all zeros.

We will just need to show $C[:,1]$ is not all zeros.

Since $G[:,1]$ is not all zeros, then assume $G_{i,1} = 1$.

Then consider the following message:

$$m = (m_1, \cdots, m_k)$$

where only $m_i = 1$. Then $m G[:,1]$ is not all zero. If $m$ is the $l$th row in $C$, then $C_{l,1} = 1$.

So $C[:,1]$ is not all zeros.

For other columns we can use the same approach.

(b) Show that each column of the array consists of $2^{k−1}$ zeros and $2^{k−1}$ ones.

Proof:

Consider the $j$th column of $C$, and denote it $C_{.,j}$, then $C_{.,j} = M G_{.,j}$.

If $C_{i,j} = 0$, it means $M_{i,.} G_{.,j} = 0$, that is the inner product of $M_{i,.} G_{.,j}$ is $0$.

Now consider $W = \text{span}(G_{.,j})$, then $\dim W = 1$. From Theorem 2.64, $\dim W_⟂ = k - 1$. So $|W_⟂| = 2^{k−1}$.

So $C_{.,j}$ consists of $2^{k−1}$ zeros and $2^{k−1}$ ones.

$\square$

(c) Show that the set of all codewords with zeros in particular component positions forms a subspace of $\mathcal{C}$. What is the dimension of this subspace?

Proof:

Let $V$ be the set of all codewords in $\mathcal{C}$ such that particular component positions are $0$, let $c_0, c_1 \in V$. For $c_0 + c_1$, and $k c_0, k = 0, 1$ those particular component positions are still $0$. So $V$ is close under addition and scaler multiplication.

Now to the dimension of this subspace, assume the particular component positions are $j_1 < j_2 < \cdots < j_p$. Then the corresponding columns in the generator matrix are $G_{., j_1}, G_{., j_2}, \cdots, G_{., j_p}$. Let $W = \text{span}(G_{., j_1}, G_{., j_2}, \cdots, G_{., j_p})$.

Then this subspace is in fact isomorphic to $W_{\perp}$. So its dimension is $k - \dim W$.

$\square$

(d) Show that the minimum distance $d_{\min}$ of this code must satisfy the following inequality, known as the Plotkin bound:

$$d_{\min} \leq \frac{n 2^{k-1}}{2^{k}-1}$$

Proof:

From Theorem 3.4, we know $d_{\min} = 𝑤_{\min}$. Then we just need to prove

$$𝑤_{\min} (2^{k}-1) \leq n 2^{k-1}$$

Given any non-zero codeword $c \in \mathcal{C}$, $𝑤_{\min} \leq wt(c)$, and there are $2^{k}-1$ non-zero codewords. That means the total number of digit $1$ in $\mathcal{C}$ is greater of equal to $𝑤_{\min} (2^{k}-1)$.

On the other hand, from part (b), we know the the total number of digit $1$ is exactly $n 2^{k-1}$, since each column of $C$ has $2^{k-1}$ $1$s and $C$ has $n$ columns.

So the Plotkin bound follows.

$\square$

3.26

Let $Γ$ be the ensemble of all the binary systematic linear $(n,k)$ codes.

(a) Prove that a nonzero binary vector $𝐯$ is contained in exactly $2^{(k−1)(n−k)}$ of the codes in $Γ$ or it is in none of the codes in $Γ$.

Proof:

We assume that for a systematic linear $(n,k)$ code, the generator matrix $G$ is like this

$$G = [I | P]$$

Basically, $I$ is an $k \times k$ matrix and $P$ is an $k \times (n-k)$ matrix.

So for a message $m$, the codeword $c = mG = (m, p)$, where $p$ is the $1 \times (n-k)$ parity bits.

Given any nonzero vector $v = (m, p)$ where $m = (m_1, \cdots, m_k), p = (p_1, \cdots, p_{n-k})$.

If $m = (0, \cdots, 0)$ and $p \neq (0, \cdots, 0)$, then $mG = 0G = 0 \neq (m, p) = v$. So such $v$ is not contained in any code in $Γ$.

Now assume $m \neq 0$, for $p_1$, we need to find $P_{.,1}$ such that $m P_{.,1} = p_1$.

If $p_1 = 0$, then let $W = \text{span}(m)$. So $\dim W = 1$. Any vector $w$ in $W_{\perp}$ will satisfy $⟨m,w⟩ = 0$. Since $\dim W_{\perp} = (k-1)$, we know $|W_{\perp}| = 2^{k-1}$.

On the other hand, if $p_1 = 1$, then any vector $w \not\in W_{\perp}$ will satisfy $⟨m,w⟩ = 1$. $|GF(2)^k\backslash W_{\perp}| = 2^{k-1}$.

In either case, there are $2^{k-1}$ choices to satisfy $m P_{.,1} = p_1$. We can apply the same argument to $P_{.,1}, \cdots, P_{.,n-k}$.

Therefore, $v$ is contained in exactly $2^{(k−1)(n−k)}$ codes.

$\square$

(b) Using the fact that the nonzero $n$-tuples of weight $d−1$ or less can be in at most

$$2^{(k−1)(n−k)} \sum_{i = 1}^{d-1} \binom{n}{i}$$

$(n,k)$ systematic binary linear codes, show that there exists an $(n,k)$ linear code with minimum distance of at least $d$ if the following bound is satisfied:

$$\sum_{i = 1}^{d-1} \binom{n}{i} < 2^{n-k}$$

Proof:

First note, since $P$ is an $k \times (n-k)$ matrix, we have $|\Gamma| = 2^{k(n-k)}$.

If a code $\mathcal{C}$'s minimum distance is less than $d$, then it must contain a codeword $c$ such that $wt(c) < d$, i.e. $wt(c) = 1, \cdots, d-1$.

Since we can have at most $\sum_{i = 1}^{d-1}\binom{n}{i}$ distinct codewords with $wt(c) < d$, and each codeword is contained in exactly $2^{(k−1)(n−k)}$ codes, then the number of code $\mathcal{C}$ with minimum distance less that $d$ is at most

$$2^{(k−1)(n−k)} \sum_{i = 1}^{d-1} \binom{n}{i} < 2^{(k−1)(n−k)} \cdot 2^{n-k} = 2^{k(n-k)}$$

So there must be at least one code in $\Gamma$, whose distance is greater or equal to $d$.

$\square$

(c) Show that there exists an $(n,k)$ binary linear code with minimum distance at least $d$ that satisfies the following inequality:

$$2^{n-k} \leq \sum_{i = 0}^{d} \binom{n}{i}$$

This provides a lower bound on the minimum distance attainable with an $(n,k)$ linear code known as the Gilbert–Varshamov bound.

Proof:

Assume $d-1$ is the largest integer that satisfies $\sum_{i = 1}^{d-1} \binom{n}{i} < 2^{n-k}$, i.e. $\sum_{i = 1}^{d-1} \binom{n}{i} < 2^{n-k} \leq \sum_{i = 1}^{d} \binom{n}{i}$ then use part (2), we can find a $\mathcal{C} \in \Gamma$ whose distance is $d$.

And

$$\sum_{i = 0}^{d} \binom{n}{i} = 1 + \sum_{i = 1}^{d} \binom{n}{i} \geq 1 + 2^{n-k} > 2^{n-k}$$

$\square$

3.29

The $[𝐮|𝐮 +𝐯]$ construction: Let $\mathcal{C}_i, i= 1,2$ be linear binary $(n,k_i)$ block codes with generator matrix $G_i$ and minimum distance $d_i$. Define the code $\mathcal{C}$ by

$$\mathcal{C} = |\mathcal{C}_1|\mathcal{C}_1 + \mathcal{C}_2| = \{[u|u+v] : u \in \mathcal{C}_1, v \in \mathcal{C}_2\}.$$

(a) Show that $\mathcal{C}$ has the generator

$$G = \begin{bmatrix} G_1 & G_1 \\ 0 & G_2 \\ \end{bmatrix}$$

Proof:

$G_i$ is $k_i \times n$ matrix. Let $m_1$ be a $1 \times k_1$ message. Let $m_2$ be a $1 \times k_2$ message.

and $u = m_1 G_1, v = m_2 G_2$.

And

$$[m_1 | m_2] G = [m_1 G_1 + 0 | m_1 G_1 + m_2 G_2] = [u | u + v]$$

So $G$ is the generator of $\mathcal{C}$.

$\square$

(b) Show that the minimum distance of $\mathcal{C}$ is

$$d_{\min} = \min (2 d_1, d_2)$$

Proof:

Note that since $c = [u|u+v]$, then $wt(c) = wt(u) + wt(u+v)$.

If $v = 0$, then $wt(c) = 2 wt(u) \geq 2 d_1$.

If $v \neq 0$, then given any $u$. Let's treat $u, v$ as vector in $\mathbb{R}^n$.

So $wt(u+v) \geq wt(v) - ⟨u,v⟩$, and also $⟨u,v⟩ \leq wt(u)$.

So

$$wt(c) = wt(u) + wt(u+v) \geq wt(u) + (wt(v) - ⟨u,v⟩) \geq wt(v) \geq d_2$$

In either case, $wt(c) \geq \min (2 d_1, d_2)$.

Furthurmore, when $v = 0$, we can find $u$ to reach $wt(c) = 2 d_1$. when $u = 0$, we can find $v$ to reach $wt(c) = d_2$.

So $d_{\min} = \min (2 d_1, d_2)$.

A note from AI: we can use the triangle inequality in the hamming distance to prove this

$$wt(v) = d(v, 0) = d(u+v, u) \leq d(u+v, 0) + d(0, u) = wt(u+v) + wt(u) \\ \Rightarrow \\ wt(u+v) \geq wt(v) - wt(u)$$

$\square$