PIPELINED 2D FFT PROCESSOR

摘要

A2D FFT processor(100)suitable for large data inputsof size N by N(e.g. 2k or 8k- point side square matrix input data), comprises an m-point FFT processor unit(10)and an n- point FFT processor unit(20)in combination, where N = m*n and m and n are any positive integers. Afirst permutation unit(31)permutes theinput 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)permutesthe 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 outputsthe third permuted data in a N by N matrix as a 2D Fourier transform of the input data.