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, Nov 01 '11 at 21:26
Note that the last two values are `r[nfft/2]` and `i[fftn/2]` (i.e. Nyquist). — Paul R, Nov 01 '11 at 21:51
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, Nov 01 '11 at 21:58
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, Nov 01 '11 at 22:01
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, Nov 01 '11 at 22:13

score 5 · Accepted Answer · answered Nov 02 '11 at 11:15

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;
}

score 0 · Answer 2 · answered Nov 01 '11 at 23:09

0

r[1]and i[1] of the fftr result constitute a complex vector. Together they give you a magnitude (sqrt of the sum of the squares of the 2 components) and a phase (via atan2()) of the first frequency bin.

answered Nov 01 '11 at 23:09

hotpaw2

70,107
14
90
153

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

2 Answers2