24.12 Exercises

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

An ISBN number is incorrectly written as 0131160938. 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{,}\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{.}$
Find $n$ and $k$.
Find the generator matrix for $C$.
List the codewords in $C$.
What is the code rate for $C$?

Let $C=\{(0\text{,}\text{}0\text{,}\text{}0)\text{,}\text{}(1\text{,}\text{}1\text{,}\text{}1)\}$ be a binary repetition code.
Find a parity check matrix for $C$.
List the cosets and coset leaders for $C$.
Find the syndrome for each coset.
Suppose you receive the message $(1\text{,}\text{}1\text{,}\text{}0)$. Use the syndrome decoding method to decode it.

Let $C$ be the binary code $\{(0\text{,}\text{}0\text{,}\text{}1)\text{,}\text{}(1\text{,}\text{}1\text{,}\text{}1)\text{,}\text{}(1\text{,}\text{}0\text{,}\text{}0)\text{,}\text{}(0\text{,}\text{}1\text{,}\text{}0)\}$.
Show that $C$ is not linear.
What is $d(C)$? (Since $C$ is not linear, this cannot be found by calculating the minimum weight.)
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{,}\text{}n)=q$, where ${A}_{q}(n\text{,}\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 $uv\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 selfdual $[n\text{,}\text{}k\text{,}\text{}d]$ code, then $n$ must be even.

Show that $g(X)=1+X+{X}^{2}+\cdots +{X}^{n1}$ is the generating polynomial for the $[n\text{,}\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}$.
Show that $g(X)$ is a factor of ${X}^{7}1$ in ${\mathbf{Z}}_{2}[X]$.
The polynomial $g(X)$ is the generating polynomial for a cyclic code $[7\text{,}\text{}4]$ code $C$. Find the generating matrix for $C$.
Find a parity check matrix $H$ for $C$.
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{.}$
Show that the rows of ${G}^{\prime}$ generate $C$.
Show that a permutation of the columns of ${G}^{\prime}$ gives the generating matrix for the Hamming $[7\text{,}\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{,}\text{}\phantom{\rule{1em}{0ex}}{f}_{2}(X)=1+X+{X}^{2}+{X}^{3}\text{,}\text{}\phantom{\rule{1em}{0ex}}{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.)

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 $(n1)/2$.)
Use (a) to show that if $n$ is odd then $\sum _{j=0}^{(n1)/2}\left(\genfrac{}{}{0ex}{}{n}{j}\right)={2}^{n1}$. (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{,}\text{}d1)$ denote the number of points in a Hamming sphere of radius $d1$. The proof of the GilbertVarshamov bound constructs an $(n\text{,}\text{}M\text{,}\text{}d)$ code with $M\ge {q}^{n}/{V}_{q}(n\text{,}\text{}d1)$. However, this code is probably not linear. This exercise will construct a linear $[n\text{,}\text{}k\text{,}\text{}d]$ code, where $k$ is the smallest integer satisfying ${q}^{k}\ge {q}^{n1}/{V}_{q}(n\text{,}\text{}d1)$.
Show that there exists an $[n\text{,}\text{}1\text{,}\text{}d]$ code ${C}_{1}$.
Suppose ${q}^{j1}<\text{\hspace{0.17em}}{q}^{n}/{V}_{q}(n\text{,}\text{}d1)$ and that we have constructed an $[n\text{,}\text{}j1\text{,}\text{}d]$ code ${C}_{j1}$ 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{,}\text{}c)\ge d$ for all $c\in {C}_{j1}$.
Let ${C}_{j}$ be the subspace spanned by $v$ and ${C}_{j1}$. 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}_{j1}$.
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{,}\text{}{a}^{1}c)\ge d$.
Show that ${C}_{j}$ is an $[n\text{,}\text{}j\text{,}\text{}d]$ code. Continuing by induction, we obtain the desired code ${C}_{k}$.
Here is a technical point. We have actually constructed an $[n\text{,}\text{}k\text{,}\text{}e]$ code with $e\ge d$. Show that by possibly modifying $v$ in step (b), we may arrange that $d(v\text{,}\text{}c)=d$ for some $c\in {C}_{j1}$, so we obtain an $[n\text{,}\text{}k\text{,}\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]$.
Using the fact that ${X}^{3}+X+1$ divides ${X}^{7}1$, show that ${\alpha}^{7}=1$.
Show that $\alpha \ne 1$.
Suppose that ${\alpha}^{j}=1$ with $1\le j<7$. Then $gcd(j\text{,}\text{}7)=1$, so there exist integers $a\text{,}\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{,}\text{}0\text{,}\text{}1\text{,}\text{}1\text{,}\text{}0\text{,}\text{}1\text{,}\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\overline{)}n$ (as in the theorem on p. 472).
Show that $deg(g)\ge 1$.
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{,}\text{}\alpha \text{,}\text{}{\alpha}^{2}\text{,}\text{}\dots \text{,}\text{}{\alpha}^{n1}$ is a root of $g(X)$. (You may use the fact that $h(X)$ cannot have more than $deg(h)$ roots.)
Show that $d(C)\ge 2$.