Hi. I want to use a very large FFT (65536 samples) on a Sharc 21065L. But I encountered a problem with the ADI FFT (rfft65536) with my DSP: the twiddle-factors need to be in the PM, but that is far too much data for the internal memory of the 21065. I tried the FFT from "Numerical Recipies in C", but the results are not really correct, there are errors for low frequencies. Now I'm looking for another FFT-algorithm, maybe someone of you has a solution for my problem. Best regards, Daniel

# Large FFT on ADSP-21065L

Started by ●August 28, 2006

Reply by ●August 29, 20062006-08-29

Bremi wrote:> Hi. > > I want to use a very large FFT (65536 samples) on a Sharc 21065L. But I > encountered a problem with the ADI FFT (rfft65536) with my DSP: the > twiddle-factors need to be in the PM, but that is far too much data for > the internal memory of the 21065. I tried the FFT from "Numerical Recipies > in C", but the results are not really correct, there are errors for low > frequencies.Apart from the twiddle factors, the data itself also does not fit into the internal memory of the DSP. I implemented a 32k real FFT on a SHARC, using DIT: you can split a size N DFT into two size N/2 DFTs, then recombine and scale the outputs of the N/2 DFTs to get the output of the N-point DFT. Apply this recursion m times until M = N / 2^m = 2048, which is the largest real FFT that can be computed with data and twiddle factors stored in internal memory of the 21065L. You'll have to store the intermediate data in external memory (which you hopefully have connected in form of SDRAM to your 21065L). Regards, Andor

Reply by ●September 28, 20062006-09-28

>Bremi wrote: >> Hi. >> >> I want to use a very large FFT (65536 samples) on a Sharc 21065L. ButI>> encountered a problem with the ADI FFT (rfft65536) with my DSP: the >> twiddle-factors need to be in the PM, but that is far too much datafor>> the internal memory of the 21065. I tried the FFT from "NumericalRecipies>> in C", but the results are not really correct, there are errors forlow>> frequencies. > >Apart from the twiddle factors, the data itself also does not fit into >the internal memory of the DSP. > >I implemented a 32k real FFT on a SHARC, using DIT: you can split a >size N DFT into two size N/2 DFTs, then recombine and scale the outputs >of the N/2 DFTs to get the output of the N-point DFT. Apply this >recursion m times until M = N / 2^m = 2048, which is the largest real >FFT that can be computed with data and twiddle factors stored in >internal memory of the 21065L. > >You'll have to store the intermediate data in external memory (which >you hopefully have connected in form of SDRAM to your 21065L). > >Regards, >Andor > >Hi. Thanks you for your answer. But I found a FFT in C-Code (see http://www.cs.umbc.edu/~squire/download/fft.c and http://www.cs.umbc.edu/~squire/download/fft.h). This one works fine on the 21065L, maybe it's slower than the ADI-FFT, but if you want to transform 32k or 64k Samples, I'm sure you don't have a real-time application. The problem I encountered with the Numerical Recipies was that I lost information (the input is a vector length N with Real[0], Imag[0], Real[1], Imag[1],...). So I get a vector with N/2 the information I need. I'm using the fft to get the impulse response out of a MLS (maximum length sequence). So I'm using the fft to correlate two vectors (ifft{ fft{MLS} * conj(fft{Record}) } ), after that, I window the ir, then I fft the windowed ir to get the spl. A better way would be (instead of doing a fft-correlation) to use the fast hadamard transform, but that didn't work with my code. Regards, Daniel