EEEN3004J Digital Signal Processing
Spring 2020
Assignment 1
The Fast Fourier Transform
You have been assigned to a team for this assignment (See Appendix 1). You may divide the work
between team members any way you agree to, but a joint grade will be awarded except where one
team member fails to engage with the assignment.
You are to solve the problems given below, and to submit your report on Brightspace. See
Brightspace for the submission deadline. Late reports will be penalized according to UCD policy.
Problems:
Each team has been assigned a combination of two different fft algorithms. See Appendix 1 for the
assignments.
1. Write down how what length of DFT, N, your algorithm will be able to calculate.
• This can be easily found for most assignments, as simply the product of the two
radices, e.g. if you had a radix 3 stage followed by a radix 4 stage, you get =
3 × 4 = 12 points. That would split a 12-point DFT calculation into three 4-point
DFTs, which would then be carried out by means of a single stage of the radix 4
algorithm, something like this:
For another example, consider Fig. 7.2.4 in the notes. That figure shows a butterfly
diagram for a three-stage algorithm, each stage of which is a radix 2 decimation in
time algorithm.
2. Algebraic derivations of any algorithms must be presented.
• The general proofs are presented in the journal paper supplied to you, but you must
customize them for the specific number of points for your problem. Cooley and
Tukey derive an algorithm for any = 12. A radix 2 decimation-in-time algorithm
requires that 2 = 2 (this is the algorithm in the notes for the class). A radix 2
decimation-in-frequency algorithm requires that 1 = 2.
3. You are to draw a butterfly diagram for your entire algorithm.
4. A numerical example must be traced through the diagram. Verify using MATLAB that your
calculation is correct. The example signal should be derived from the digits of your student
numbers, e.g. Given a team with an = 12 problem, the last six digits of both member’s
student numbers should be used to give 12 integers which can then be tracked.