Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 2 / 39A / 1

Table of contents
- Solution 1

Solution

Separate even and odd indices, using

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

. Then

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

The second identity uses

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

. Each FFT butterfly uses one shared twiddle-factor product and two additions, so assembly costs

m

multiplications and

2 m

 Ancestors (10)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version