DANN:Fast Fourier Transform

From Syncleus Wiki

A Fast Fourier Transform takes an input signal representing a sequence of time varying floating point numbers and break it up into the frequencies present in the signal. It can also reverse this information and turn a collection of frequencies into a sequence of varying values. There are circular and linear convolve functions for working on 2 simultaneous signals.

Cooley Tukey Implementation

The most common implementation of a Fast Fourier Transform is the Cooley Tukey implementation. This algorithm recursively breaks the signal down into odd and even points to compute its composite frequencies. While the signal can be any length anything less than a power of two will be internally padded with 0, so its suggested to break your signal up into blocks that are a power of 2.

This class also exposes several methods not present in the FastFourierTransform interface, these methods end with *Matrix. All of these methods expose the core algorithm behind a Cooley Tukey implementation and allow you to pass ComplexNumber arrays directly. Unless your doing something unusual you will probably want to limit yourself to the methods exposed in the interface.

Example: Processing a signal

We want to show a simple example of analyzing a signal over a single block of time. Most real applications will process blocks of time consecutively in real time or until the data runs out.

The first step is of course to get a chunk of your signal. The important part to consider here is that the larger the block size the more of the lower frequencies you'll pick up. If you want a higher resolution of the upper frequencies the only way to do that is to increase the bitrate of your incoming stream. So keep in mind the resolution of the spectrum is dependent on the bitrate for the upper end and the block size for the lower end.

If you want to calculate the maximum frequency given a particular bitrate call:

DiscreteFourierTransform.upperFrequency(bitrate);

If you want to know the resolution of the frequencies you'll get from a particular blockSize and bitrate then call:

DiscreteFourierTransform.frequencyResolution(blockSize, bitrate);

Another way to look at the frequency resolution is that it us the smallest frequency that isn't 0. All Discrete Fourier Transforms include the frequency 0 which represents any offset of the overall signal.

We don't care how you obtain the signal but in this demo we assume it's size is the same as blockSize:

double[] signal = getSignal();
assert (signal.length == blockSize);

Once we've figured out our block size and bitrate and have a signal to go along with it then we can create a transformer to process the signal:

FastFourierTransformer transformer =
     new CooleyTukeyFastFourierTransformer(signal.length, bitrate);

Next we want to use our transformer to convert the signal into a DiscreteFourierTransform which represents the collection of frequencies that make up the signal.

DiscreteFourierTransform transformed = transformer.transform(signal);

Now all we have to do something useful with this new information. Lets say we wanted to test to see if the signal has more high frequency waves than low frequency we simplye do:

double middleFrequency = transformed.getMaximumFrequency() / 2.0;
double maxFrequency = transformed.getMaximumFrequency();

double lowPower = transformed.getBandRms(0.0, middleFrequency);
double highPower = transformed.getBandRms(middleFrequency, maxFrequency);

if( highPower > lowPower )
{
     //mostly high frequencies
}
else
{
     //mostly low frequencies
}

See Also

• Discrete Fourier Transform