In this research, design concepts of a parallel processing oriented FFT processor are suggested. Problems of previous FFT harware and previous FFT algorithms are pointed out in the aspect of parallelism in the FFT. Solving such problems, an array hardware structure for parallel processing in butterfly operations is proposed, and a two-dimensional FFT algorithm for parallel processing in data permutations is also proposed. The new FFT algorithm derived from a two-dimensional Fourier transform permits a data permutation by the exchange of butterfly algorithms. The proposed array structure and the algorithm provide highly parallel processing suited for high speed FFT on a large number of data, and eliminate hardware for butterflying and data permutating.

This paper introduces a new method of deriving high-speed FFT based on two-dimensional parallel processing, and describes its VLSI hardware implementation. With the development of VLSI technology, research on special processors for high-speed processing is on the increase and studies are focused on designing VLSI-oriented processors for signal processing. Among them, subjects concerning the development of a new FFT algorithm to handle extremely large volumes of data, and the design of special hardware using that algorithm are pointed out. This paper proposes a two-dimensional systolic array hardware structure and also proposes a new computing algorithm for performing data permutation by a two-dimensional systolic array to solve the above stated problem. The proposed array structure and the algorithm provide highly parallel processing suited for high speed FFT on a large number of data. In addition, a new algorithm to process arbitrary sampling points without hardware modification is suggested. Finally, the comparison of performance among the proposed FFT method by two-dimensional systolic array, systolic DFT array proposed by Kung and the existing general unity FFT processor is investigated.