FFT convolution

[babazaroni]

Hello,

I'm implementing auto-correlation using fft convolution, which requires the results of 2 fft's multiplied together followed by an inverse fft.

In xcore-sc-dsp-transforms is the routine fftTwoRealsForward and this seems ideal as it will do the two fft's simultaneously. But the routine requires a sine table, and this seems out of place for a convolution.

Should the sine table be the normal sine table for a 256 sample? Or for convolution should it be all zeroes or ones?

Maybe I'm using the wrong function?

Any ideas from the xmos dsp experts?

Thanks

--Chuck

[babazaroni]

An update. The xmos fft routines do indeed work for auto correlation. The forward and inverse fft is supplied with a sine table appropriate for the length of the input signal. What is the purpose of this sine table? Is it a windowing function?

[andrewxcav]

An update. The xmos fft routines do indeed work for auto correlation. The forward and inverse fft is supplied with a sine table appropriate for the length of the input signal. What is the purpose of this sine table? Is it a windowing function?

I believe the sine table contains one period of a sine wav that is the same length as your input data.

The FFT can be thought of as a series of correlations (1 per bin) with complex exponentials (which can be represented as sin() and cos() ).

i.e.
bin 0 corresponds to a correlation with a straight line (DC)
bin 1 corresponds to a correlation with one period of a cos (real) and sin (imaginary)
...

The high resolution sine table allows the algorithm to produce all sin and cos values needed since cos is just shifted sin, and higher frequencies can be made by decimating the high resolution sine wave.

To answer your question about windowing, no it is not a windowing function, you would have to apply that to the input data yourself.

Depending on your application there may already be a way to do this very cleanly. i.e. lib_mic_array provides an interface to decimators for audio processing that allows you to specify a window length, a window function, and even some overlap options.