FFT docs are ambiguous

General JUCE discussion
1

The docs explain:

On return, the array will contain complex frequency + phase data, and can be passed to performRealOnlyInverseTransform() in order to convert it back to reals.

Nowhere in the description of this method is the order of the complex frequency + phase data specified. How is anyone supposed to know if the real and imaginary components are interleaved, or if the real components are 0->N/2-1 and the imaginary components are N/2->N?

For example, say that you provide that method with the collection [R,R,R,R]. You should get back an array of floats that is of size 2*N containing the real and imaginary frequency domain components. However, some FFT implementations would supply [R,R,R,R,I,I,I,I], while others might give you [R,I,R,I,R,I,R,I].

I realize that I can use a collection of Complex objects to avoid this ambiguity, but then what is the point of the performRealOnlyForwardTransform() and performRealOnlyInverseTransform() methods? My assumption is that these are here for the sake of computational efficiency if one wants to perform transforms in-place.

It seems to me that these methods should either be documented more thoroughly or removed, as they are frustrating at best the way they are now. If you’d like evidence of this, see this thread, where user gerudobombshell is simply instructed to avoid using these methods in favor of perform() and their inquiries regarding the arrangement of the output of performRealOnlyForwardTransform() is ignored.

TL;DR

performRealOnlyForwardTransform(): Are the real and imaginary components of the output interleaved, or is the result split into two halves, real and imaginary?

2 Likes
2

interleaved

3 Likes
3

Well, thank you. That is very helpful! Not sure how you figured that out, but uh, sweet!

4

…because FFT works on FFT::Complex, which is a struct of float r; and float i;

5

The method performRealOnlyForwardTransform takes a float* as an argument, not FFT::Complex. JUCE FFT does not solely operate on collections of FFT::Complex.

See: https://www.juce.com/doc/classFFT

6

you are right, and I read many people struggling with exactly what you just wrote… most times they managed when using the perform and ignoring the rest…
Also I peeked at the code, e.g.

But I am too bad in low level mathematics to claim to know the correct answer…

7

Here’s a quick example using the perform() method. And showing the correct scaling if you want to get the original signal back:

        const int order = 8;
        FFT fft (order, false);
        FFT ifft (order, true);
        
        const int fftSize = fft.getSize();
        jassert (ifft.getSize() == fftSize);
        
        HeapBlock<FFT::Complex> input (fftSize);
        HeapBlock<FFT::Complex> output (fftSize);
        
        for (int i = 0; i < fftSize; ++i)
        {
            const double phase = 2.0 * double_Pi * double (i) / (fftSize - 1);
            input[i] = { (float) sin (phase), 0.0f };
        }
        
        for (int i = 0; i < fftSize; ++i)
            Logger::writeToLog (String::formatted ("input[%d]=%f", i, input[i].r));
        
        fft.perform (input, output);
        
        for (int i = 0; i < fftSize; ++i)
            Logger::writeToLog (String::formatted ("output[%d]=(%f,%fi)", i, output[i].r, output[i].i));
        
        ifft.perform (output, input);
        
        const float scale = 1.0f / fftSize;
        
        for (int i = 0; i < fftSize; ++i)
            Logger::writeToLog (String::formatted ("input[%d]=%f", i, input[i].r * scale));
1 Like
8

I’ve been a bit confused about this as well:
First of all I would call it real and imaginary - frequency and phase is confusing. The output is interleaved (real1, imag1, real2,…) and at N/2 the negative frequencies start but in reverse order. Since the negative frequencies are not needed anyway I would just discard them. So for transforming a real signal it could as well take an array of size N and return an array of size N discarding the negative frequencies. Just my two cents :wink:

1 Like
9

No! This would not be “non-standard” FFT and also you need the negative frequency when you inverse transform the FFT back to real.

PS: also at N/2 there is the nyquist frequency, if you cut the FFT to the half, the information gets lost

10

Given the output is real, the input must have been real. If that’s the case, all the “negative” frequencies can be derived from the “positive” frequencies as they’re just the complex conjugate of the first half. This is what makes a real FFT faster, thus they usually only produce N/2 results (equaling a N sized real array)

e:

[quote=“chkn, post:9, topic:19096”]
PS: also at N/2 there is the nyquist frequency, if you cut the FFT to the half, the information gets lost
[/quote]This is false. The nyquist bin is always there, it is mirrored for complex FFTs (the missing “bin” is the DC bin that for complex transforms holds the DC offset for the first half as the real part, and the imaginary part is the second half DC offset).

11

really?, i think gustav was reffering to the FFT::performRealOnlyForwardTransform method,
which has a real input and a complex output

This is the description of the function, it says clearly it has a real input and a complex output

Performs an in-place forward transform on a block of real data.
The size of the array passed in must be 2 * getSize(), and the first half should contain your raw input sample data. On return, the array will contain complex frequency + phase data, and can be passed to performRealOnlyInverseTransform() in order to convert it back to reals.

first bin ( n n+1 ) is DC

( n/2 and /2+1 ) is Nyquist

The nyquist bin is always there

before the transformation there is no nyquist bin

1 Like
12

I haven’t used the FFT class so I wouldn’t know, but mathematically it is totally redundant to compute the conjugate pairs and/or require them to perform a real inverse fft.

Also, complex output != conjugate output. A real fft, unless the real signal is symmetric, has a complex frequency domain representation / output. This is not the same as having a 2x complex conjugate output.

[quote=“chkn, post:11, topic:19096”]
first bin ( n n+1 ) is DC

( n/2 and /2+1 ) is Nyquist
[/quote]Just to make sure we’re on the same page…

X(0) = {first half real DC, second half real DC}
X(N / 2) = {complex nyquist}
X(N - 1) = {second half complex bin 1}

So given a transform of the size 8, this will be the transform:

0 = dc
1 = i*2*pi*1/8
2 = i*2*pi*2/8
3 = i*2*pi*3/8
4 = i*2*pi*4/8 (nyquist)
5 = -i*2*pi*3/8
6 = -i*2*pi*2/8
7 = -i*2*pi*1/8

This is using zero-indexing. Given a real signal,

X(i + N/2) = X(N/2 - i)*

Where * is the conjugate of the complex number. In other words, the transform is conjugate symmetric around the nyquist bin. Thus, there’s no loss of generality by chopping of the second half of the transform, if the input signal is real. Also, on real transforms, the DC bin will always only contain a real part.

[quote=“chkn, post:11, topic:19096”]
before the transformation there is no nyquist bin
[/quote]Well, no.

e: wait sorry, I’m messing this up. Read the newest edit

13

Arrgh, Yes, but I WAS referring to the function description and it SAYS cleary what it does.
And when its described that this function uses a real input and a complex output it just does the right thing.

PS: I guess the FFT uses another format where the first bin is dc, and the first bin of the second half is the nyquist

14

Gustav originally suggested the real computation could work on half the size. I was just confirming he was right, since you claimed you need the negative frequencies to convert back (you don’t).

I would say the description is ambiguous, it doesn’t tell whether the output contains the symmetric part of the spectrum or not. “Complex output” does not contain this information.

1 Like
15

could work on half the size

well you need all frequency bins + nyquist bin and the DC bin, this is more than the half

Gustav originally suggested the real computation could work on half the size

I would say the description is ambiguous, it doesn’t tell whether the output contains the symmetric part of the spectrum

Its a FFT, and FFT does what a FFT does

16

Well, I couldn’t care less about the nyquist frequency, since it will be beyond the audible range anyway (unless you work at 8khz or the like).
Also the negative frequencies are redundant, it’s easy to derive them from the positive ones before doing the inverse fft - as already discussed…
so in my opinion for transforming real signals I would rather work with the positive half only. this would improve the overall workflow because:

  • I don’t need to make an array double the size of my data (and fill the rest with zeros)
  • I don’t get back an array with redundant information (the negative frequencies)
  • it could speed up the FFT class possibly (not sure if it is actually calculating the negative frequencies us or just mirroring the positives, in the first case it would be an improvement)
17

Well that’s a matter of perspective, a real transform is not an FT, so the behaviour would have to be documented.

For a real transform, the DC bin and nyquist bin only contains a real part, thus it fits exactly in a N/2 space.

18

it could be a separate RealFFT class to avoid confusion, maybe I’ll do that for my own sake at least :wink:
ah, that’s true about the size, thanks for reminding us!

19

Yes, normally FFT libraries have a real FFT transform that doesn’t give you all frequencies, because the negative frequencies are redundant, so that’s N/2+1 frequencies including nyquist.
Normally they also use this to make the real-fft twice as fast as complex fft, which sadly JUCE’s FFT doesn’t currently do making it at least 2 times slower than kiss_fft for most use cases.

20

Yes you are 100% right