Instructions: You may type up or handwrite your work, but it must be neat, professional, and organized and it must be saved as a PDF file and uploaded to the appropriate Gradescope assignment. Use a scanner or scanning app to convert handwritten work on paper to PDF. I encourage you to type your work using the provided template.
All tasks below must have a complete solution that represents a good-faith attempt at being right to receive engagement credits. If your submission is complete and turned in on time, you will receive full engagement credit for the assignment. All other submissions will receive zero engagement credit. Read the guidelines at Grading Specifications carefully.
To abide by the class’ academic honesty policy, your work should represent your own understanding in your own words. If you work with other students, you must clearly indicate who you worked with in your submission. The same is true for using tools like generative AI although I strongly discourage you from using such tools since you need to build your own understanding here to do well on exams.
In class we claimed that the Hamming distance is a metric on the set of all n-tuples over an alphabet, \(\Sigma^n\text{.}\) Prove this claim by verifying that the Hamming distance satisfies the properties of a metric.
In this exercise, you will show that you can convert arbitrary codes into codes with slightly different parameters. In both parts below, your argument should not assume anything about the code except the given parameters. Your constructions should work for any values of the parameters and for any alphabet in the first part.
Show that if there exists an \((n,M,d)_{\Sigma}\) code with \(d\geq 2\text{,}\) then there also exists an \((n-1,M,d-1)_{\Sigma}\) code. Specifically, show how to convert the first code into the second code. This process is called puncturing a code.
For odd \(d\text{,}\) show that if an \((n,M,d)_2\) code exists, then there also exists an \((n+1,M,d+1)_2\) code. Specifically, show how to convert the first code into the second code. This process is called extending a code.
Define a binary code other than \(C_H\) with \(n=7\text{,}\)\(k=4\text{,}\) and \(d=3\text{.}\) Justify that your code has the desired parameters and that it is not \(C_H\text{.}\)
Does there exist a matrix \(\tilde{G}\) such that \(G\) and \(\tilde{G}\) have the same rowspace and \(\tilde{G}=(I_k\mid A)\) for some integer \(k\) and matrix \(A\text{?}\)
