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?

Answer 1

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