Patent ID: 8694570

Claim:
A device for evaluating a discrete Fourier transform (DFT) of a multidimensional input data set with dimensionality D, wherein D is greater than or equal to two, said device comprising: at least one computing node enabled to evaluate said DFT on said input data set or a subgroup of said input data set, wherein said subgroup comprises groupings of elements taken from a plurality of selected dimensions of said input data set for subsequent multidimensional DFT operations, wherein said at least one computing node comprises: at least one re-ordering buffer for aligning operands fetched from said data set or said subgroup for presentation to an arithmetic unit, at least one mechanism for performing arithmetic operations upon data available from several sources, data local to said computing node, data received from other instances of said computing node, said input data set or said subgroup, at least one mechanism for producing constant coefficients according to a schedule determined by dimensions and dimensionality of said input data set or said subgroup, and at least one counter for tracking recursion depth; at least one partition module enabled to provide elements of said multidimensional input data set and further enabled to partition and distribute elements within said multidimensional input data set to said at least one computing node; at least one collection module enabled to collect transformed output elements of said multidimensional input data set from said at least one computing node and operate upon the collected transformed output; an interconnection network that enables each computing node to communicate with different computing nodes at different stages of the computation; wherein said at least one computing node is enabled to evaluate a discrete Fourier transform (DFT) of said multidimensional input data set when said multidimensional data set is of arbitrary dimensionality D′, wherein D′ is less than or equal to D with dimensions N 1 ×N 2 × . . . ×N D , said at least one computing node further comprising: a memory device for storage and retrieval of said multidimensional input data set, a control sequencing module that implements said recursion depth counter, a memory access generation module for generating memory accesses, a complex rotation factor module for producing complex rotation factors, an arithmetic module for performing complex additions, subtractions, and multiplications; wherein said control sequencing module is enabled to: track a current radix vector recursion depth by at least one counter, a forward DFT transformation mode, a reverse DFT transformation mode, a DIT (Decimation-in-time) DFT transformation strategy, and a DIF (Decimation-in-frequency) DFT transformation strategy, and produce control outputs for said memory access generation module, said complex rotation factor generation module, and said arithmetic module.