1. Describe how to construct a field of order 8 = 23 as a quotient ring...

 

Transcribed Image Text:

1. Describe how to construct a field of order 8 = 23 as a quotient ring R/I (i.e., state what the appropriate ring R and ideal I are). In particular, describe what the elements of the ring R/I are for your chosen R and I. 2. (12 points) Let C be the set of solutions z C to the equation 28 = 1. (a) Describe the elements of C as powers of a single complex number w. (What is w? Which powers? You may also find it helpful to draw the elements of C in the complex plane.) (b) What is the sum of the elements of C? (No explanation necessary.) 3. (12 points) Let a and d be positive integers. State what the Division Theorem says about dividing a by d. 4. (14 points) Solve 87x = 3 in Z/(156), or explain why no solution is possible. Show all your work and JUSTIFY your answer. 5. (14 points) Let F64 be the field of order 64, and let a be a primitive element of F64. (a) What is the order of a? (No explanation necessary.) (b) What is the order of Ba? Briefly EXPLAIN. (c) Find a different element of F64 that has the same order as =a6. Express your answer as a power of a, and briefly JUSTIFY your answer. 6. (14 points) Let v = 1 V2= and v3 = be vectors in F7 and let W = 2 3. span {V1, V2, V3}. (a) Use the definition of linear independence to prove that {V1, V2, V3} is linearly inde- pendent. (b) How many vectors are there in W? JUSTIFY your answer. (You can just express your answer as a power of some number; you don't have to multiply out that power.) 7. (14 points) Consider the subgroup H = (7) in F19. 8. (14 points) Let W be the subset of F 3 defined by W = { +22=0}. x2 Fx1+x20 x3 13 Give part of the proof that W is a subspace of F 17, in the following steps: (a) Explain why 0 W. (b) Suppose x, y = W. Explain why x + y = W. 9. (14 points) Use the Euclidean Algorithm to find gcd (x+x5 in F2[x], given the following first step: x6 + x5 +1, x + x+x+1) + x3 + 1 = (x + x + 1)(x + x + x + 1) + (x +x) In other words, the first step of the Euclidean Algorithm is done for you, above, and you do not need to check it. Otherwise, show all your work. 10. (14 points) Recall that the parity check matrix of the Hamming 7-code H7 is [1 0 1 0 1 0 1 H7 0 1 1 0 0 1 1 0 0 0 1 1 1 1 Suppose Yolanda is receiving transmissions sent using the Hamming 7-code, and she receives 1 y = Correct y to a codeword y', if necessary, and read off the message bits 3, 5, 6, and 7 to find the intended message m'. Show all your work. 11. (14 points) Note that in F2[x], we have x6 x3 * + x + 1 = (x + x) (x + x + x + 1) + (x+x+1) +x+x+1 = (x) (x + x + 1) +1 (I.e., you are given the above facts and do not need to check them yourself.) Let F64 = F2[a], where a is a root of x6 + x + 1. Find the multiplicative inverse of a3a+a+1. Show all your work. 12. (14 points) Let A be a matrix with entries in F5 such that [2 4 2 3 4 2 [1 0 3 0 0 2 3 2 2 0 0 2 0 4 0 0 3 A = 4 1 1 2 3 1 ' RREF(A) = 0 0 0 1 0 3 2 2 4 1 0 3 4 4 3 0 3 4 Find bases for Col(A) and Null(A). Show your work. 0 0 0 0 1 3 0 0 0 0 0 0 13. (14 points) Let E = F256, let be a primitive element of E, and let a = 35. Note that the order of a is 51 (i.e., you are given this fact and do not need to check it or justify it). Let C be the BCH code based on a with designed distance 8 = 5 over F2. In the following, show all your work, especially your orbit calculations. (a) Recall that m(x) is the minimal polynomial of a. Express m(x) as a product of terms of the form (x - a). (b) Find the generating polynomial g(x) of C, expressed as a product of minimal polyno- mials mi(x). (You do not need to expand each mi (x) as a product of terms of the form (x-a), other than the expansion of m(x) that you have already done in part (a).) (c) Find kdim C. 14. (24 points) Fix N = 36 and w = ei/36. Let H0 = C, H = C2, H2 = C6, H3 = C12, and H4C36. Recall that the main loop of the FFT based on C1 C2 C6 C12C36, applied to the initial input x = f(0) can be described as follows. For i = 1 to 4: Set Hi-1 = (wm), H = (wk), and d = m/k. d-1 Subgroup fill: For j = 0 to (N/k) 1, set y(jk) = x(jm + kr)wrkj. r=0 Translate the subgroup fill to cosets of Hi, set x = y, and loop. (a) Working in terms of w, write out the elements of H2 and H3 and write out the elements of the standard transversal T2,3 for H2 in H3. (b) Write out the results of the "subgroup fill" part of step 3 (i = 3). That is, for all t corresponding to the elements of H3, write out the formula for y(t) in terms of the inputs x (the output of step 2, i = 2). (c) Draw the corresponding subgroup subdiagram for step 3 (i = = 3). 1. Describe how to construct a field of order 8 = 23 as a quotient ring R/I (i.e., state what the appropriate ring R and ideal I are). In particular, describe what the elements of the ring R/I are for your chosen R and I. 2. (12 points) Let C be the set of solutions z C to the equation 28 = 1. (a) Describe the elements of C as powers of a single complex number w. (What is w? Which powers? You may also find it helpful to draw the elements of C in the complex plane.) (b) What is the sum of the elements of C? (No explanation necessary.) 3. (12 points) Let a and d be positive integers. State what the Division Theorem says about dividing a by d. 4. (14 points) Solve 87x = 3 in Z/(156), or explain why no solution is possible. Show all your work and JUSTIFY your answer. 5. (14 points) Let F64 be the field of order 64, and let a be a primitive element of F64. (a) What is the order of a? (No explanation necessary.) (b) What is the order of Ba? Briefly EXPLAIN. (c) Find a different element of F64 that has the same order as =a6. Express your answer as a power of a, and briefly JUSTIFY your answer. 6. (14 points) Let v = 1 V2= and v3 = be vectors in F7 and let W = 2 3. span {V1, V2, V3}. (a) Use the definition of linear independence to prove that {V1, V2, V3} is linearly inde- pendent. (b) How many vectors are there in W? JUSTIFY your answer. (You can just express your answer as a power of some number; you don't have to multiply out that power.) 7. (14 points) Consider the subgroup H = (7) in F19. 8. (14 points) Let W be the subset of F 3 defined by W = { +22=0}. x2 Fx1+x20 x3 13 Give part of the proof that W is a subspace of F 17, in the following steps: (a) Explain why 0 W. (b) Suppose x, y = W. Explain why x + y = W. 9. (14 points) Use the Euclidean Algorithm to find gcd (x+x5 in F2[x], given the following first step: x6 + x5 +1, x + x+x+1) + x3 + 1 = (x + x + 1)(x + x + x + 1) + (x +x) In other words, the first step of the Euclidean Algorithm is done for you, above, and you do not need to check it. Otherwise, show all your work. 10. (14 points) Recall that the parity check matrix of the Hamming 7-code H7 is [1 0 1 0 1 0 1 H7 0 1 1 0 0 1 1 0 0 0 1 1 1 1 Suppose Yolanda is receiving transmissions sent using the Hamming 7-code, and she receives 1 y = Correct y to a codeword y', if necessary, and read off the message bits 3, 5, 6, and 7 to find the intended message m'. Show all your work. 11. (14 points) Note that in F2[x], we have x6 x3 * + x + 1 = (x + x) (x + x + x + 1) + (x+x+1) +x+x+1 = (x) (x + x + 1) +1 (I.e., you are given the above facts and do not need to check them yourself.) Let F64 = F2[a], where a is a root of x6 + x + 1. Find the multiplicative inverse of a3a+a+1. Show all your work. 12. (14 points) Let A be a matrix with entries in F5 such that [2 4 2 3 4 2 [1 0 3 0 0 2 3 2 2 0 0 2 0 4 0 0 3 A = 4 1 1 2 3 1 ' RREF(A) = 0 0 0 1 0 3 2 2 4 1 0 3 4 4 3 0 3 4 Find bases for Col(A) and Null(A). Show your work. 0 0 0 0 1 3 0 0 0 0 0 0 13. (14 points) Let E = F256, let be a primitive element of E, and let a = 35. Note that the order of a is 51 (i.e., you are given this fact and do not need to check it or justify it). Let C be the BCH code based on a with designed distance 8 = 5 over F2. In the following, show all your work, especially your orbit calculations. (a) Recall that m(x) is the minimal polynomial of a. Express m(x) as a product of terms of the form (x - a). (b) Find the generating polynomial g(x) of C, expressed as a product of minimal polyno- mials mi(x). (You do not need to expand each mi (x) as a product of terms of the form (x-a), other than the expansion of m(x) that you have already done in part (a).) (c) Find kdim C. 14. (24 points) Fix N = 36 and w = ei/36. Let H0 = C, H = C2, H2 = C6, H3 = C12, and H4C36. Recall that the main loop of the FFT based on C1 C2 C6 C12C36, applied to the initial input x = f(0) can be described as follows. For i = 1 to 4: Set Hi-1 = (wm), H = (wk), and d = m/k. d-1 Subgroup fill: For j = 0 to (N/k) 1, set y(jk) = x(jm + kr)wrkj. r=0 Translate the subgroup fill to cosets of Hi, set x = y, and loop. (a) Working in terms of w, write out the elements of H2 and H3 and write out the elements of the standard transversal T2,3 for H2 in H3. (b) Write out the results of the "subgroup fill" part of step 3 (i = 3). That is, for all t corresponding to the elements of H3, write out the formula for y(t) in terms of the inputs x (the output of step 2, i = 2). (c) Draw the corresponding subgroup subdiagram for step 3 (i = = 3).