Solution Found!
Solved: In Exercises 53 and 54, we will work with the binary digits (or bits) 0 and 1
Chapter 3, Problem 54(choose chapter or problem)
(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 (in 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.
ln computers, information is stored and processed in the form of strings 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 \(\mathbb{F}^{4}\)), for example,
...| 1011 | 1001 | 1010 | 1011 | 1 0 0 0 I ....
Suppose these vectors in \(\mathbb{F}^{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 \(\vec{u}\) in \(\mathbb{F}^{4}\)) is first transformed into a vector \(\vec{v}=M \vec{u} \text { in } \mathbb{F}^{7}\), where M is the matrix you found in Exercise 53. The last four entries of \(\vec{v}\) are just the entries of \(\vec{u}\); the first three entries of \(\vec{v}\) are added to detect errors. The vector \(\vec{v}\) is now transmitted to Kourou. We assume that at most one error will occur during transmission; that is, the vector \(\vec{w}\) received in Kourou will be either \(\vec{v}\) (if no error has occurred) or \(\vec{w}=\vec{v}+\vec{e}_{i}\) (if there is an error in the zth component of the vector).
a. Let H be the Hamming matrix introduced in Exercise 53. How can the computer in Kourou use \(H \vec{w}\) to determine whether there was an error ifl the transmission? If there was no error, what is \(H \vec{w}\)? If there was an error, how can the computer determine in which component the error was made?
b. Suppose the vector
\(\vec{w}=\left[\begin{array}{l}
1 \\
0 \\
1 \\
0 \\
1 \\
0 \\
0
\end{array}\right]\)
is received in Kourou. Determine whether an error was made in the transmission and, if so, correct it. (That is, find \(\vec{v}\) and \(\vec{u}\).)
Questions & Answers
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 (in 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.
ln computers, information is stored and processed in the form of strings 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 \(\mathbb{F}^{4}\)), for example,
...| 1011 | 1001 | 1010 | 1011 | 1 0 0 0 I ....
Suppose these vectors in \(\mathbb{F}^{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 \(\vec{u}\) in \(\mathbb{F}^{4}\)) is first transformed into a vector \(\vec{v}=M \vec{u} \text { in } \mathbb{F}^{7}\), where M is the matrix you found in Exercise 53. The last four entries of \(\vec{v}\) are just the entries of \(\vec{u}\); the first three entries of \(\vec{v}\) are added to detect errors. The vector \(\vec{v}\) is now transmitted to Kourou. We assume that at most one error will occur during transmission; that is, the vector \(\vec{w}\) received in Kourou will be either \(\vec{v}\) (if no error has occurred) or \(\vec{w}=\vec{v}+\vec{e}_{i}\) (if there is an error in the zth component of the vector).
a. Let H be the Hamming matrix introduced in Exercise 53. How can the computer in Kourou use \(H \vec{w}\) to determine whether there was an error ifl the transmission? If there was no error, what is \(H \vec{w}\)? If there was an error, how can the computer determine in which component the error was made?
b. Suppose the vector
\(\vec{w}=\left[\begin{array}{l}
1 \\
0 \\
1 \\
0 \\
1 \\
0 \\
0
\end{array}\right]\)
is received in Kourou. Determine whether an error was made in the transmission and, if so, correct it. (That is, find \(\vec{v}\) and \(\vec{u}\).)
ANSWER:Step 1 of 4
a). If there is no error, then \(\vec{w}=\vec{v}=M \vec{u} \text { and } H \vec{w}=H(M \vec{u})=\overrightarrow{0}\),