0.2 Multidimensional index mapping

A powerful approach to the development of efficient algorithms is to break a large problem into multiple small ones.One method for doing this with both the DFT and convolution uses a linear change of index variables to map the original one-dimensional problem into a multi-dimensional problem. Thisapproach provides a unified derivation of the Cooley-Tukey FFT, the prime factor algorithm (PFA) FFT, and the Winograd Fourier transformalgorithm (WFTA) FFT. It can also be applied directly to convolution to break it down into multiple short convolutions that can be executedfaster than a direct implementation. It is often easy to translate an algorithm using index mapping into an efficient program.

The basic definition of the discrete Fourier transform (DFT) is

where $n$ , $k$ , and $N$ are integers, $j=\sqrt{-1}$ , the basis functions are the $N$ roots of unity,

and $k=0,1,2,\cdots ,N-1$ .

If the $N$ values of the transform are calculated from the $N$ values of the data, $x\left(n\right)$ , it is easily seen that $N^2$ complex multiplications and approximately that same number of complex additions are required. Onemethod for reducing this required arithmetic is to use an index mapping (a change of variables) to change the one-dimensional DFTinto a two- or higher dimensional DFT. This is one of the ideas behind the very efficient Cooley-Tukey [link] and Winograd [link] algorithms. The purpose of index mapping is to change a large problem into several easier ones [link] , [link] . This is sometimes called the “divide and conquer" approach [link] but a more accurate description would be “organize and share" which explains the process of redundancy removal or reduction.

The index map

For a length-N sequence, the time index takes on the values

When the length of the DFT is not prime, $N$ can be factored as $N=N_1{N}_2$ and two new independent variables can be defined over the ranges

A linear change of variables is defined which maps $n_1$ and $n_2$ to $n$ and is expressed by

where $K_i$ are integers and the notation ${\left(\left(x\right)\right)}_N$ denotes the integer residue of $x$ modulo $N$ [link] . This map defines a relation between all possible combinations of $n_1$ and $n_2$ in [link] and [link] and the values for $n$ in [link] . The question as to whether all of the $n$ in [link] are represented, i.e., whether the map is one-to-one (unique), has beenanswered in [link] showing that certain integer $K_i$ always exist such that the map in [link] is one-to-one. Two cases must be considered.

Case 1.

$N_1$ and $N_2$ are relatively prime, i.e., the greatest common divisor $(N_1,N_2)=1$ .

The integer map of [link] is one-to-one if and only if:

where $a$ and $b$ are integers.

Case 2.

$N_1$ and $N_2$ are not relatively prime, i.e., $(N_1,N_2)>1$ .

The integer map of [link] is one-to-one if and only if:

or