Pipelined 2D fast Fourier transform with three permutation stages, two FFT processor units and a twiddle factor unit.

摘要

Disclosed is a 2D FFT processor (100) for data inputs of size N by N (2k or 8k-point side square matrix input data), with an m-point FFT processor unit (10) and an n-point FFT processor unit (20) in combination. N = rn*n with m and n are positive integers. A first permutation unit (31) permutes the input data into first permuted data arranged in n*n data blocks each of size m*m words. The first m-point FFT processor unit (10) performs a Fourier transform on the first permuted data to provide first transformed data arranged in n*n data blocks each of size m*m words. A second permutation unit (32) permutes the first transformed data into second permuted data arranged in m*m data blocks each of size n*n words. A twiddle factor multiplication unit (40) comprises a complex multiplier arranged to multiply each word of the second permuted data by a predetermined twiddle factor to provide twiddle factor multiplied data. The n-point FFT processor unit (20) is arranged to perform a Fourier transform on the twiddle factor multiplied data to provide second transformed data arranged in m*m data blocks each of size n*n words. A third permutation unit (33) permutes the second transformed data into third permuted data and outputs the third permuted data in a N by N matrix as a 2D Fourier transform of the input data.