Fourier transform apparatus

A Fourier transform apparatus for performing discrete Fourier transform, comprising:

• transform means of a preceding stage including a number a of M-point radix 2 pipeline FFT circuits each having two parallel inputs/outputs, wherein M (=2m, m>=2) represents a maximum number of points for transform and a (a is equal to or smaller than M/2) represents a divisor of said maximum transform point number M;
• first data supply means for supplying data sets each consisting of M data mutually separated by M points, on an a-by-a basis, in parallel on a two-by-two data basis in each set to said transform means of a preceding stage from input data;
• transform means of a succeeding stage including a same number of M-point radix 2 pipeline FFT circuits as the transform means of said preceding stage, each of said FFT circuits having two parallel inputs/outputs;
• second data supply means for supplying data sets, each consisting of M data mutually separated by M points, on an a-by-a basis, in parallel on a two-by-two data basis in each set to said transform means of a succeeding stage, from said transforming result of transform means of a preceding stage;
• and
• twiddle factor multiplication means including 2a complex multiplication circuits and a factory memory for supplying twiddle factors, provided between said second data supply means and the transform means of said succeeding stage for multiplication of twiddle factors, wherein
• said first data supply means is comprised of first and second data permutating modules, said first data permutating module being composed of a first memory circuit for storing data, a read or write address generating circuit which conforms to a predetermined logic of said first memory circuit and a parallel-in serial-out circuit for permutating the data read out from said first memory circuit, while said second data permutating module includes a second memory circuit constituted by two banks so that upon data storing, data are written in said two banks alternately M by M data whereas upon data reading, corresponding data of corresponding data sets each of M point data are simultaneously read out from said two banks, respectively, to constitute two parallel inputs of said pipeline FFT circuit and a read or write address generating circuit which operates in conformance to a predetermined logic of said second memory circuit, and
• said second data supply means is comprised of a third memory circuit constituted by two banks so that upon data storing, data are written in said two banks alternately on an M-by-M basis whereas upon data reading, corresponding data of corresponding data sets each of M point data are simultaneously read out from said two banks, respectively, to constitute two parallel inputs of said pipeline FFT circuit and a read or write address generating circuit which operates in conformance to a predetermined logic of said third memory circuit.