Two codewords were sent using the Hamming $[7\text{,}4]$ code and were received as 0100111 and 0101010. Each one contains at most one error. Correct the errors. Also, determine the 4-bit messages that were multiplied by the matrix $G$ to obtain the codewords.

An ISBN number is incorrectly written as 0-13-116093-8. Show that this is not a correct ISBN number. Find two different valid ISBN numbers such that an error in one digit would give this number. This shows that ISBN cannot correct errors.

The following is a parity check matrix for a binary $[n\text{,}k]$ code $C$:

$\left(\begin{array}{ccccc}1& 1& 1& 0& 0\\ 1& 0& 0& 1& 0\\ 0& 1& 0& 0& 1\end{array}\right)\text{.}$

1. Find $n$ and $k$.

2. Find the generator matrix for $C$.

3. List the codewords in $C$.

4. What is the code rate for $C$?

Let $C=\{(0\text{,}0\text{,}0)\text{,}(1\text{,}1\text{,}1)\}$ be a binary repetition code.

1. Find a parity check matrix for $C$.

2. List the cosets and coset leaders for $C$.

3. Find the syndrome for each coset.

4. Suppose you receive the message $(1\text{,}1\text{,}0)$. Use the syndrome decoding method to decode it.

Let $C$ be the binary code $\{(0\text{,}0\text{,}1)\text{,}(1\text{,}1\text{,}1)\text{,}(1\text{,}0\text{,}0)\text{,}(0\text{,}1\text{,}0)\}$.

1. Show that $C$ is not linear.

2. What is $d(C)$? (Since $C$ is not linear, this cannot be found by calculating the minimum weight.)

3. Show that $C$ satisfies the Singleton bound with equality.

Show that the weight function (on ${\mathbf{F}}^n$) satisfies the triangle inequality: $wt(u+v)\le wt(u)+wt(v)$.

Show that $A_q(n\text{,}n)=q$, where $A_q(n\text{,}d)$ is the function defined in Section 24.3.

Let $C$ be the repetition code of length $n$. Show that $C^{\perp }$ is the parity check code of length $n$. (This is true for arbitrary $\mathbf{F}$.)

Let $C$ be a linear code and let $u+C$ and $v+C$ be cosets of $C$. Show that $u+C=v+C$ if and only if $u-v\in C$. (Hint: To show $u+C=v+C$, it suffices to show that $u+c\in v+C$ for every $c\in C$, and that $v+c\in u+C$ for every $c\in C$. To show the opposite implication, use the fact that $u\in u+C$.)

Show that if $C$ is a self-dual $[n\text{,}k\text{,}d]$ code, then $n$ must be even.

Show that $g(X)=1+X+X^2+\cdots +X^{n-1}$ is the generating polynomial for the $[n\text{,}1]$ repetition code. (This is true for arbitrary $\mathbf{F}$.)

Let $g(X)=1+X+X^3$ be a polynomial with coefficients in ${\mathbf{Z}}_2$.

1. Show that $g(X)$ is a factor of $X^7-1$ in ${\mathbf{Z}}_2[X]$.

2. The polynomial $g(X)$ is the generating polynomial for a cyclic code $[7\text{,}4]$ code $C$. Find the generating matrix for $C$.

3. Find a parity check matrix $H$ for $C$.

4. Show that $G^{\prime }{H}^T=0$, where

   $G^{\prime }=\left(\begin{array}{ccccccc}1& 1& 0& 1& 0& 0& 0\\ 0& 1& 1& 0& 1& 0& 0\\ 0& 0& 1& 1& 0& 1& 0\\ 0& 1& 1& 1& 0& 0& 1\end{array}\right)\text{.}$

5. Show that the rows of $G^{\prime }$ generate $C$.

6. Show that a permutation of the columns of $G^{\prime }$ gives the generating matrix for the Hamming $[7\text{,}4]$ code, and therefore these two codes are equivalent.

Let $C$ be the cyclic binary code of length $4$ with generating polynomial $g(X)=X^2+1$. Which of the following polynomials correspond to elements of $C$?

$f_1(X)=1+X+X^3\text{,}{f}_2(X)=1+X+X^2+X^3\text{,}{f}_3(X)=X^2+X^3$

Let $g(X)$ be the generating polynomial for a cyclic code $C$ of length $n$, and let $g(X)h(X)=X^n-1$. Write $h(X)=b_0+b_{1}X+\cdots +X^{\mathrm{\ell }}$. Show that the dual code $C^{\perp }$ is cyclic with generating polynomial ${\tilde{h}}_r(X)=(1/b_0)(1+b_{\mathrm{\ell }-1}X+\cdots +b_1{X}^{\mathrm{\ell }-1}+b_0{X}^{\mathrm{\ell }})$. (The factor $1/b_0$ is included to make the highest nonzero coefficient be 1.)

1. Let $C$ be a binary repetition code of odd length $n$ (that is, $C$ contains two vectors, one with all 0s and one with all 1s). Show that $C$ is perfect. (Hint: Show that every vector lies in exactly one of the two spheres of radius $(n-1)/2$.)

2. Use (a) to show that if $n$ is odd then $\sum _{j=0}^{(n-1)/2}\left(\genfrac{}{}{0ex}{}{n}{j}\right)=2^{n-1}$. (This can also be proved by applying the binomial theorem to $(1+1{)}^n$, and then observing that we’re using half of the terms.)

Let $2\le d\le n$ and let $V_q(n\text{,}d-1)$ denote the number of points in a Hamming sphere of radius $d-1$. The proof of the Gilbert-Varshamov bound constructs an $(n\text{,}M\text{,}d)$ code with $M\ge q^n/V_q(n\text{,}d-1)$. However, this code is probably not linear. This exercise will construct a linear $[n\text{,}k\text{,}d]$ code, where $k$ is the smallest integer satisfying $q^k\ge q^{n-1}/V_q(n\text{,}d-1)$.

1. Show that there exists an $[n\text{,}1\text{,}d]$ code $C_1$.

2. Suppose $q^{j-1}<q^n/V_q(n\text{,}d-1)$ and that we have constructed an $[n\text{,}j-1\text{,}d]$ code $C_{j-1}$ in ${\mathbf{F}}^n$ (where $\mathbf{F}$ is the finite field with $q$ elements). Show that there is a vector $v$ with $d(v\text{,}c)\ge d$ for all $c\in C_{j-1}$.

3. Let $C_j$ be the subspace spanned by $v$ and $C_{j-1}$. Show that $C_j$ has dimension $j$ and that every element of $C_j$ can be written in the form $av+c$ with $a\in \mathbf{F}$ and $c\in C_{j-1}$.

4. Let $av+c$, with $a\ne 0$, be an element of $C_j$, as in (c). Show that $wt(av+c)=wt(v+a^{-1}c)=d(v\text{,}-a^{-1}c)\ge d$.

5. Show that $C_j$ is an $[n\text{,}j\text{,}d]$ code. Continuing by induction, we obtain the desired code $C_k$.

6. Here is a technical point. We have actually constructed an $[n\text{,}k\text{,}e]$ code with $e\ge d$. Show that by possibly modifying $v$ in step (b), we may arrange that $d(v\text{,}c)=d$ for some $c\in C_{j-1}$, so we obtain an $[n\text{,}k\text{,}d]$ code.

Show that the Golay code $G_{23}$ is perfect.

Let $\alpha$ be a root of the polynomial $X^3+X+1\in {\mathbf{Z}}_2[X]$.

1. Using the fact that $X^3+X+1$ divides $X^7-1$, show that ${\alpha }^7=1$.

2. Show that $\alpha \ne 1$.

3. Suppose that ${\alpha }^j=1$ with $1\le j<7$. Then $gcd(j\text{,}7)=1$, so there exist integers $a\text{,}b$ with $ja+7b=1$. Use this to show that ${\alpha }^1=1$, which is a contradiction. This shows that $\alpha$ is a primitive seventh root of unity.

Let $C$ be the binary code of length 7 generated by the polynomial $g(X)=1+X^2+X^3+X^4$. As in Section 24.8, $g(1)=g(\alpha )=0$, where $\alpha$ is a root of $X^3+X+1$. Suppose the message $(1\text{,}0\text{,}1\text{,}1\text{,}0\text{,}1\text{,}1)$ is received. It has one error. Use the procedure from Section 24.8 to correct the error.

Let $C\subset {\mathbf{F}}^n$ be a cyclic code of length $n$ with generating polynomial $g(X)$. Assume $0\ne C\ne {\mathbf{F}}^n$ and $p\cancel{|}n$ (as in the theorem on p. 472).

1. Show that $deg(g)\ge 1$.

2. Write $X^n-1=g(X)h(X)$. Let $\alpha$ be a primitive $n$th root of unity. Show that at least one of $1\text{,}\alpha \text{,}{\alpha }^2\text{,}\dots \text{,}{\alpha }^{n-1}$ is a root of $g(X)$. (You may use the fact that $h(X)$ cannot have more than $deg(h)$ roots.)

3. Show that $d(C)\ge 2$.