Bruun's FFT algorithm: Difference between revisions

Revision as of 00:31, 22 April 2011

Revision as of 12:51, 19 September 2012

Line 63:

</math>

Note that all of the polynomials that appear in the Bruun factorization above can be written in this form. The Thesezeroes of these polynomials are <math>e^{2\pi i ( \pm\alpha + k ) / N}</math> for <math>k=0,1,\dots,N-1</math> in the <math>\alpha \neq 0</math> case, and <math>e^{2\pi i k / 2N}</math> for <math>k=0,1,\dots,2N-1</math> in the <math>\alpha=0</math> case. Hence these polynomials can be recursively factorized for a factor (radix) ''r'' via:

:<math>\phi_{rM, \alpha}(z) =

\left\{ \begin{matrixarray}{ll}

\prod_{\ell=0}^{r-1} \phi_{M,(\alpha+\ell)/r} & \mbox{if } 0 < \alpha \leq 0.5 \\ \\

\prod_{\ell=0}^{r-1} \phi_{M,(1-\alpha+\ell)/r} & \mbox{if } 0.5 < \alpha < 1 \\ \\

\prod_{\ell=0}^{r-1} \phi_{M,\ell/(2r)} & \mbox{if } \alpha = 0

\end{matrixarray} \right.

\end{matrix} \right.

</math>