How to interpret the result from KissFFT's kiss_fftr (FFT for a real signal) function

Question

I'm using KissFFT's real function to transform some real audio signals. I'm confused, since I input a real signal with nfft samples, but the result is nfft/2+1 complex frequency bins.

From KissFFT's README:

The real (i.e. not complex) optimization code only works for even length ffts. It does two half-length FFTs in parallel (packed into real&imag), and then combines them via twiddling. The result is nfft/2+1 complex frequency bins from DC to Nyquist.

So I have no concrete knowledge of how to interpret the result. My assumption is the data is packed like r[0]i[0]r[1]i[1]...r[nfft/2]i[nfft/2], where r[0] would be DC, i[0] is the first frequency bin, r[1] the second, and so on. Is this the case?

Yes, I think that's probably correct - it should be pretty easy to verify if you feed in a known signal and look at the result in the frequency domain. — Paul R
Note that the last two values are r[nfft/2] and i[fftn/2] (i.e. Nyquist). — Paul R
Good idea @paul. However, assuming my assumption is correct, the returned array has two extra "bins", r[0] and i[nfft/2+1]. Would these be the DC and Nyquist offsets? — Steve Barna
Not quite - since you have nfft/2+1 complex bins it's most likely that you have a complex bin for DC (index = 0) and a complex bin for Nyquist (index = nfft/2), even though the imaginary part of these is not needed. — Paul R
OK, that makes sense. Since its two half-length FFTs there would be duplicate DC and Nyquit values, thus creating an extra complex bin. And sorry, I had my array indices off by one. Thanks for the help @paul — Steve Barna

Mark Borgerding Mark Borgerding · Accepted Answer · 2011-11-02T11:15:57

Yes. The reason kiss_fftr makes only Nfft/2+1 bins is because the DFT of a real signal is conjugate-symmetric. The coefficients corresponding to negative frequencies ( -pi:0 or pi:2pi , whichever way to like to think about it) , are the conjugated coefficients from [0:pi).

Note the out[0] and out[Nfft/2] bins (DC and Nyquist) have zero in the imaginary part. I've seen some libraries pack these two real parts together in the first complex, but I view that as a breach of contract that leads to difficult-to-diagnose, nearly-right bugs.

Tip: If you are using float for your data type (default), you can cast the output array to float complex* (c99) or std::complex* (c++). The packing for the kiss_fft_cpx struct is compatible. The reason it doesn't use these by default is because kiss_fft works with other types beside float and double and on older ANSI C compilers that lack these features.

Here's a contrived example (assuming c99 compiler and type==float)

float get_nth_bin_phase(const float * in, int nfft, int whichbin )
{
  kiss_fftr_cfg st = kiss_fftr_alloc(1024,0,0,0);
  float complex * out = malloc(sizeof(float complex)*(nfft/2+1));
  kiss_fftr(st,in,(kiss_fft_cpx*)out);

  whichbin %= nfft;
  if ( whichbin <= nfft/2 ) 
    ph = cargf(out[whichbin]);
  else
    ph = cargf( conjf( out[nfft-whichbin] ) );
  free(out);
  kiss_fft_free(st);
  return ph;
}

How to interpret the result from KissFFT's kiss_fftr (FFT for a real signal) function

2 Answers