Question

See Exercise 53 for some background. When information is transmitted, there may be some errors in the communication. We present a method of adding extra information to messages so that most errors that occur during transmission can be detected and corrected. Such methods are referred to as error-correcting codes. (Compare these with codes whose purpose is to conceal information.) The pictures of man’s first landing on the moon (1969) were televised just as they had been received and were not very clear, since they contained many errors induced during transmission. On later missions, much clearer error-corrected pictures were obtained.

In computers, information is stored and processed in the form of string of binary digits, 0 and 1. This stream of binary digits is often broken up into “blocks” of eight binary digits (bytes). For the sake of simplicity we will work with blocks of only four binary digits (i.e., with vectors in ${\mathbf{F}}^{\mathbf{4}}$), for example

$\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{|}\mathbf{1}\mathbf{}\mathbf{0}\mathbf{}\mathbf{1}\mathbf{}\mathbf{1}\mathbf{|}\mathbf{}\mathbf{1}\mathbf{}\mathbf{0}\mathbf{}\mathbf{0}\mathbf{}\mathbf{1}\mathbf{}\mathbf{|}\mathbf{1}\mathbf{}\mathbf{0}\mathbf{}\mathbf{1}\mathbf{}\mathbf{0}\mathbf{}\mathbf{|}\mathbf{}\mathbf{1}\mathbf{}\mathbf{0}\mathbf{}\mathbf{1}\mathbf{}\mathbf{1}\mathbf{|}\mathbf{}\mathbf{1}\mathbf{}\mathbf{0}\mathbf{}\mathbf{0}\mathbf{}\mathbf{0}\mathbf{.}\mathbf{.}\mathbf{.}$

Suppose these vectors in ${\mathit{F}}^{\mathbf{4}}$have to be transmitted from one computer to another, say, from a satellite to ground control in Kourou, French Guiana (the station of the European Space Agency). A vector $\overrightarrow{\mathbf{u}}$in ${\mathit{F}}^{\mathbf{4}}$is first transformed into a vector $\overrightarrow{\mathbf{v}}\mathbf{=}\mathit{M}\overrightarrow{\mathbf{u}}\mathbf{}\mathbf{in}\mathbf{}{\mathit{F}}^{\mathbf{7}}$ , where M is the matrix you found in Exercise 53. The last four entries of $\overrightarrow{\mathbf{v}}$are just the entries of $\overrightarrow{\mathbf{u}}$; the first three entries of $\overrightarrow{\mathbf{v}}$are added to detect errors. The vector is now transmitted to Kourou. We assume that at most one error will occur during transmission; that is, the vector $\overrightarrow{\mathbf{\omega }}$received in Kourou will be either $\overrightarrow{\mathbf{v}}$(if no error has occurred) or $\overrightarrow{\mathbf{\omega }}\mathbf{=}\overrightarrow{\mathbf{v}}\mathbf{+}\overrightarrow{\mathbf{e}}$(if there is an error in the th component of the vector).

(a) Let Hbe the Hamming matrix introduced in Exercise 53. How can the computer in Kourou use $\mathit{H}\overrightarrow{\mathbf{\omega }}$to determine whether there was an error in the transmission? If there was no error, what is $\mathit{H}\overrightarrow{\mathbf{\omega }}$? If there was an error, how can the computer determine in which component the error was made?

(b) Suppose the vector

$\overrightarrow{\mathbf{\omega }}\mathbf{=}\mathbf{}\mathbf{\left[}\begin{array}{c}\mathbf{1}\\ \mathbf{0}\\ \mathbf{1}\\ \mathbf{0}\\ \mathbf{1}\\ \mathbf{0}\\ \mathbf{0}\end{array}\mathbf{\right]}$

is received in Kourou. Determine whether an error was made in the transmission and, if so, correct it. (That is find $\overrightarrow{\mathbf{v}}\mathbf{}\mathbf{and}\mathbf{}\overrightarrow{\mathbf{u}}$.)

Short answer

(a) By multiplying matrix H to some error vector $\overrightarrow{\omega }$, we will get column of matrix H so in that part of initial vector an error occurred.

(b)The vectors $\overrightarrow{v}$and $\overrightarrow{u}$are $\overrightarrow{v}=\left[\begin{array}{c}1\\ 0\\ 1\\ 0\\ 1\\ 0\\ 1\end{array}\right],\overrightarrow{u}=\left[\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}\right]$,

Step-by-step solution

To define kernel of linear transformation

The kernel of linear transformation is defined as follows:

The kernel of a linear transformation $T\left(\overrightarrow{x}\right)=A\overrightarrow{x}\mathrm{from}{R}^m\mathrm{to}{R}^n$consists of all zeros of the transformation, i.e., the solutions of the equations $T\left(\overrightarrow{x}\right)=A\overrightarrow{x}=0$.

It is denoted by ker(T) or ker(A).

(a)Tofind the component of the error

From the Exercise 53, we know that im$\left(M\right)=ker\left(H\right)$.

Let $\overrightarrow{u}$be the initial vector.

$\therefore \overrightarrow{v}=M\left(\overrightarrow{u}\right)$

Also, from previous Exercise, we have,

$H\left(M\overrightarrow{u}\right)=0$

Therefore, if an error occurs and vector $\overrightarrow{v}$becomes vector $\overrightarrow{\omega }$such that .

$H\left(\overrightarrow{\omega }\right)\ne 0$

If computer does not get 0 by applying matrix to given vector, we have,

$$\begin{gathered} H\left(\overrightarrow{v}+e_i\right)=H\left(\overrightarrow{v}\right)+H\left(\overrightarrow{e_i}\right)....(\because bylinearityproperty) \\ =H\left(\overrightarrow{e_i}\right)....(\because \overrightarrow{v}\in ker(H)\Rightarrow H\left(\overrightarrow{v}\right)=0 \end{gathered}$$

Hence, on multiplying matrix H to some error vector$\overrightarrow{\omega }$ , we will get column of matrix H so in that part of initial vector$\overrightarrow{v}$ an error occurred.

(b) To find the error in the transmission

We have vector$\overrightarrow{\omega }$ as follows:

role="math" localid="1660644503180" $\overrightarrow{\omega }=\left[\begin{array}{c}1\\ 0\\ 1\\ 0\\ 1\\ 0\\ 0\end{array}\right]$

By applying matrix H , we have,

$$\begin{gathered} H=\left[\begin{array}{ccccccc}1& 0& 0& 1& 0& 1& 1\\ 0& 1& 0& 1& 1& 0& 1\\ 0& 0& 1& 1& 1& 1& 0\end{array}\right]\left[\begin{array}{c}1\\ 0\\ 1\\ 0\\ 1\\ 0\\ 0\end{array}\right] \\ H=\left[\begin{array}{c}1\\ 1\\ 2\end{array}\right] \end{gathered}$$

But since here, we are using binary digits 0 and 1, we will use 1 for odd numbers and 0 for even numbers.

Thus, above column matrix becomes,

$H=\left[\begin{array}{c}1\\ 1\\ 0\end{array}\right]$

We can see that there is same vector as in the 7^th column vector of matrix H .

Therefore, there is an error in that row of vector$\overrightarrow{\omega }$ .

Thus, the vector$\overrightarrow{v}$ is given by,

$\overrightarrow{V}=\left[\begin{array}{c}1\\ 0\\ 1\\ 0\\ 1\\ 0\\ 1\end{array}\right]$

By solving the system,$M\left(\overrightarrow{u}\right)=\overrightarrow{v}$ , we get,

$\overrightarrow{u}=\left[\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}\right]$