In this section a method quite different from the index mapping or polynomial evaluation is developed. Rather than dealing with the DFT directly, it is converted into a cyclic convolution which must then be carried out by some efficient means. Those means will be covered later, but here the conversion will be explained. This method requires use of some number theory, which can be found in an accessible form in [12] or [13] and is easy enough to verify on one's own. A good general reference on number theory is [14].

The DFT and cyclic convolution are defined by

For both, the indices are evaluated modulo

creates a unique, one-to-one map of
the

r | m= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |

2 | 1 | 2 | 4 | 3 | 1 | 2 | 4 | 3 | |

3 | 1 | 3 | 4 | 2 | 1 | 3 | 4 | 2 | |

4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | |

5 | * | 0 | 0 | 0 | * | 0 | 0 | 0 | |

6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

Table 1 is an array of values of

and

where the term with the negative exponent (the inverse) is defined as the integer that satisfies

If

for

New functions are defined, which are simply a permutation in the order of the original functions, as

Equation 7 then becomes

which is cyclic convolution of length N-1 (plus

Applying this change of variables (use of logarithms) to the DFT can best be illustrated from the matrix formulation of the DFT. Equation 1 is written for a length-5 DFT as

where the square matrix should contain the terms of

and

which can be seen to be a reordering of the structure in Equation 12. This is in the form of cyclic convolution as indicated in Equation 10. Rader first showed this in 1968 [12], stating that a prime length-N DFT could be converted into a length-(N-1) cyclic convolution of a permutation of the data with a permutation of the W's. He also stated that a slightly more complicated version of the same idea would work for a DFT with a length equal to an odd prime to a power. The details of that theory can be found in [12], [10].

Until 1976, this conversion approach received little attention since it seemed to offer few advantages. It has specialized applications in calculating the DFT if the cyclic convolution is done by distributed arithmetic table look-up [5] or by use of number theoretic transforms [1], [12], [13]. It and the Goertzel algorithm [16], [3] are efficient when only a few DFT values need to be calculated. It may also have advantages when used with pipelined or vector hardware designed for fast inner products. One example is the TMS320 signal processing microprocessor which is pipelined for inner products. The general use of this scheme emerged when new fast cyclic convolution algorithms were developed by Winograd [21].

Comments:"The Fast Fourier Transform (FFT) is a landmark algorithm used in fields ranging from signal processing to high-performance computing. First popularized by two American scientists in 1965, the […]"