Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 4 / 40E / a

Solution

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

ℓ

There are no discussions about this article yet.

There are currently no matching articles.