Hi Jean-Marc and list, Is the spx_fft function in fftwrap.c a standard fft function? void spx_fft(void *table, spx_word16_t *in, spx_word16_t *out) When I say standard, I mean the input "in" is 128 point short data for example and the output "out" is 128 short complex value which is stored in 256 short array with real and image part. Looks like the function did some manipulation on the output from the kiss_fft. I am still reading the codes and am not completely understand the code yet. I am trying to replace the fft module with some hardware logic. I would greatly appreciate it if you could clarify my doubts. Thank a lot! Regards, William
> Is the spx_fft function in fftwrap.c a standard fft function? > void spx_fft(void *table, spx_word16_t *in, spx_word16_t *out) > > When I say standard, I mean the input "in" is 128 point short data for > example and > the output "out" is 128 short complex value which is stored in 256 > short array with real and > image part. Looks like the function did some manipulation on the > output from the kiss_fft. I am > still reading the codes and am not completely understand the code yet. > I am trying to replace > the fft module with some hardware logic. I would greatly appreciate it > if you could clarify my > doubts.spx_fft() computes a real-data FFT. For a size N, it takes N real values as input and outputs N/2+1 real values and N/2-1 imaginary values. The packing format it uses is: RRIRIRIRIRI...RIR (note that it starts with two real values and ends with one). Also, unlike some floating-point conventions, the forward FFT normalises by 1/N (to avoid overflows), while the inverse FFT doesn't do normalisation at all (because the output is assumed to have proper scaling. As for the mangling in fftwrap.c, that was just to change the ordering of kiss-fft to fit the one Speex wants. I removed it recently because I directly modified kiss_fft to give me the results with the right ordering. Jean-Marc
(keeping this on the list) William Zhang wrote:> I read the mdf.c an my understanding is that N is actually window size for > the FFT. The actual length L = N/2 which is the frame length. The > second part of the buffer is padded with the new frame data. So this is > like the overlap-save method for improving the acuracy in calculating > the fft of > long sequence of data?The reason for the zero padding is that it's the only way to compute the convolution correctly in the frequency domain (that is, without circular convolution effects).> My hardware logic can perform N real point FFT real fast and it produce > N complex fft resultsIf that's the case, then you can still benefit by converting the N-point real FFT into an N/2 point complex FFT and an update pass.> RIRIRI...RI. How does it map to your N/2 complex > output especially > the first R and last R in your sequecne?The packing is actually R(0), R(1), I(1), R(2), I(2), ... R(N/2) Because the input is real, it means that I(0) and R(N/2) are equal to zero (so we don't need to include them). Also, everything above N/2 is the complex conjugate of what's below so it's uninteresting as well.> And do you think the hardware > approach will fit in > your AEC module?Sure, use the right ordering (and be careful with scaling!) and it'll work. Jean-Marc
Thanks for the explaination. Please see my questions and comment in lines. On 4/16/07, Jean-Marc Valin <jean-marc.valin@usherbrooke.ca> wrote:> (keeping this on the list) > > William Zhang wrote: > > I read the mdf.c an my understanding is that N is actually window sizefor> > the FFT. The actual length L = N/2 which is the frame length. The > > second part of the buffer is padded with the new frame data. So this is > > like the overlap-save method for improving the acuracy in calculating > > the fft of > > long sequence of data? > > The reason for the zero padding is that it's the only way to compute the > convolution correctly in the frequency domain (that is, without circular > convolution effects). > > > My hardware logic can perform N real point FFT real fast and it produce > > N complex fft results > > If that's the case, then you can still benefit by converting the N-point > real FFT into an N/2 point complex FFT and an update pass.This is what the kiss_fftr function does, right?> > RIRIRI...RI. How does it map to your N/2 complex > > output especially > > the first R and last R in your sequecne? > > The packing is actually R(0), R(1), I(1), R(2), I(2), ... R(N/2)> Because the input is real, it means that I(0) and R(N/2) are equal toI think you mean I(R/2), correct?> zero (so we don't need to include them). Also, everything above N/2 is > the complex conjugate of what's below so it's uninteresting as well. > > > > And do you think the hardware > > approach will fit in > > your AEC module? > > Sure, use the right ordering (and be careful with scaling!) and it'llwork. In the FIX_POINT version of the spx_fft function, where is the actual code that do the forward FFT normaliaztion by 1/N? I saw the code first maxmize the input before the FFT and renormalize it back afterwards. Isn't this making the signal bigger and easy to overflow? If I am not mistaking, the input to the kiss_fft is the 2's complement value. I use the Xilinx Logicore FFT IP which also supports the 16bit fixed point FFT and it has some internal scaling for each stage. Do I need to match the same scaling of 1/N in the software code?> Jean-Marc > >-------------- next part -------------- An HTML attachment was scrubbed... URL: http://lists.xiph.org/pipermail/speex-dev/attachments/20070417/b9df09a5/attachment.html