Bottom     Previous     Contents

FFT of Pure Real Sequences.

Both the definition of the DFT and the various FFT algorithms which have been developed for its evaluation use complex numbers and complex arithmetic. Common sense would suggest that for a the transform of a pure real sequence, only half as much work should be needed. This is almost true. There's no getting away from the need for complex arithmetic, but there are several ways of getting better performance from the FFT algorithms applied to pure real sequences.

An important fact about real transforms is their symmetry:

equation

This is easy to prove. (Try it.)

As a result, we can see that if N is even, both F(0) and F(N/2) must be real. Given these two values and the complex values F(1)..F(N/2-1), (I.E. N numbers in total) the sequence is completely characterised.

If N is odd, F(0) is real but F(N/2) does not exist. To fully characterise the DFT of an odd numbered sequence we need F(0) and the complex values F(1)..F((N-1)/2). Again, this gives use a total of N numbers. So in general, we don't need the 'full' DFT.

Two for the Price of One.

This method uses a single N point complex FFT to evaluate two N point real FFT's.

Let the real sequences be x(n) and y(n). Define a complex sequence z(n):

equation

This can be reversed...

equation

equation

In the frequency domain we have:

equation

equation

But we don't need to evaluate the FFT of z*, symmetry helps out again:

equation

equation

In other words..

equation

So the result is:

equation

equation

So a simple pass after the FFT can be used to extract the transforms of x and y.

Note that in some cases, this pass is unnecessary. If the FFT is being used to convolve two real signals with the same real impulse response, all that is needed is to multiply by the FFT of the filter impulse response and IFFT the result.

It's easy to see how to reverse this process to evaluate two inverse transforms at once, if it's known that the inverse transforms are both real. Let the two transformed sequences be:

equation

equation

Calculate..

equation

The result of evaluating the inverse transform of Z(k) will simply be:

equation

The real part gives x(n), the imaginary part gives y(n).

A Different DIT.

The 'two for the price of one' method is only good if we really do need two FFT's. But, we've seen that any FFT of size N (N even) can be expressed as two N/2 sub-FFT's in the development of the DIT algorithm. This method uses the 'two for the price of one' method for the sub-FFT's and then combines the results using a single DIT algorithm butterfly pass.

Recall the DIT decomposition for a sequence of N samples, where N is even:

equation

equation

equation

equation

Remember the algorithm is to evaluate the sub-transforms of even and odd samples and then combine them with a butterfly. The two sub transforms are both real, so there's nothing to stop us using the 'two for the price of one' method to evaluate both of these at the same time. (Of course, you can use any FFT you like to do this, it doesn't need to be a DIT algorithm.) So here's the algorithm.

Form a complex N/2 sample sequence (even samples are real, odd are imaginary):

equation

(If your FFT expects a complex array to be represented as an array of real/imaginary pairs, then nothing has to be done.)

Take the FFT of z to get:

equation

The 'two for the price of one' method tells us that the transforms of fe and fo, Fe and Fo are:

equation

equation

All that remains to be done is to combine these using the DIT algorithm butterfly:

equation

or..

equation

This gives us values for k=0..N/2-1. This is almost all we need for a the transform of a real signal, the only missing point is k=N/2. However, periodicity of Z shows that:

equation

(Note the +j.) If we want the remaining values for k=N/2+1 .. N-1 then symmetry of real transforms tells us:

equation

In order to reverse this process, and calculate the inverse transform of a single sequence which is known to be real, we need a way of calculating Z(k), given F(k). This is quite easy. Observing that symmetry implies F(N/2+k) =F(N/2-k)*, the final butterfly stage can be reversed as follows:

equation

equation

The array for IFFT is simply:

equation

Evaluating the IFFT will yield the even samples as the real part and the odd samples as the imaginary part.

Half a Transform.

The previous two methods for real transforms have the advantage that you can use any general purpose complex FFT to evaluate a real FFT (or two), but they both required an additional pass of the FFT output to get the data we want.

There is also an intrisic hazard with the 'two for the price of one' method if the two sequences have significantly different magnitudes. This problem is most likely to occur if you're using floating point arithmetic. Remember that in reality all calculations will be of finite precision. The 'mixing up' of sequences in the combined transform means that the smaller magnitude sequence will see the quantisation noise floor of the larger magnitude sequence, which may be quite significant (possibly overwhelming).

There is another approach you can use, if you don't mind writing a special FFT for real data. Recall the symmetry of the DFT of real sequences:

equation

For even N, we only need F(0)..F(N/2), both F(0) and F(N/2) are real.

For odd N, we only need F(0)..F(N-1/2), F(0) is real.

The basic idea is to modify the FFT algorithm to calculate only these values. If we want the whole transformed sequence it can easily be generated using the symmetry property above.

A Real DIT.

In the case of the Decimation In Time algorithm, this is particularly simple. Remember that in the recursive version the DIT algorithm we divided the transform into even (fe) and odd (fo) sequences of size N/2, evaluated the FFT of these sequences and then combined the result with a DIT butterfly pass:

For k= 0 .. N/2-1:

equation

and..

equation

where:

equation

The two sub-transforms are also real, so we could modify them to just evaluate Fourier coefficients from 0 .. N/4. Similarly, the final butterfly pass only needs to calculate coefficients 0 .. N/2. The recursive nature of the transform means that this butterfly pass modification is all we really need to do. We'll use FFT' to denote this FFT of a real sequence.

So, for k= 1 .. N/4-1:

equation

and using the symmetry of the sub-transforms, for k= N/4+1 .. N/2-1:

equation

All of the above calculations are fully complex.

The two real points k=0 and k=N/2 are calculated from 2 real points as:

equation

equation

The complex point k=N/4 is calculated from 2 real points as:

equation

For an N point real transform (where N is even) we need to calculate (N/2+1), not N/2 points. Of these the first F(0) and last F(N/2) are always real, the rest are complex. To implement this method with an 'in-place' algorithm, probably the easiest solution is to keep the F(N/2) value in the (vacant) imaginary part of F(0).

The only minor problem with this is that the simplest form of the DIT algorithm operates on input data in bit reversed order and generates normal order output. It is therefore better suited to inverse transforms than forward transforms. However, we're more likely to be performing forward transforms on real data. This is not an unsolvable problem. We've already described two ways to use the DIT algorithm on normal order data to generate bit reversed order output. (Use bit reversed addressing if it's available, or else modify the FFT routine to accept samples spaced at intervals greater than 1 and use a bit reversed order twiddle factor table).

An 'Unreal' DIF.

In the light of the above discussion, it should come as no surprise that the DIF algorithm can easily be modified to evaluate the inverse FFT of a signal which is known to be real. Again, the idea is to only calculate half of what a full complex FFT requires, and use symmetry to get the other half. The DIF algorithm divides the FFT into two sub-transforms, both of which are required to give a real result. Recall the form of the DIF algorithm, expressed as an inverse FFT.

For even n (n=2n'):

equation

equation

equation

For odd n (n=2n'+1):

equation

equation

equation

We only have values of F for, k = 0 .. N/2, but symmetry allows us to write:

equation

So..

equation

equation

Because each of the (N/2 point) sub-transforms generates a real result, we should only need values of E and O for k = 0 .. N/4 (not k = 0 .. N/2). This is easily verified:

equation

equation

equation

So the work required on each pass is only half that of the complex IFFT.

©1999 - Engineering Productivity Tools Ltd.


Next     Top