Fourier
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Fourier as PDF for free.
More details
- Words: 402
- Pages: 3
Course: Algorithm Theory Instructor: Christian Schindelhauer
Questions:
Answers: 1) w 0 = 1, notprimitive 8 w1 = e 2Πi / 8 = Cos (Π / 4) + iSin(Π / 4) = 0.707 + i * 0.707 ≠ 1 8 2 w 2 = e ( 2Πi / 8) = Cos (Π / 2) + iSin(Π / 2) = 0 + i * 1 ≠ 1 8 3 w3 = e ( 2Πi / 8) = Cos (3Π / 4) + iSin(3Π / 4) = −0.707 + i * 0.707 ≠ 1 8 4 w 4 = e ( 2Πi / 8) = Cos (Π ) + iSin(Π ) = −1 ≠ 1 8 5 w5 = e ( 2Πi / 8) = Cos (5Π / 4) + iSin(5Π / 4) = −0.707 + i * (−0.707) ≠ 1 8 6 w 6 = e ( 2Πi / 8) = Cos (3Π / 2) + iSin(3Π / 2) = 0 + i * −1 ≠ 1 8 7 w 7 = e ( 2Πi / 8) = Cos (7Π / 4) + iSin(7Π / 4) = 0.707 + i * −0.707 ≠ 1 8 Not all 8-th roots of unity are primitive, e.g. (omega_8^2)^4 = (omega_8^2)^0 = 1 Only w1 , w3 , w5 , w 7 are primitives.
8
8
8
8
2) a)
We calculated for n=4 because degree of pq is 4.
0 1 2 3 b) w = 1 , w = i , w = −1 , w = −i 4
4
4
0 0 4 4 1 1 ( w , p( w )) =(i, 3i-1) 4 4 2 2 ( w , p( w )) =(-1, -4) 4 4 3 3 ( w , p( w )) =(-i, -3i-1) 4 4 ( w , p( w )) =(1, 2)
4
0 0 4 4 1 1 ( w , q( w )) =(i, 2i+5) 4 4 2 2 ( w , q( w )) =(-1,3) 4 4 3 3 ( w , q( w )) =(-i, -2i+5) 4 4 ( w , q( w )) =(1, 7)
0 0 4 4 1 1 ( w , pq( w )) =(i, 13i-11) 4 4 2 2 ( w , pq( w )) =(-1,-12) 4 4 3 3 ( w , pq( w )) =(-i, -13i-11) 4 4 ( w , pq( w )) =(1, 14)
c)
d)
Questions:
Answers: 1) w 0 = 1, notprimitive 8 w1 = e 2Πi / 8 = Cos (Π / 4) + iSin(Π / 4) = 0.707 + i * 0.707 ≠ 1 8 2 w 2 = e ( 2Πi / 8) = Cos (Π / 2) + iSin(Π / 2) = 0 + i * 1 ≠ 1 8 3 w3 = e ( 2Πi / 8) = Cos (3Π / 4) + iSin(3Π / 4) = −0.707 + i * 0.707 ≠ 1 8 4 w 4 = e ( 2Πi / 8) = Cos (Π ) + iSin(Π ) = −1 ≠ 1 8 5 w5 = e ( 2Πi / 8) = Cos (5Π / 4) + iSin(5Π / 4) = −0.707 + i * (−0.707) ≠ 1 8 6 w 6 = e ( 2Πi / 8) = Cos (3Π / 2) + iSin(3Π / 2) = 0 + i * −1 ≠ 1 8 7 w 7 = e ( 2Πi / 8) = Cos (7Π / 4) + iSin(7Π / 4) = 0.707 + i * −0.707 ≠ 1 8 Not all 8-th roots of unity are primitive, e.g. (omega_8^2)^4 = (omega_8^2)^0 = 1 Only w1 , w3 , w5 , w 7 are primitives.
8
8
8
8
2) a)
We calculated for n=4 because degree of pq is 4.
0 1 2 3 b) w = 1 , w = i , w = −1 , w = −i 4
4
4
0 0 4 4 1 1 ( w , p( w )) =(i, 3i-1) 4 4 2 2 ( w , p( w )) =(-1, -4) 4 4 3 3 ( w , p( w )) =(-i, -3i-1) 4 4 ( w , p( w )) =(1, 2)
4
0 0 4 4 1 1 ( w , q( w )) =(i, 2i+5) 4 4 2 2 ( w , q( w )) =(-1,3) 4 4 3 3 ( w , q( w )) =(-i, -2i+5) 4 4 ( w , q( w )) =(1, 7)
0 0 4 4 1 1 ( w , pq( w )) =(i, 13i-11) 4 4 2 2 ( w , pq( w )) =(-1,-12) 4 4 3 3 ( w , pq( w )) =(-i, -13i-11) 4 4 ( w , pq( w )) =(1, 14)
c)
d)
