Two codewords were sent using the Hamming 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 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 code :
Find and .
Find the generator matrix for .
List the codewords in .
What is the code rate for ?
Let be a binary repetition code.
Find a parity check matrix for .
List the cosets and coset leaders for .
Find the syndrome for each coset.
Suppose you receive the message . Use the syndrome decoding method to decode it.
Let be the binary code .
Show that is not linear.
What is ? (Since is not linear, this cannot be found by calculating the minimum weight.)
Show that satisfies the Singleton bound with equality.
Show that the weight function (on ) satisfies the triangle inequality: .
Show that , where is the function defined in Section 24.3.
Let be the repetition code of length . Show that is the parity check code of length . (This is true for arbitrary .)
Let be a linear code and let and be cosets of . Show that if and only if . (Hint: To show , it suffices to show that for every , and that for every . To show the opposite implication, use the fact that .)
Show that if is a self-dual code, then must be even.
Show that is the generating polynomial for the repetition code. (This is true for arbitrary .)
Let be a polynomial with coefficients in .
Show that is a factor of in .
The polynomial is the generating polynomial for a cyclic code code . Find the generating matrix for .
Find a parity check matrix for .
Show that , where
Show that the rows of generate .
Show that a permutation of the columns of gives the generating matrix for the Hamming code, and therefore these two codes are equivalent.
Let be the cyclic binary code of length with generating polynomial . Which of the following polynomials correspond to elements of ?
Let be the generating polynomial for a cyclic code of length , and let . Write . Show that the dual code is cyclic with generating polynomial . (The factor is included to make the highest nonzero coefficient be 1.)
Let be a binary repetition code of odd length (that is, contains two vectors, one with all 0s and one with all 1s). Show that is perfect. (Hint: Show that every vector lies in exactly one of the two spheres of radius .)
Use (a) to show that if is odd then . (This can also be proved by applying the binomial theorem to , and then observing that we’re using half of the terms.)
Let and let denote the number of points in a Hamming sphere of radius . The proof of the Gilbert-Varshamov bound constructs an code with . However, this code is probably not linear. This exercise will construct a linear code, where is the smallest integer satisfying .
Show that there exists an code .
Suppose and that we have constructed an code in (where is the finite field with elements). Show that there is a vector with for all .
Let be the subspace spanned by and . Show that has dimension and that every element of can be written in the form with and .
Let , with , be an element of , as in (c). Show that .
Show that is an code. Continuing by induction, we obtain the desired code .
Here is a technical point. We have actually constructed an code with . Show that by possibly modifying in step (b), we may arrange that for some , so we obtain an code.
Show that the Golay code is perfect.
Let be a root of the polynomial .
Using the fact that divides , show that .
Show that .
Suppose that with . Then , so there exist integers with . Use this to show that , which is a contradiction. This shows that is a primitive seventh root of unity.
Let be the binary code of length 7 generated by the polynomial . As in Section 24.8, , where is a root of . Suppose the message is received. It has one error. Use the procedure from Section 24.8 to correct the error.
Let be a cyclic code of length with generating polynomial . Assume and (as in the theorem on p. 472).
Show that .
Write . Let be a primitive th root of unity. Show that at least one of is a root of . (You may use the fact that cannot have more than roots.)
Show that .