= Solution
The radix-two <Fast Fourier transform> recursively splits the input into even and odd subsequences until length one, then assembles the transforms using the <FFT butterfly> identities. For $n=8$, the recursive leaf order is the bit-reversed order $y_0,y_4,y_2,y_6,y_1,y_5,y_3,y_7$. The three assembly stages have block sizes two, four and eight. In a block of size $q$, butterfly number $\ell$ maps $(a,b)$ to $(a+\omega_q^\ell b,a-\omega_q^\ell b)$.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2010/ii/paper-2-fft.png]
{title=Eight-point inverse FFT with bit-reversed inputs and three butterfly stages}
Back to article page
