CSE 417 Homework 5, Winter 2011

Do this assignment independently. Submit your written results and graph in class on Wednesday, March 2. Submit your program code via Catalyst by 2:00 PM, Wednesday March 2.

Overall description

Implement, describe, and compare two methods of computing the Discrete Fourier Transform: (a) the direct method, working from the definition on slide 12 of the Powerpoint set on the Fast Fourier Transform. (b) the Fast Fourier Transform, using the form given in the pseudocode on slide 15.

Details

Implement both algorithms. Use either Java or Python. Implement two functions: DirectDFT and FFT. Each should accept its arguments in the following form: FFT(n, cvector) where n is an integer (assumed to be a power of 2) and cvector is a one-dimensional array of complex numbers. In Java the complex vector should be an array of Complex elements, i.e., Complex[]; (for a recommended Java library of complex number methods, see GoPost). In Python, it should be a list of complex numbers, such as [5.0+2.3j, -1.2-0.5j].

Each of DirectDFT and FFT should return a similar cvector containing the Discrete Fourier Transform of the input.

Set up your program so that input to it can be provided in a file of complex numbers. The five-line example below gives one example of the file format. Notice that n is a power of 2, but it is not given explicitly. There just happen to be n complex numbers in the file (and in the example below, n=8). Also, notice that some of the numbers appear to be real numbers, with no imaginary part; the program should simply assume that the imaginary parts of those numbers are zero. We'll use the Python convention that the imaginary unit vector is denoted by "j" (not "i"). Complex numbers on the same line are separated by commas. Spaces are optional and they may occur before or after a number. A complex number will not be split across multiple lines. No comma is necessary at the end of a line, but if it is there, it will not cause an error. A line that begins with "#" is a comment.

2-3j, -2.5+7.75j, 0, -3j, -127
  -101.2999999-102.1j,
# This line is a comment.
# The following line contains the last two numbers.
  2.2,    3+j

This file format has been designed to make it easy for the program to handle both complex data (in which the imaginary parts of numbers are sometimes nonzero) and real data (in which the imaginary parts of numbers are consistently zero). Also, the built-in Python conversion function "complex" can be applied to any of the numbers here (given as strings), and it will properly construct the corresponding complex number. (If you use Java, you may need to write a method that will handle the various cases that are illustrated in the example.)

Test cases

Case 1:

 n = 4
 A(x) = [1.0, 0+j, -1.0, -j]

Case 2:

 n = 8
 (The data is that in the above example input file.)

Case 3:

n = 256
A(x) = 16 cos (4 pi x / 256)

Comparison cases

Using any data of the right dimensions, compare the performance of your two procedures for n = 2, 4, 8, 16, 32, 64, 128, 256, 512, and if your DirectDFT doesn't take too long, also 1024, 2048, and 4096. Give the running times in millisec, and draw a graph that shows how they compare.

Coding

Comment your code clearly using any format you like. The comments should explain how each part of your code implements its part of the algorithm, or whatever else it is there for.

Points

(a) DirectDFT: 10 points
(b) FFT: 20 points
(c) Test cases: 10 + 10 + 10
(d) Comparison runs and Graph: 20
(e) Comments: 20

Items a, b, c and e should be submitted via Catalyst. (Your comments will be in your code. Your DirectDFT and FFT can either be in the same file or separate files. The output for the three test cases can be cut and pasted into a single file, with identifying comments added to show clearly which is which.) Item d should be submitted as hardcopy at the beginning of class: the comparison runs should be presented as a table, with the runtimes given in milliseconds. The graph may be hand-drawn, and it should clearly show your data points as well as the diverging growth rates for the algorithms.

Extra credit (10)

Apply the FFT to the problem of image filtering as follows:
(a) read in a 512 x 512 black-and-white or color image and store it in an array such at the individual pixel values can be easily accessed.
(b) compute the 2D DFT of the image by first transforming each row of the image (obtaining an intermediate array whose elements are complex) and then transforming each column of the intermediate array.
(c) zero out the set of (high) frequency components of the transform, where the set is defined as the union of a region of high horizontal frequency components and a region of high vertical frequency components. Each region should be about half of the transform array. This means roughly one fourth of the transform values will remain potentially nonzero after this step.
(d) inverse-transform the columns of this array getting a new intermediate array.
(e) inverse-transform the rows of the new intermediate array getting a filtered array.
(f) convert the filtered array to an image by taking the modulus of each element and restricting the final value to the range of legal pixel values (typically 0 to 255).
(g) write out the filtered image as a .PNG file.

Turn in the extra credit materials via Catalyst. Turn in your extra code in a file ExtraCredit.java or ExtraCredit.py. Turn in both your original and your final .PNG images.

Last updated: Feb. 17, 2011.