1
$\begingroup$

I am trying to design a large 1D FFT by splitting N into two smaller FFTs of sizes N1 and N2. This is common approach stemming from the Cooley Tukey Algorithm. My FFT is taking time sampled data in order, remapping into a 2D matrix and then computing the 2D FFT as 1D FFTs of the columns and rows, before remapping back into a 1D output sequence. All of this is targeted at an FPGA with external memory.

My problem is that at each stage (before the first FFT, between the two FFTs, and at the output) The data that needs to be presented is not the order it is generated in. The input time samples for instance, are present N2 samples apart into the 1st FFT stage. This means that that the time ordered input N samples need to be buffered in external memory so that they can be read back in the right order. The mid-stage transform values are also generated in a different order to that required by the 2nd FFT stage. The final output transform is also not naturally ordered.

Doing external memory access is bandwidth intensive. I have tried to research alternative algorithms and mappings that would remove at least one of the 3 memory accesses but cannot find any, basically by allowing a stage to access data in it's time generated natural order Is this possible?

Thanks

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.