0.2 Multidimensional index mapping  (Page 4/6)

The concept of using an index map can also be applied to convolution to convert a length $N=N_1{N}_2$ one-dimensional cyclic convolution into a $N_1$ by $N_2$ two-dimensional cyclic convolution [link] , [link] . There is no savings of arithmetic from the mapping alone as there is with the DFT, but savings can beobtained by using special short algorithms along each dimension. This is discussed in Algorithms for Data with Restrictions .

In-place calculation of the dft and scrambling

Because use of both the type-one and two index maps uncouples the calculations of the rows and columns of the dataarray, the results of each short length $N_i$ DFT can be written back over the data as it will not be needed again after thatparticular row or column is transformed. This is easily seen from Figures [link] , [link] , and [link] where the DFT of the first row of $x(n_1,n_2)$ can be put back over the data rather written into a new array. After all thecalculations are finished, the total DFT is in the array of the original data. This gives a significant memory savings over using aseparate array for the output.

Unfortunately, the use of in-place calculations results in the order of the DFT values being permuted or scrambled. This is becausethe data is indexed according to the input map [link] and the results are put into the same locations rather than the locationsdictated by the output map [link] . For example with a length-8 radix-2 FFT, the input index map is

which to satisfy [link] requires an output map of

The in-place calculations will place the DFT results in the locations of the input map and these should be reordered orunscrambled into the locations given by the output map. Examination of these two maps shows the scrambled output to be ina “bit reversed" order.

For certain applications, this scrambled output order is not important, but for many applications, the order must be unscrambledbefore the DFT can be considered complete. Because the radix of the radix-2 FFT is the same as the base of the binary numberrepresentation, the correct address for any term is found by reversing the binary bits of the address. The part of most FFT programs that doesthis reordering is called a bit-reversed counter. Examples of various unscramblers are found in [link] , [link] and in the appendices.

The development here uses the input map and the resulting algorithm is called “decimation-in-frequency". If the output ratherthan the input map is used to derive the FFT algorithm so the correct output order is obtained, the input order must be scrambledso that its values are in locations specified by the output map rather than the input map. This algorithm is called“decimation-in-time". The scrambling is the same bit-reverse counting as before, but it precedes the FFT algorithm in this case.The same process of a post-unscrambler or pre-scrambler occurs for the in-place calculations with the type-one maps. Details can befound in [link] , [link] . It is possible to do the unscrambling while calculating the FFT and to avoid a separate unscrambler. Thisis done for the Cooley-Tukey FFT in [link] and for the PFA in [link] , [link] , [link] .