We have found that by using the split nesting algorithm for circular convolution a new set of efficient prime length DFT modules that cover a wide variety of lengths can be developed. We have also exploited the structure in the split nesting algorithm to write a program that automatically generates compact readable code for convolution and prime length FFT programs.
The resulting code makes clear the organization and structure of the
algorithm and clearly enumerates the disjoint convolutions into which
the problem is decomposed.
These independent convolutions can be executed in parallel and, moreover, the
individual commands are of the form
The number of additions and multiplications incurred by the programs we have
generated are the same as or are competitive with existing prime length FFT programs.
We note that previously, prime length FFTs were made available for
primes only up to 29.
As in the original Winograd short convolution algorithms, the efficiency of the
resulting prime
It should be noted too that the programs for convolution developed above are useful
in the convolution of long integer sequences when exact results are needed.
This is because all multiplicative constants in an
By developing a large library of prime point FFT programs we can extend the maximum length and the variety of lengths of a prime factor algorithm or a Winograd Fourier transform algorithm. Furthermore, because the approach taken in this paper gives a bilinear form, it can be incorporated into the dynamic programming technique for designing optimal composite length FFT algorithms [2]. The programs described in this paper can also be adapted to obtain discrete cosine transform (DCT) algorithms by simply permuting the input and output sequences [1].
