= Solution
Let $y_r^{(E)}=y_{2r}$ and $y_r^{(O)}=y_{2r+1}$. Since $\omega_{2m}^2=\omega_m$,
$$
x_\ell=\sum_{r=0}^{m-1}\omega_m^{r\ell}y_{2r}
+\omega_{2m}^{\ell}\sum_{r=0}^{m-1}\omega_m^{r\ell}y_{2r+1}.
$$
Hence, for $0\leq\ell<m$, the <even--odd fast Fourier transform recursion> is
$$
\boxed{x_\ell=x_\ell^{(E)}+\omega_{2m}^{\ell}x_\ell^{(O)},
\qquad
x_{\ell+m}=x_\ell^{(E)}-\omega_{2m}^{\ell}x_\ell^{(O)}}.
$$
Only one twiddle-factor multiplication is needed for each value of $\ell$.
Back to article page
