Output of KISS FFT interpretation

Question

I'm receiving PCM data trough socket connection in packets containing 320 samples. Sample rate of sound is 8000 samples per second. I am doing with it something like this:

int size = 160 * 2;//160;
int isinverse = 1;
kiss_fft_scalar zero;
memset(&zero,0,sizeof(zero));
kiss_fft_cpx fft_in[size];
kiss_fft_cpx fft_out[size];
kiss_fft_cpx fft_reconstructed[size];

kiss_fftr_cfg fft = kiss_fftr_alloc(size*2 ,0 ,0,0);
kiss_fftr_cfg ifft = kiss_fftr_alloc(size*2,isinverse,0,0);

for (int i = 0; i < size; i++) {
    fft_in[i].r = zero;
    fft_in[i].i = zero;
    fft_out[i].r = zero;
    fft_out[i].i = zero;
    fft_reconstructed[i].r = zero;
    fft_reconstructed[i].i = zero;
}

// got my data through socket connection

for (int i = 0; i < size; i++) {
     // samples are type of short
     fft_in[i].r = samples[i];
     fft_in[i].i = zero;
     fft_out[i].r = zero;
     fft_out[i].i = zero;
 }

 kiss_fftr(fft, (kiss_fft_scalar*) fft_in, fft_out);
 kiss_fftri(ifft, fft_out, (kiss_fft_scalar*)fft_reconstructed);

 // lets normalize samples
 for (int i = 0; i < size; i++) {
     samples[i] = rint(fft_reconstructed[i].r/(size*2));
 }

After that I fill OpenAL buffers and play them. Everything works just fine but I would like to do some filtering of audio between kiss_fftr and kiss_fftri. Starting point as I think for this is to convert sound from time domain to frequency domain, but I don't really understand what kind of data I'm receiving from kiss_fftr function. What information is stored in each of those complex number, what its real and imaginary part can tell me about frequency. And I don't know which frequencies are covered (what frequency span) in fft_out - which indexes corresponds to which frequencies.

I am total newbie in signal processing and Fourier transform topics.

Any help?

Answer 1

What you might want to investigate is FFT fast convolution using overlap-add or overlap-save methods. You will need to expand the length of each FFT by the length of the impulse of your desired filter. This is because (1) FFT/IFFT convolution is circular, and (2) each index in the FFT array result corresponds to almost all frequencies (a Sinc shaped response), not just one (even if mostly concentrated near one), so any single bin modification will leak throughout the entire frequency response (except certain exact periodic frequencies).

Answer 2

Each output "bucket" from the FFT represents a frequency band. The left-most bucket represents DC, the next up very low frequencies, the next up a little higher, etc. Each step is a fixed number of Hertz. If f is the sampling frequency and N (which should normally be a power of 2) is the number of FFT input buckets, there will be N/2 output buckets (each with both real and imaginary parts), and the highest output bucket will correspond to a frequency of f/2.

So the output of kiss_fftr is your "frequency domain" information.

As for the real vs imaginary parts, that has to do with the phase/timing of that frequency vs all the others. If you think about a nice smooth sinusoid waveform, and look at it at some instant in time, the vertical line denoting the current time will hit the wave at the peak, at the valley, near midway, or somewhere in-between.

If we define the peak as 1.0 real & 0.0 imaginary, the valley would -1.0 real and 0.0 imaginary, and midway would be 0.0 real and +/- 1.0 imaginary (with the +/- depending on whether your on the falling slope or the rising one). (Actually, I suspect that the "official" version would have 1.0 real be midway on the rising slope, but it's harder to explain that way, and the reference point is somewhat arbitrary anyway.)

In your case you appear to be using an N of 320 -- not a power of 2. I'm no expert on this, but my impression is that, while in concept you can do FFT on a non-power-of-2 buffer, in practice many FFT algorithms do not handle it well. (And I would not expect kiss_fft, being a fairly primitive algorithm, to "handle it well".) But as I said, I'm no expert, so maybe someone else has some input on this point.

Answer 3

One problem might be that the kiss_fftr() function needs a regular kiss_fft_scalar array and not a kiss_fft_cpx array as the input argument.