Introduction to Algebraic Coding Theory

Find the Hamming weight of each code word in Table 29.1 (the code words of the Hamming $(7,4)$ code of Example 1):

Find the Hamming distance between the following pairs of vectors: $\left\{ 1101, 0111\right\}$, $\left\{ 0220, 1122\right\}$, $\left\{ 11101, 00111\right\}$.

Referring to Example 1, use the nearest-neighbor method to decode the received words $0000110$ and $1110100$.

For any vector space $V$ and any $u, v, w$ in $F^n$, prove that the Hamming distance has the following properties.

Determine the $(6, 3)$ binary linear code with generator matrix

Show that for binary vectors, $\mathrm{wt}(u + v) \ge \mathrm{wt}(u) = \mathrm{wt}(v)$ and equality occurs if and only if for all $i$ the $i$th component of $u$ is $1$ whenever the $i$th component of $v$ is $1$.

If the minimum weight of any nonzero code word is $2$, what can we say about the error-detecting capability of the code?

Suppose that $C$ is a linear code with Hamming weight $3$ and that $C'$ is one with Hamming weight $4$. What can $C'$ do that $C$ can't?

Let $C$ be a binary linear code. Show that the code words of even weight form a subcode of $C$. (A subcode of a code is a subset of the code that is itself a code.)

Let

What is the error-correcting capability of $C$? What is the error-detecting capability of $C$?

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

Can the code correct any single error?

Use the generator matrix

to construct a $(4, 2)$ ternary linear code. What is the parity- check matrix for this code? What is the error-correcting capability of this code? What is the error-detecting capability of this code? Use parity-check decoding to decode the received word $1201$.

Find all code words of the $(7, 4)$ binary linear code whose generator matrix is

Find the parity-check matrix of this code. Will this code correct any single error?

Show that in a binary linear code, either all the code words end with $0$, or exactly half end with $0$. What about the other components?

Suppose that a code word $v$ is received as the vector $u$. Show that coset decoding will decode $u$ as the code word $v$ if and only if $u - v$ is a coset leader.

Consider the binary linear code

Construct a standard array for $C$. Use nearest-neighbor decoding to decode $11101$ and $01100$. If the received word $11101$ has exactly one error, can we determine the intended code word? If the received word $01100$ has exactly one error, can we determine the intended code word?

Construct a $(6, 3)$ binary linear code with generator matrix

Decode each of the received words

by the following methods:

Suppose that the minimum weight of any nonzero code word in a linear code is $6$. Discuss the possible options for error correction and error detection.

Using the code and the parity-check matrix given in Example 10, show that parity-check matrix decoding cannot detect any multiple errors (i.e., two or more errors).

Suppose that the last row of a standard array for a binary linear code is

Determine the code.

How many code words are there in a $(6, 4)$ ternary linear code? How many possible received words are there for this code?

If the parity-check matrix for a binary linear code is

will the code correct any single error? Why?

Suppose that the parity-check matrix for a ternary code is

Can the code correct all single errors? Give a reason for your answer.

Prove that for nearest-neighbor decoding, the converse of Theorem 29.2 is true.

Can a $(6, 3)$ binary linear code be double-error-correcting using the nearest-neighbor method? Do not assume that the code is systematic.

Prove that there is no $2 \times 5$ standard generator matrix $G$ that will produce a $(5, 2)$ linear code over $Z_3$ capable of detecting all possible triple errors.

Why can't the nearest-neighbor method with a $(4, 2)$ binary linear code correct all single errors?

Suppose that one row of a standard array for a binary code is

Determine the row that contains $100001$.

Use the field $F = Z_2[x]/\langle x^2 + x + 1 \rangle$ to construct a $(5, 2)$ linear code that will correct any single error.

Find the standard generator matrix for a $(4, 2)$ linear code over $Z_3$ that encodes $20$ as $2012$ and $11$ as $1100$. Determine the entire code and the parity-check matrix for the code. Will the code correct all single errors?

Assume that $C$ is an $(n, k)$ binary linear code and that, for each position $i = 1, 2, \ldots , n$, the code $C$ has at least one vector with a $1$ in the $i$th position. Show that the average weight of a code word is $n/2$.

Let $C$ be an $(n, k)$ linear code over $F$ such that the minimum weight of any nonzero code word is $2t + 1$. Show that not every vector of weight $t+1$ in $F^n$ can occur as a coset leader.

Let $C$ be an $(n, k)$ binary linear code over $F = Z_2$. If $v \in F^n$ but $v \notin C$, show that $C \cup (v + C)$ is a linear code.

Let $C$ be a binary linear code. Show that either every member of $C$ has even weight or exactly half the members of $C$ have even weight. (Compare with Exercise 27 in Chapter 5.)

Let $C$ be an $(n, k)$ linear code. For each $i$ with $1 \le i \le n$, let $C_i = \left\{ v \in C \mid \text{the } i\text{th component of } v \text{ is } 0\right\}$. Show that $C_i$ is a subcode of $C$.