Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 4 / 40E (Numerical Analysis)

Let $y_r^{(E)}=y_{2r}$ and $y_r^{(O)}=y_{2r+1}$. Since ${\omega }_{2m}^2={\omega }_m$,Hence, for $0\le \ell <m$, the even--odd fast Fourier transform recursion isOnly one twiddle-factor multiplication is needed for each value of $\ell$.

The radix-two Fast Fourier transform recursively applies part (a) until it reaches one-point transforms, then combines adjacent even and odd transforms in butterfly operations. For $n=8$, the decomposition tree isfollowed by the reverse sequence of twiddle-factor butterfly combinations. This is the usual three-stage FFT network.

If $C(n)$ counts complex multiplications and a twiddle product is reused in the two butterfly outputs, thenFor $n=2^k$, solving the recurrence gives

Here ${\omega }_4=i$. Splitting into even and odd pairs giveswhose two-point inverse discrete Fourier transforms are $(2,0)$ and $(-2,0)$. The butterfly therefore yields

Now $y^{(E)}=(1,-1)$ and $y^{(O)}=(1,-1)$, and both two-point transforms equal $(0,2)$. The twiddle factors $1,i$ give