CS 370 Winter 2018: Assignment 3
Due March 15, 5 pm.
Instructor: G. Labahn Office: DC3629 e-mail:
Lectures: MWF 8:30, 11:30 Office Hours: Tues 11:00-12:00
Instructor: Y. Li Office: DC3623 e-mail:
Lectures: MWF 1:30 Office Hours: Thurs 2:00-3:00
Web Site: cs370 piazza
Your assignment should be handed in electronically on UW Learn. The submission
should include one pdf file containing the assignment answers and the cover sheet and
all the m-files required to run the code, with no folder structure (not zipped).
Analytic Questions
1. (10 marks)
(a) Calculate by hand the discrete Fourier transform of f = (1, 2, 3, 2).
(b) Calculate by hand the inverse discrete Fourier transform of F = (4, −1, 0, −1).
2. (15 marks)
Let {F0 , . . . , FN −1 } be the DFT of a sequence {f0 , . . . , fN −1 } defined by
−1
1 NX
Fk = fn W −nk
N n=0
2πi
with W = e N the N th root of unity. Show your work and simplify where possible.
(a) Give a formula for Fk for all k when fn = (−1)n for n = 0, ..., N − 1.
(b) Suppose (f0 , . . . , fN −1 ) = (−1, . . . , −1, 1, . . . , 1) having the first half negative one and
remaining half one (with N even). Show that F2k = 0, k = 0, 1, . . . , N2 −1.
3. ( 20 marks)
Consider the sequence of eight numbers f = ( 1, 0, 2, 0, −1, 0, −2, 0 ).
(a) What are the two arrays (g and h, each of length 4) that are used in computing the
DFT of f by the FFT method?
(b) Compute G and H, the two DFTs for {gi } and {hi }, respectively, using the definition
of DFT of 4 values. Simplify if possible.
(c) Using G and H from part b), write out the DFT of the array f .
(d) Using the FFT butterfly algorithm, compute by hand the DFT of f .
1
Due March 15, 5 pm.
Instructor: G. Labahn Office: DC3629 e-mail:
Lectures: MWF 8:30, 11:30 Office Hours: Tues 11:00-12:00
Instructor: Y. Li Office: DC3623 e-mail:
Lectures: MWF 1:30 Office Hours: Thurs 2:00-3:00
Web Site: cs370 piazza
Your assignment should be handed in electronically on UW Learn. The submission
should include one pdf file containing the assignment answers and the cover sheet and
all the m-files required to run the code, with no folder structure (not zipped).
Analytic Questions
1. (10 marks)
(a) Calculate by hand the discrete Fourier transform of f = (1, 2, 3, 2).
(b) Calculate by hand the inverse discrete Fourier transform of F = (4, −1, 0, −1).
2. (15 marks)
Let {F0 , . . . , FN −1 } be the DFT of a sequence {f0 , . . . , fN −1 } defined by
−1
1 NX
Fk = fn W −nk
N n=0
2πi
with W = e N the N th root of unity. Show your work and simplify where possible.
(a) Give a formula for Fk for all k when fn = (−1)n for n = 0, ..., N − 1.
(b) Suppose (f0 , . . . , fN −1 ) = (−1, . . . , −1, 1, . . . , 1) having the first half negative one and
remaining half one (with N even). Show that F2k = 0, k = 0, 1, . . . , N2 −1.
3. ( 20 marks)
Consider the sequence of eight numbers f = ( 1, 0, 2, 0, −1, 0, −2, 0 ).
(a) What are the two arrays (g and h, each of length 4) that are used in computing the
DFT of f by the FFT method?
(b) Compute G and H, the two DFTs for {gi } and {hi }, respectively, using the definition
of DFT of 4 values. Simplify if possible.
(c) Using G and H from part b), write out the DFT of the array f .
(d) Using the FFT butterfly algorithm, compute by hand the DFT of f .
1
