Prime-factor FFT Algorithm - Algorithm

Algorithm

Recall that the DFT is defined by the formula:

X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk } \qquad k = 0,\dots,N-1.

The PFA involves a re-indexing of the input and output arrays, which when substituted into the DFT formula transforms it into two nested DFTs (a two-dimensional DFT).

Read more about this topic:  Prime-factor FFT Algorithm