# FFT of a real sequence

I know there are many questions (almost the same as this one) on this forum and I am sure I have read most of them, however, I still cannot answer this question:

I use the RFFT function of ARM CMSIS (on STM32):

I want to understand why the output array containing the real that imaginary part of each complex number is half as long as the input array.

From what I have read, it seems to be my understanding that the reasons are two:

1) The FFT of a real sequence N long has even symmetry in the spectrum, i.e., the second half of the elements is equal to the first half conjugate flipped in frequency .. so I can represent the data using only N/2 complex numbers arranged alternately

2) By Nyquist's Theorem, the useful results are only N/2

Do they both mean the same thing? Are they both true? Or only one of them? To me they seem like two different motivations independent of each other i.e. one has nothing to do with the other ... but maybe I am wrong?

• Do you have a link to the function documentation? It should explain what it returns. As for your question, no 1 and 2 are not directly related statements. Feb 3 at 17:42
• @user1850479 keil.com/pack/doc/CMSIS/DSP/html/… Feb 3 at 20:57

These are two different relationships.

Taking the second one by itself, you still have N FFT bins spanning the frequency range from -fS/2 to +fS/2. Note that these limits are both below the Nyquist frequency.

When you put in the additional condition that your data is real, this means that positive and negative frequency sides of the spectrum become mirror images, and thus redundant.

• if I understand correctly, the result of fft in the spectrum is scattered from -fs/2 to fs/2 ... but the content from [-fs/2 .. 0]Hz is the same as that from [fs/2 .. 0]Hz, so only the latter is chosen. Feb 4 at 10:50
• @KaleM The content from fS/2 to fS is the same as from -fS/2 to 0. These regions are indistinguishable as per sampling theorem. If you compute the full length (N) FFT, you could say that you get the frequency content from [0 .. fS], but this is still in line with Nyquist because there is no unique information there beyond fS/2, that is not already in the negative Nyquist zone [-fS/2 .. 0]. Feb 4 at 12:18

It really depends on your viewpoint.

If you have sampling rate of N samples per second, or N Hz, the maximum frequency you can capture/play is N/2 Hz.

So you need only N/2 frequency bins.

And that is because the samples are real numbers, not complex numbers. This would not be true if the input values are complex numbers.

But, because any frequency has both amplitude and phase, you need N/2 coefficients for amplitudes and N/2 coefficients for phases. That can be represented as N/2 complex numbers or N/2 amplitudes for cosines and N/2 amplitudes for sines, but you must realize that you still need N output numbers for N input numbers.

• thank you for the clarification, however I am still left with the doubt of my original question. Do both 1) and 2) mean the same thing? Are they both true? Or only one of them? To me they seem like two different motivations independent of each other i.e. one has nothing to do with the other ... and if I am right, to the question "why is the output of the FFT N/2?" what would you answer? The 1) or the 2) ? Feb 4 at 11:01
• @KaleM But the output of FFT is not N/2 real values, is either N real values, or N/2 complex values, which must be represented with N real values. So, N real values can be represented with N/2 complex numbers so statement 1 is true, and by Nyquist, you only need N/2 complex numbers, so they are both true and basically mean the same thing from different angle of view. Feb 4 at 11:14

Take a look at the complex FFT from that library:

https://www.keil.com/pack/doc/CMSIS/DSP/html/group__ComplexFFT.html

The FFT functions operate in-place. That is, the array holding the input data will also be used to hold the corresponding result. The input data is complex and contains 2*fftLen interleaved values: {real[0], imag[0], real[1], imag[1], ...}

When you run the FFT with real values, the N/2 complex values are all zero. Since you're only putting in half as many unique values, logically you only get half as many unique outputs. If you run the complex FFT, it will work but you'll get a mirrored spectrum with only N/2 unique values.

So why have a real FFT function if the complex will work? Since CPU power and especially memory are often very limited on embedded systems, it makes sense to avoid wasting memory and CPU time on those redundant samples. Especially for systems with limited SRAM, the difference between N and N/2 for each buffer can be the difference between fitting on chip and having to use slow external DRAM. The real FFT is an optimization that avoids the redundant samples.