Some time ago I produced an application that worked out the power-frequency spectrum of a user-chosen section of a sound file. The application is called

The ‘slow’ method has some advantages. For example, it is easy to understand, and to write a computer program which can be studied or modified. However most serious computations of the spectrum of a signal tend to adopt ‘Fast Fourier Transform’ (FFT) methods which – as the name indicates – are much quicker. So I decided it was about time I produced such a ‘fast’ application, which I have duly now done, and have named !

The way you set up and use this new application is essentially the same as for

I am not even going to try to explain all the details of how an FFT works as understanding them can be a nightmare! But I will try to outline the basic ‘tricks’ involved. To do this I will also explain the idea behind Fourier analysis. Lets start with the arrangement illustrated in Figure 1.

This shows two graphs. The upper graph plots two patterns. The solid (blue) line represents an input signal waveform, and the broken (red) line a ‘test sinewave’ of a chosen frequency. In this case the input signal happens to be a sinusoid of the same frequency and phase as our ‘test sinewave’. The analysis works by multiplying the two patterns together on a sample-by-sample basis and adding up the results of these multiplications. The result in this case is shown by the solid (black) like in the lower graph of Figure 1.

This process is at the heart of Fourier analysis. In effect, when we add together all the values obtained by the sample-by-sample multiplications we get a result which indicates the level of any variations in the signal which shared the same frequency as our test sinewave. Variations at the ‘correct’ frequency add up to a large result. Variations at other frequencies then to make little or no contribution to the sum of the sample-by-sample multiplications.

This means that when we have some other input signal pattern we can try the above method for various test frequencies. By doing it for various number of cycles in the chosen time period for which we have samples we can determine the effective amount at each frequency contained in the signal pattern. (We also have to do cosines, but the argument is the same.) The results then tell us how much of the signal power presents itself as being as being at each of the tested frequencies. Hence we have worked out a power-frequency spectrum. The problem is that – as described – the process is quite slow when we have many samples to analyse, and lots of possible frequencies - even when we limit the chosen frequencies to just those with an integer number of cycles in the time period covered by our set of signal samples.

Fortunately some tricks have been spotted and can be used to speed up this process quite dramatically! The first is to spot that our test sinewave tends to repeat the same series of values over and over again during each of its cycles. Since multiplications take longer than additions we can then hope to speed things up if we re-arrange the input data to combine signal samples we want to multiply by the same test value before do the multiplication. A similar ‘trick’ is to spot that when we double the frequency of the test sinewave we are essentially just weeding out alternate values and shifting the remaining ones together. This means we can ’rearrange’ all the signal sample information before we do any multiplications, then do just a relatively small number of multiplications, and then unscramble the rearrangement to reveal the spectrum!

The above is far from being a complete and accurate explanation of how an FFT works, but I hope it gives a flavour of the kinds of mathematical short-cuts used. The consequences can be quite dramatic. To illustrate this, Figure 3 compares the results of using the slow and FFT methods on the same input. Here I have used a sound data file which contained a 0dB level 1 kHz sinewave as the input signal.

As with the previous example applications in this series

1450 words

29th Nov 2007

Jim Lesurf

29th Nov 2007

Jim Lesurf