<< Chapter < Page | Chapter >> Page > |
Corollary: If the modulus polynomial is , then multiplications are necessary to compute modulo , where is the number of positive divisors of .
Theorem 5 is very general since it allows a general modulus polynomial. The proof of the upper boundinvolves reducing and modulo the factors of . Each of the irreducible residue polynomials is then multiplied using the method of Theorem 4 requiring multiplies and the products are combined using the CRT. The total number of multiplies from the parts is . The theorem also states the structure of these optimal algorithms is essentiallyunique. The special case of is interesting since it corresponds to cyclic convolution and, as stated in the corollary, is easily determined. The factors of are called cyclotomic polynomials and have interesting properties [link] , [link] , [link] .
Theorem 6 [link] , [link] Consider calculating the DFT of a prime length real-valued number sequence. If is chosen as the field of rational numbers, the number of realmultiplications necessary to calculate a length-P DFT is where is the number of divisors of .
This theorem not only gives a lower limit on any practical prime length DFT algorithm, it also gives practicalalgorithms for , and 7. Consider the operation counts in [link] to understand this theorem. In addition to the real multiplications counted by complexity theory, each optimalprime-length algorithm will have one multiplication by a rational constant. That constant corresponds to the residue modulo (s-1)which always exists for the modulus . In a practical algorithm, this multiplication must be carried out, andthat accounts for the difference in the prediction of Theorem 6 and count in [link] . In addition, there is another operation that for certain applications must be counted as amultiplication. That is the calculation of the zero frequency term in the first row of the example in The DFT as Convolution or Filtering: Matrix 1 . For applications to the WFTA discussed in The Prime Factor and Winograd Fourier Transform Algorithms: The Winograd Fourier Transform Algorithm , that operation must be counted as a multiply. For lengths longer than 7,optimal algorithms require too many additions, so compromise structures are used.
Theorem 7 [link] , [link] If is chosen as the field of rational numbers, the number of real multiplicationsnecessary to calculate a length-N DFT where N is a prime number raised to an integer power: , is given by
where is the number of divisors of .
This result seems to be practically achievable only for , or perhaps 25. In the case of , there are two rational multiplies that must be carried out and arecounted in [link] but are not predicted by Theorem 7 . Experience [link] indicates that even for , an algorithm based on a Cooley-Tukey FFT using a type 2 index map givesan over-all more balanced result.
Theorem 8 [link] If is chosen as the field of rational numbers, the number of real multiplications necessary tocalculate a length-N DFT where is given by
Notification Switch
Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?