0.6 Programs for prime length ffts

Programs for prime length ffts

Using the circular convolution algorithms described above, we can easily design algorithmsfor prime length FFTs. The only modifications that needs to be made involvethe permutation of Rader [link] and the correct calculation of the DC term ( $y\left(0\right)$ ). These modifications are easily made to the above describedapproach. It simply requires a few extra commands in theprograms. Note that the multiplicative constants arecomputed directly, since we have programs for all the relevant operations.

In the version we have currently implemented and verified for correctness,we precompute the multiplicative constants, the input permutation and the output permutation.From Equation 8 from A Bilinear Form for the DFT , the multiplicative constants are given by $V_p(1\oplus C^t{R}^{-t}PJ{Q}_s)w$ , the input permutation is given by $1\oplus P{Q}_r$ , and the output permutation is given by $1\oplus Q_s^{t}J{P}^t$ . The multiplicative constants, the input and output permutation areeach stored as vectors. These vectors are then passed to the prime length FFT program,which consists of the appropriate function calls, see the appendix.In previous prime length FFT modules, the input and output permutations can be completely absorbed in to the computationalinstructions. This is possible because they are written as straight line code.It is simple to modify the code generating program we have implemented so that it produces straight line code and absorbs the permutationsin to the computational program instructions.

In an in-place in-order prime factor algorithm for the DFT [link] , [link] , the necessary permuted forms of the DFT can be obtainedby modifying the multiplicative constants. This can be easily done by permuting the roots of unity, $w$ , in the expression for the multiplicative constants [link] , [link] , nothing else in the structure of the algorithm needs to be changed.By changing the multiplicative constants, it is not possible, however, to omit the permutation required for Rader's conversionof the prime length DFT in to circular convolution.

Operation counts

[link] lists the arithmetic operations incurred by the FFT programs we have generated andverified for correctness. Note that the number of additions and multiplicationsincurred by the programs we have generated are the same as previously existing programs for prime lengthsup to and including 13. For $p=17$ a program with 70 multiplications and 314 additions has been written,and for $p=19$ a program with 76 multiplications and 372 additions has been written [link] . Thus for the length $p=17$ , the program we have generated requires fewer total arithmetic operations,while for $p=19$ , ours uses more.

There are several table of operation counts in [link] , each table corresponding to a different variation of the algorithmsused in that paper. For each variation, the algorithms we have described use feweradditions and fewer multiplications. The focus of [link] , however, is the implementation of prime point FFT on various computer architecturesand the advantage that can be gained from matching algorithms with architectures. It should be noted that the highest prime in [link] for which an FFT was designed is 29.Although we have not executed the programs described in this paper on these computers, they are, as mentioned above, writtento be easily adapted to parallel/vector computers.