Content deleted Content added
CRGreathouse (talk | contribs) m dab by unlinking |
m Fixing improperly nested section headings (task 5) |
||
Line 37:
Moreover, as long as the polynomial factors at each stage are [[relatively prime]] (which for polynomials means that they have no common roots), one can construct a dual algorithm by reversing the process with the [[Chinese Remainder Theorem]].
The standard decimation-in-frequency (DIF) radix-''r'' Cooley–Tukey algorithm corresponds closely to a recursive factorization. For example, radix-2 DIF Cooley–Tukey factors <math>z^N-1</math> into <math>F_1 = (z^{N/2}-1)</math> and <math>F_2 = (z^{N/2}+1)</math>. These modulo operations reduce the degree of <math>x(z)</math> by 2, which corresponds to dividing the problem size by 2. Instead of recursively factorizing <math>F_2</math> directly, though, Cooley–Tukey instead first computes ''x''<sub>2</sub>(''z'' ω<sub>''N''</sub>), shifting all the roots (by a ''twiddle factor'') so that it can apply the recursive factorization of <math>F_1</math> to both subproblems. That is, Cooley–Tukey ensures that all subproblems are also DFTs, whereas this is not generally true for an arbitrary recursive factorization (such as Bruun's, below).
Line 52:
Moreover, since all of these polynomials have purely real coefficients (until the very last stage), they automatically exploit the special case where the inputs ''x''<sub>''n''</sub> are purely real to save roughly a factor of two in computation and storage. One can also take straightforward advantage of the case of real-symmetric data for computing the [[discrete cosine transform]] (Chen and Sorensen, 1992).
The Bruun factorization, and thus the Bruun FFT algorithm, was generalized to handle arbitrary ''even'' composite lengths, i.e. dividing the polynomial degree by an arbitrary ''radix'' (factor), as follows. First, we define a set of polynomials φ<sub>''N'',α</sub>(''z'') for positive integers ''N'' and for α in <nowiki>[0,1)</nowiki> by:
| |||