Method and apparatus for improved calculation of multiple dimension fast fourier transforms

A memory storage device for storing data in a block to provide improved accessibility of the stored data in two or more dimensions, the memory storage device comprising:

• a) an input buffer including a plurality of memory macros constituting a row of the block, the input buffer arranged such that sequential values in the data are loaded into sequential memory macros;
• b) a barrel shifter coupled to the input buffer to circularly shift the data stored in the input buffer a predetermined number of columns relative to a preceding row of data, each column being one memory macro wide;
• and
• c) a plurality of storage elements coupled to the barrel shifter for storing circularly shifted rows of data from the input buffer, each storage element corresponding to one of the columns of the block.

A computer readable medium adapted to instruct a general purpose computer to store data in a block to provide improved accessibility of the stored data in three or more dimensions, the computer readable medium having stored computer executable program code for performing a method comprising the steps of:

• a) loading the data into a plurality of memory macros constituting a row of the block such that sequential values in the data are loaded into sequential memory macros, each memory macro is a predetermined number of bits wide;
• b) circularly shifting the data loaded in the row a predetermined number of columns relative to a preceding row, each column being one memory macro wide;
• c) storing the circularly shifted row of data;
• d) repeating steps (a), (b), and (c) until a predetermined number of rows of data are stored, thereby forming a two dimensional (2D) data block;
• e) circularly shifting the data stored in the 2D data block a predetermined number of rows relative to a preceding 2D data block;
• f) storing the circularly shifted 2D data block;
• and
• g) repeating steps (a), (b), (c), (d), (e), and (f) until a predetermined number of 2D data blocks are stored, thereby forming a three dimensional (3D) data block.

In a single instruction multiple data (SIMD) processor, a method of processing a single processor readable instruction, the method comprising, in response to the single processor readable instruction:

• a) multiplying N pairs of two's complement complex numbers, where N is an integer greater than three;
• b) separating the N products of step (a) into (N/M) groups of M products, where M is an integer greater than one and (N/M) is an integer;
• and
• c) computing an M-point fast Fourier transform (FFT) for each group of M products.

A single instruction multiple data (SIMD) processor comprising an arithmetic logic unit (ALU) for receiving N pairs of two's complement complex numbers from data storage, where N is an integer greater than three, the ALU including:

• N multipliers, for multiplying the N pairs of two's complement complex numbers in response to a single processor executable instruction;
• a register coupled to the N multipliers to store the N products of the N multipliers;
• and
• a fast Fourier transform (FFT) engine coupled to the register to perform an FFT on the N products stored in the register in response to the single processor executable instruction.

A computer readable medium adapted to instruct a single instruction multiple data (SIMD) processor to process a single processor readable instruction, the computer readable medium having stored computer executable program code for performing a method comprising, in response to the single processor readable instruction:

• a) multiplying N pairs of two's complement complex numbers, where N is an integer greater than three;
• b) separating the N products of step (a) into (N/M) groups of M products, where M is an integer greater than one and (N/M) is an integer;
• and
• c) computing an M-point fast Fourier transform (FFT) for each group of M products.