Conflict-free parallel memory accessing techniques for FFT architectures

Speeding up fast Fourier transform (FFT) computations is critical for today's real-time systems targeting signal processing and telecommunication applications. Aiming at the performance improvement and the efficiency of FFT architectures, this paper presents an address generation technique which enables a radix-b processor to access in parallel b memory banks without conflicts during each stage's computations. Using kb memory banks at each stage leads to increasing the speedup of the algorithm by a factor of kb. The address generation can be realized in each radix-b stage by the use of lookup tables of size O(kb2) bits. The proposed technique is cost efficient and leads to the design of FFT architectures of high speedup and high sustained throughput. © 2008 IEEE