Patent ID: 7657587

Claim:
A method of controlling a data processing apparatus to perform a multi-dimensional Fast Fourier Transform upon an array of data values, said method comprising: (i) storing said array of data values within a data value memory, said array of data values having 2 n rows each of 2 m data values stored as a concatenated sequence of rows within said data value memory; (ii) selecting an initial set of coefficient values as a working set of Fourier coefficient values to be applied to a set of said data values; (iii) selecting an initial data address value as a working data address value; (iv) performing a Fast Fourier Transform butterfly calculation using said working set of Fourier coefficient values upon said set of data values read from said data value memory at address values dependent upon said working data address value; (v) storing result data values from said Fast Fourier Transform butterfly calculation in said data value memory; (vi) updating said working set of Fourier coefficient values and said working data address value; (vii) repeating steps (iv), (v) and (vi) until all of said data values of said 2 n rows have been traversed; (viii) updating said initial set of coefficient values and said initial data address value; and (ix) repeating steps (iv) to (viii) until said multi-dimensional Fast Fourier Transform is complete.