Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 2 / 39A / 2 / 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)$.