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(kb ²) bits. The proposed technique is cost efficient and leads to the design of FFT architectures of high speedup and high sustained throughput.