Parallel radix 4 FFT algorithms on an eight-neighbor processor array

Hardware algorithms for one-dimensional fast Fourier transform (FFT) computation on an 8-neighbor processor array are presented. These algorithms achieve high-speed FFT computation by combining the radix 4 butterfly computation with the communication capabilities of the 8-neighbor processor array. Three algorithms are considered. Two data mapping methods and algorithms are shown: the algorithm for similarity allocation and the algorithm for superposition allocation. The radix 4 and the radix 2 FFT algorithms are compared and evaluated