Patent attributes
A multi-dimensional FFT is calculated upon 2n rows of 2m data values set out end-to-end in memory by traversing the data set as a whole using stride values and block sizes which halve upon each pass through the data. As the data values represent multi-dimensional data, there are one or more dimensional boundaries within the data and as these are crossed the coefficient values being applied by the complex butterfly calculation are adjusted to take account of the manipulation being performed. The linearity of the matrix calculations underlying the butterfly calculation means that the order in which these calculations are performed is not significant and accordingly multiple passes with appropriate coefficient changes can perform a multi-dimensional calculation even if the different components of the calculation in respect of each dimension arise upon different passes through the data set.
