ARCHITECTURE FOR TWO DIMENSIONAL FAST FOURIER TRANSFORM

A novel architecture and circuitry for implementing a new fast fourier transform algorithm which does not require a very large core memory and also does not require a transpose of a matrix. A pipelined and parallel architecture implements the two dimensional fast fourier transform on an array of input data values, with the transformation being performed by a plurality of serially arranged pass stages. Each pass stage includes an input shuffle arrangement for receiving an ordered set of input data from a row or column of a two dimensional matrix of such input data values, and for performing a shuffle operation thereon to produce a shuffled order of the input data. Each pass stage further includes a plurality of identical switching circuits coupled in parallel to receive the shuffled order of input data. Each switching circuit includes an arithmetic logic unit which receives four input data values and performs four data transformations thereon to produce four output data values, with each of the four data transformations including a first operation of selective addition or subtraction of the four input data values, followed by a second operation of selective multiplication by an exponential multiplier.