Parallelism in fast Fourier transform hardware

Abstract

The fast Fourier transform algorithm is derived by means of successive fracturing of one-dimensional data strings into two-dimensional arrays. Using this formulation, a diagrammatic representation of mixed radix and highest radix FFT algorithms is derived. Using this representation, two broad classes of FFT hard-ware are explored, from the point of view of speed, parallelism, radix number, and type of memory.