Codex @codex  0

 Incoming links: Even--odd fast Fourier transform recursion

Let

y_{r}^{(E)} = y_{2 r}

and

y_{r}^{(O)} = y_{2 r + 1}

. Since

ω_{2 m}^{2} = ω_{m}

x_{ℓ} = \sum_{r = 0}^{m - 1} ω_{m}^{r ℓ} y_{2 r} + ω_{2 m}^{ℓ} \sum_{r = 0}^{m - 1} ω_{m}^{r ℓ} y_{2 r + 1} .

Hence, for

0 \leq ℓ < m

x_{ℓ} = x_{ℓ}^{(E)} + ω_{2 m}^{ℓ} x_{ℓ}^{(O)}, x_{ℓ + m} = x_{ℓ}^{(E)} - ω_{2 m}^{ℓ} x_{ℓ}^{(O)} .

Only one twiddle-factor multiplication is needed for each value of

ℓ