Problem Set M1

Print preview

Worksheet Problem Set M1

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.

🔗

1.

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.

🔗

(a)

\(d(x,y)\geq 0\) (positive semidefinite)

🔗

Solution.

The Hamming distance \(d(x,y)\) counts the number of positions where the n-tuples \(x\) and \(y\) differ, so this number is always non-negative.

🔗

(b)

\(d(x,y)=0\) if and only if \(x=y\)

🔗

Solution.

If \(x=y\text{,}\) then there are no positions where \(x\) and \(y\) differ, so \(d(x,y)=0\text{.}\) Conversely, if \(d(x,y)=0\text{,}\) then there are no positions where \(x\) and \(y\) differ, which means \(x=y\text{.}\)

🔗

(c)

\(d(x,y)=d(y,x)\) (symmetric)

🔗

Solution.

Counting the positions where \(x\) and \(y\) differ is the same as counting the positions where \(y\) and \(x\) differ, so \(d(x,y)=d(y,x)\text{.}\)

🔗

(d)

\(d(x,z) \leq d(x,y) + d(y,z)\) (triangle inequality)

🔗

Solution.

This is the trickiest of the properties to verify, so let’s be careful. Fix vectors \(x,z \in \Sigma^n\text{.}\) To show that \(d(x,z)\leq d(x,y)+d(y,z)\) for any \(y \in \Sigma^n\text{,}\) we will show that each position where \(x\) and \(z\) differ is either a position where \(x\) and \(y\) differ or a position where \(y\) and \(z\) differ (or both). Since the right hand side counts all such positions, with repetition for positions where both pairs differ, this will establish the inequality.

🔗

So, let \(i\) be a position where \(x\) and \(z\) differ, hence \(x_i\neq z_i\text{.}\) If \(y_i \neq x_i\text{,}\) we are done, since then this position is counted by \(d(x,y)\text{.}\) Otherwise, we have \(y_i = x_i\text{,}\) and since \(x_i \neq z_i\text{,}\) it follows that \(y_i \neq z_i\text{,}\) so this position is counted by \(d(y,z)\text{.}\) In either case, the position \(i\) is counted by the right hand side, completing the proof.

🔗

2.

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.

🔗

(a)

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.

🔗

Solution.

Let \(C\) be an \((n,M,d)_{\Sigma}\) code. To puncture the code, we will remove the last symbol from each codeword in \(C\text{.}\) Define the new code \(C'\) by:

\begin{gather*} C' = \{ (x_1, x_2,\ldots, x_{n-1}) \mid (x_1,x_2,\ldots,x_n) \in C \} \end{gather*}

🔗

Now we can analyze the properties of \(C'\text{.}\) First, we reduced the length of each codeword by 1, so \(C'\) has block length \(n-1\) as desired. Second, we claim that this process does not change the number of codewords. If two distinct codewords \(x,y\in C\) became the same codeword in \(C'\) after puncturing, then \(x\) and \(y\) would have to differ only in the last position. But this means \(d(x,y)=1\text{,}\) contradicting the assumption that \(C\) has minimum distance at least 2. Thus, the number of codewords in \(C'\) is still \(M\text{.}\)

🔗

Finally, we need to show that the minimum distance of \(C'\) is at least \(d-1\text{.}\) Suppose to the contrary that the minimum distance of \(C'\) is \(d-2\) or less. Then there are distinct codewords \(x', y' \in C'\) such that

\begin{gather*} d(x',y')\leq d-2 \text{.} \end{gather*}

That means that \(x'\) and \(y'\) differ in at most \(d-2\) positions. Let \(x,y \in C\) be the codewords that produced \(x'\) and \(y'\) by puncturing. Since \(x\) and \(y\) differ in at most \(d-2\) positions in the first \(n-1\) symbols, they can differ in at most one additional position (the last position). Thus, we have

\begin{gather*} d(x,y)\leq d-1 \text{,} \end{gather*}

a contradiction. Therefore, the minimum distance of \(C'\) is at least \(d-1\text{.}\) Actually, it is possible that puncturing does not change the minimum distance at all and \(d(C')=d\) (think about why!), but we have shown that \(d(C')\geq d-1\text{,}\) as desired. So we have constructed an \((n-1,M,d-1)_{\Sigma}\) code \(C'\) from the given \((n,M,d)_{\Sigma}\) code \(C\text{.}\)

🔗

(b)

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.

🔗

Solution.

Let \(C\) be an \((n,M,d)_2\) code with odd \(d\text{.}\) To extend the code, we will add a parity bit to each codeword in \(C\text{.}\) Define the new code \(C'\) by:

\begin{gather*} C' = \{ (x_1, x_2,\ldots, x_{n}, x_1+x_2+\ldots+x_{n}) \mid (x_1,x_2,\ldots,x_n) \in C \} \end{gather*}

where as usual the addition is modulo 2.

🔗

Now we can analyze the properties of \(C'\text{.}\) First, we increased the length of each codeword by 1, so \(C'\) has block length \(n+1\) as desired. Second, since we are simply appending a new bit to each codeword based on the existing bits, the number of codewords in \(C'\) is still \(M\text{.}\)

🔗

Finally, we need to show that the minimum distance of \(C'\) is at least \(d+1\text{.}\) To prove this, we will show that for any two distinct codewords \(x,y \in C\text{,}\) the corresponding codewords \(x',y' \in C'\) differ in at least \(d+1\) positions. Since \(C\) has minimum distance \(d\text{,}\) we know that \(x\) and \(y\) differ in at least \(d\) positions. First, if \(x\) and \(y\) differ in \(d+1\) or more positions, then the resulting codewords \(x'\) and \(y'\) also differ in those same positions, so they differ in at least \(d+1\) positions. So suppose they differ in exactly \(d\) positions, say \(i_1, i_2, \ldots, i_d\text{.}\) We now need to show that

\begin{align*} x_{i_1}+x_{i_2}+\ldots +x_{i_d} \neq y_{i_1}+y_{i_2}+\ldots+y_{i_d} \amp \end{align*}

since the sums of the other digits are the same for both codewords.

🔗

Since this is a binary code, that means we need to show that one of these is 0 and the other is 1. But each sum is 1 if it has an odd number of 1s and 0 otherwise. Since \(x\) and \(y\) differ in each of these \(d\) positions, the total number of 1s in these positions across both codewords is \(d\text{.}\) Since \(d\) is odd, one of the codewords must have an odd number of 1s in these positions and the other must have an even number of 1s. Therefore, one of the sums is 1 and the other is 0, as desired. Thus, \(x'\) and \(y'\) differ in at least \(d+1\) positions and the minimum distance of \(C'\) is at least \(d+1\text{.}\) So we have constructed an \((n+1,M,d+1)_2\) code \(C'\) from the given \((n,M,d)_2\) code \(C\text{.}\)

🔗

3.

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{.}\)

🔗

Solution.

There are a variety of solutions to this problem. The easiest is to just insert the message bits into different positions than in \(C_H\text{.}\) Then all of the parameters remain the same, but the code is different because the codewords are different. We defined \(C_H\) as the set

\begin{align*} \{ (x_1,x_2,x_3,x_4, x_2+x_3+x_4, x_1+x_3+x_4, x_1+x_2+x_4) \mid x_1,x_2,x_3,x_4 \in \F_2 \} \amp \text{.} \end{align*}

🔗

Instead we might define the code

\begin{align*} C = \{(x_1,x_2, x_2+x_4+x_7,x_4, x_1+x_4+x_7, x_1+x_2+x_7 ,x_7) \mid x_1,x_2,x_3,x_4 \in \F_2\} \amp \text{.} \end{align*}

The same arguments that we used to show that \(C_H\) has \(n=7\text{,}\) \(k=4\text{,}\) and \(d=3\) apply here as well, so this code also has the desired parameters. However, it is different from \(C_H\) because the codewords are different (without using what we learned about linear codes you can see this by listing all sixteen codewords of each code and observing that they are not the same set). Or we can give the generator matrices for these codes as given and then row reduce to show they generate different codes:

\begin{align*} G_{C_H} \amp = \begin{bmatrix} 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \\ 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \\ \end{bmatrix} \\ G_C \amp = \begin{bmatrix} 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \\ 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \amp 0 \\ 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1 \\ \end{bmatrix} \end{align*}

🔗

The former is already in reduced row echelon form, while the latter row reduces to

\begin{align*} \begin{bmatrix} 1 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \\ 0 \amp 1 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \\ 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1 \\ 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \\ \end{bmatrix} \end{align*}

which is different from \(G_{C_H}\text{,}\) confirming that these are different codes.

🔗

4.

Explain why in any binary linear code either all codewords begin with a 0 or exactly half of the codewords begin with a 0.

🔗

Solution.

Let \(C\) be a binary linear code. We prove the statement by showing that if there is at least one codeword that begins with a 1, then exactly half of the codewords begin with a 0 (if no such codeword exists, then all codewords begin with a 0, so the statement holds).

🔗

Define the map \(f:C\to\F_2\) by \(f(x_1,\ldots,x_n) = x_1\text{,}\) the projection map onto the first coordinate of the code. This is a linear map, since for any \(x,y \in C, a \in \F_2\text{,}\) we have

\begin{align*} f(x+y) \amp= f(x_1+y_1,\ldots,x_n+y_n)=x_1+y_1=f(x)+f(y) \\ f(ax)\amp =f(ax_1,\ldots,ax_n)=ax_1=af(x) \end{align*}

(note that over \(\F_2\text{,}\) the scalar multiplication is condition for linear maps is trivial since the only scalars are 0 and 1).

🔗

Now the rank-nullity theorem tells us that the dimension of the kernel of \(f\) plus the dimension of the image of \(f\) is equal to the dimension of \(C\text{.}\) Since we are assuming that there is at least one codeword that begins with a 1, the image of \(f\) is all of \(\F_2\text{,}\) which has dimension 1 over itself. Therefore, the dimension of the kernel of \(f\) is one less than the dimension of \(C\text{.}\) The kernel of \(f\) is exactly all of the codewords that begin with a 0, so the number of such codewords is

\begin{equation*} 2^{\dim(\ker(f))} = 2^{\dim(C)-1} = \frac{1}{2}2^{\dim(C)} = \frac{1}{2}|C|\text{,} \end{equation*}

as desired.

🔗

5.

In this exercise, you will work with the subset \(S\subset \Z_{5}^5\) defined by

\begin{equation*} S=\{ (0,1,2,3,4), (1,1,1,1,1), (2,1,3,4,1), (4,2,2,3,3) \} \end{equation*}

🔗

(a)

Give a matrix \(G\) whose rowspace is the subspace of \(\Z_{5}^5\) spanned by the vectors in \(S\)

🔗

Solution.

Lots of possible responses here depending on how far you row reduce. The key is to form the matrix with the vectors in \(S\) as the rows and then row reduce to find a basis for the rowspace. In reduced row echelon form, the matrix \(G\) is

\begin{align*} \begin{bmatrix} 1 \amp 0 \amp 0 \amp 3 \amp 3\\ 0 \amp 1 \amp 0 \amp 3 \amp 2 \\ 0 \amp 0 \amp 1 \amp 0 \amp 1 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ \end{bmatrix} \amp \end{align*}

🔗

(b)

Give a matrix whose rows span \(\ker(G)\)

🔗

Solution.

From the reduced row echelon form of \(G\text{,}\) we can read off the solutions to \(G\mathbf{x}=0\text{.}\) These must satisfy the equations

\begin{align*} x_1 \amp= 2x_4+2x_5\\ x_2 \amp = 2x_4+3x_5\\ x_3 \amp = 4x_5 \end{align*}

One such matrix \(H\) is

\begin{align*} \begin{bmatrix} 2 \amp 2 \amp 0 \amp 1 \amp 0\\ 2 \amp 3 \amp 4 \amp 0 \amp 1 \\ \end{bmatrix}\amp \text{.} \end{align*}

🔗

(c)

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{?}\)

🔗

Solution.

Yes. From the reduced row echelon form of \(G\text{,}\) we can see that the first three columns contain leading 1s, so we can take those as the identity portion. Thus, the unique such matrix \(\tilde{G}\) is the reduced row echelon form given above with

\begin{align*} A = \begin{bmatrix} 3 \amp 3\\ 3 \amp 2 \\ 0 \amp 1 \end{bmatrix} \amp \text{.} \end{align*}

🔗

Prev Top Next

Print preview

Worksheet Problem Set M1

1.

(a)

(b)

(c)

(d)

2.

(a)

(b)

3.

4.

5.

(a)

(b)

(c)

Worksheet Problem Set M1