Structures of the two dimensional FFT

In the following sections we present the definition of 2D-FFT. An algorithm that implements the 2D-FFT, known as the row-column method, is presented. We develop a mathematical formulation for this algorithm using Tensor Products and Stride Permutations.

The summation form of the 2D-FFT on a matrix ${\bf X}$ of size $M \times N$ is given by:

$${\bf Y}(k,l) = \sum_{m = 0}^{M-1} \sum_{n = 0}^{N-1} {\bf ... ... e^{\textstyle -j \frac{\textstyle 2 \pi n l}{\textstyle N}}$$

Using tensor products, this can be represented as:

$${\bf Y} = \left[ F_N \otimes F_M \right]~{\bf X},$$

where $F_J$ is a $J \times J$ matrix defined as $F_{ik}$ = $\exp(-j 2\pi ik/J)$.

Figure 5: Three Data Structures in Distributed Environment