SETI@home: Fast Fourier Transform (FFT)


log in
Raw radiowave data varies with time—like a line on an oscilloscope that wiggles up and down in response to your voice through an attached microphone. In this case, time runs along the horizontal x-axis and signal strength (air pressure) along the vertical y-axis. The raw radio telescope signal is not very useful to us. What we would like to see is if there are any constant (and loud) "tones" within the signal. We would rather be looking at a graph with frequecy running along the horizontal x-axis, and power along the vertical y-axis. Any spike in this graph would be a loud signal at a single frequency.

To transform a set of time-based data into a set of frequency-based data, we apply a relatively complex mathematical operation called a "Fast Fourier Transform" or FFT.

The large graph in the lower frame of the SETI@home screensaver displays data resulting from FFT processing. At the beginning of a work-unit, we perform 15 different FFT's, each examining the data with varying resolution. We begin by looking for details as small as .07 Hz wide. There are tradeoffs with this type of analysis. If you want to be very accurate in frequency, you need to observe the data in longer chunks of time. For example, at the 0.075 Hz frequency resolution, we must look at chunks of data 13.42 seconds in length. To completely analyze our 107 second sample, we need to do 8 of these FFT's. When we reduce the frequency resolution to 0.14 Hz we only have to look at a 6.7 second sample of data. We now have less frequency resolution, but we have more time resolution. We have to look at twice the number of these (16 of them) to cover our 107 seconds of data! We look at 15 different frequency resolutions (0.075, 0.15, 0.3, 0.6, 1.2, 2.5, 5, 10, 20, 40, 75, 150, 300, 600, and 1200 Hz) in our analysis. With each halving of the frequency resolution we must perform twice the number of FFT's to cover 107 seconds of work-unit data. The amount of number crunching necessary is impressive.

Copyright © 2014 University of California