1.
Compute the distance between the following pairs of vectors:
Print preview
Worksheet Distance of a Code and Error Correction
In this activity, you’ll practice computing the Hamming distance between vectors and the minimum distance of a code, and you’ll begin to explore how these concepts relate to the error-detecting and error-correcting capabilities of a code.
2.
The 1972 Mariner space mission used a code to transmit images of Mars back to Earth. The scientists and engineers working on the mission expected that solar activity and atmospheric conditions would introduce errors in the transmitted data. To mitigate this problem and recover most of the pictures sent, they used the following coding scheme. The source alphabet consisted of 64 shades of gray, which were represented as 6-tuples of binary digits. For example, the shade represented by \(000000\) was black, and the shade represented by \(111111\) was white. The channel encoder then produced binary 32-tuples from these 6-tuples. The source decoder could correct up to 7 errors in any 32-tuple.
Taking the alphabet for this setup to be the binary one, what are the block length, dimension, and rate of this code? What minimum distance must this code have had to be able to correct up to 7 errors?
3.
The parity code \(C_{\oplus}\) with block length 5 is the code produced by the channel encoder that maps any 4-tuple \((a_1, a_2, a_3, a_4)\) to the 5-tuple \((a_1, a_2, a_3, a_4, b)\text{,}\) where \(b\) is chosen so that the total number of 1’s in the 5-tuple is even. Equivalently, \(b = a_1 + a_2 + a_3 + a_4 \mod 2\text{.}\)
What is the minimum distance of \(C_{\oplus}\text{?}\) Justify your answer.
4.
Discuss in your group how rate and redundancy of a code are related.
5.
Can codes be “perfect”? In other words, given a set of message vectors, can you add enough bits to correct any possible number of errors in transmission and recover the original message with 100% probability?
6.
Consider the code
\begin{gather*}
C=\{c_1,c_2,c_3,c_4\}= \{(00000), (10110), (01011), (11101) \}\text{.}
\end{gather*}
(a)
What is the minimum distance of this code and therefore how many errors can it detect and correct?
(b)
How many words (5-tuples) might be received by the decoder if any number of errors could occur during transmission of each codeword?
(c)
Find the spheres of radius 1 centered at each codeword. Do these spheres cover the entire space of 5-tuples? If not, which 5-tuples are not included in any sphere?
(d)
Suppose we receive \(\mathbf{y}=(00011)\text{.}\) What does our decoder output?
(e)
Suppose we receive \(\mathbf{y}=(11000)\text{.}\) What does our decoder output?
(f)
Suppose we receive \(\mathbf{y}=(10100)\text{.}\) What does our decoder output? If two errors were made during transmission, is it possible to know what the original codeword was? If we are only using this code for error detection, can we be sure that an error occurred?
