4.5 Java1486-fun with java, understanding the fast fourier transform  (Page 2/14)

There are several different FFT algorithms in common use. In addition, there are many sites on the web where you can find explanations of themechanics of FFT algorithm. I won't replicate those explanations. Rather, I will explain the underlying concepts that make the FFT possible andillustrate those concepts using a simple program. Hopefully, once you understand the underlying concepts, one or more of the explanations of themechanics that you find on other sites will make sense to you.

A general-purpose transform

The Fourier transform is most commonly associated with its use in transforming time-domain data into frequency-domain data. However, it isimportant to understand that there is nothing inherent in the Fourier transform regarding either the time domain or the frequency domain. Rather,the Fourier transform is a general-purpose transform that is used to transform a set of complex data in one domain into a different set ofcomplex data in another domain. It is purely happenstance that it happens to be so valuable in describing the relationship between the time domain andthe frequency domain.

Transforming from space domain to wave number domain

For example, my first job after earning a BSEE degree in 1962 was in the Seismic Research Department of Texas Instruments. That is where I had myfirst encounter with Digital Signal Processing (DSP) . In that job, I did a lot of work with Fourier transforms involving the time domain and the frequencydomain. I also did a lot of work with Fourier transforms involving the space domain and the wave-number domain.

Wave number is the name given to the reciprocal of wavelength for compression and shear waves propagating through a medium such as an ironbar, earth, water, or air, and also for electromagnetic waves such as radio and radar propagating through space.

(Those familiar with the subject will know that while compression waves will propagate through water and air, those media won't supportshear waves.)

Two-dimensional Fourier transforms

For example, one of the things that we did was to compute two-dimensional Fourier transforms on diagrams representing weighted points intwo-dimensional space. We would transform the weighted points in the space domain into points in the wave-number domain.

The weighted points in the space domain represented the locations and amplifications of seismometers in a two-dimensional array on the surface ofthe earth. Each seismometer was amplified by a different gain factor and polarity. The amplified outputs of the seismometers were added together invarious and complex ways intended to enhance signals and suppress noise.

Wave-number response to seismic waves

In this case, the wave number was the reciprocal of the wave length of seismic waves propagating across the array. By plotting the results of thetransformation in the wave-number domain, we could estimate which seismic waves would be enhanced and which seismic waves would be suppressed by theprocessing being applied to the seismometer outputs.