Split-radix algorithms for length-pm DFT's
The split-radix algorithm for the discrete Fourier trans- form of length-2"' is by now fairly popular. First, we give the reason why the split-radix algorithm is better than any single-radix algorithm on length-2" DFT's. Then, the split-radix approach is generalized to length-p" DFT's. It is shown that whenever a radix-p2 outperforms a radix-p algorithm, then a radix-plp' algorithm will outperform both of them. As an example, a radix-3/9 algorithm is developed for length- 3"' DFT's. I. INTRODUCTION HE calculation of the discrete Fourier transform TpT) via a fast algorithm depends on the length of the sequence on which the transform has to be evaluated. When the length N is the product of coprime factors (N = II N,, (Ni, N, ) = 0, i # j ), one generally uses Good's mapping (8) to obtain a multidimensional transform that can then be evaluated with the Winograd (20) or the prime factor (lo) algorithm (note that the Cooley-Tukey map- ping could be used as well, but would be less efficient). When the factors of the length are not coprime (typically when N is a power of a small prime number p), then the Cooley-Tukey mapping (2) must be used and leads to a radix-r algorithm (r being equal top or one of its powers). Examples are radix-2 or radix-4 algorithms for the length- 2" DFT. In this type of algorithm, a large part of the com- putational complexity arises from intermediate multipli- cations, the so-called twiddle factors ( 121. In this paper, we will be concerned with the second case (that is, N = p") and discuss so-called split-radix algorithms. Note that these cannot be obtained via the classical Cooley-Tukey mapping and that this might be the reason why they were discovered only recently. Split- radix algorithms for length-2" DFT's were introduced simultaneously by several authors in 1984 (4), ( 1 11, ( 181, (16) and lead to the lowest known number of operations (multiplications and additions) for DFT's on these lengths (21). Recently, a number of papers have explored the split-radix idea, for example, from an implementation point of view (6), ( 141, for real data (6), ( 151, (7), or for the computation of convolutions and Hartley transforms