초록 ▼

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 inp

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.

대표청구항 ▼

A pipelined and parallel system for implementing a 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, with each pass stage comprising, a. shuffle means for receiving an ordered set of input

A pipelined and parallel system for implementing a 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, with each pass stage comprising, a. shuffle means for receiving an ordered set of input data for that pass stage and for performing a shuffle operation thereon to produce a shuffled order of input data, with the first pass stage receiving an ordered set of input data from a row or column of a two dimensional matrix of such input data values, and pass stages subsequent to the first pass stage receiving an ordered set of input data from the preceding pass stage; and b. a plurality of identical switching circuit means coupled in parallel to receive the shuffled order of input data, each switching circuit means including an arithmetic logic unit with four inputs for receiving four input data values and including means for performing four data transformations of the four input data values to produce four output data values, said means for performing each of the four data transformations including a first means for performing a first operation of selective addition or subtraction of the four input data values, followed by a second means for performing a second operation of selective multiplication by an exponential multiplier.