Is there any article/paper that describe the way to derive FFT algorithm?

Question

As the title suggest, I don't want the instant implementation, rather, the derivation that leads to the implementation. My slow head hurt my ability to learn how this algorithm comes to fruition:

c0=Xi(k+jm)
c1=Xi(k+jm+lm)
c2=Xi(k+jm+2lm)
c3=Xi(k+jm+3lm)
c4=Xi(k+jm+4lm)
d0=c1+c4
d1=c2+c3
d2=sin(2pi/5)*(c1-c4)
d3=sin(2pi/5)*(c2-c3)
d4=d0+d1
d5=sqrt(5)/4*(d0-d1)
d6=c0-d4/4
d7=d6+d5
d8=d6-d5
d9=-i(d2+sin(pi/5))/(d3*sin(2pi/5))
d10=-i(-d3+sin(pi/5)/(sin(2pi/5)d2)
.....

This radix-5 code was traced back into Temperton's 1983 paper, but even then he just abruptly drop these as subtransform of n=5 FFT. Not sure if I should ask this to SO or here, but as derivation implies more math work I guess here is better

Answer 1

Here is a description of what the procedure described on pages $297$–$298$ of the Cooley-Tukey paper I cited in my comment above looks like in the special case when $\ N=5^n\ $. In the notation adopted in that paper, we will have \begin{align} W&=e^\frac{2\pi i}{5^n}\\ r_1&=5\\ r_ 2&=5^{n-1}\\ j&=5j_1+j_0\ \ \big(j_1=0,1,\dots,5^{n-1}-1;j_0=0,1,\dots,4\big)\\ k&=5^{n-1}k_1+k_0\ \ \big(k_1=0,1,\dots,4;k_0=0,1,\dots,5^{n-1}-1\big)\ . \end{align} Denoting the discrete Fourier transform an $\ N$-long array, $\ A_0,$$A_1,$$\dots,$$A_{N-1}\ $, by $$ {\scr F}_NA\ , $$ we have \begin{align} \big({\scr F_{5^n}}A\big)_j&=\sum_{k=0}^{5^n-1}A_ke^\frac{2\pi ijk}{5^n}\\ &=\sum_{k_0=0}^{5^{n-1}-1}\sum_{k_1=0}^4A_{5^{n-1}k_1+k_0}e^\frac{2\pi i\big(5j_1+j_0\big)\big(5^{n-1}k_1+k_0\big)}{5^n}\\ &=\sum_{k_0=0}^{5^{n-1}-1}e^\frac{2\pi ij_1k_0}{5^{n-1}}\sum_{k_1=0}^4A_{5^{n-1}k_1+k_0}e^\frac{2\pi ij_0k_0}{5^n}e^\frac{2\pi ij_0k_1}{5}\\ &=\big({\scr F }_{5^{n-1}}B(j_0)\big)_{j_1}\ , \end{align} where $\ \big(B(j_0)\big)_{k_0}=\sum_\limits{k_1=0}^4A_{5^{n-1}k_1+k_0}e^\frac{2\pi ij_0k_0}{5^n}e^\frac{2\pi ij_0k_1}{5}\ $. The $\ \sin\big(\frac{2\pi}{5}\big)\ $ in your code extract will have come from the fact that $\ e^\frac{2\pi i}{5}=\cos\big(\frac{2\pi i}{5}\big)+$$i\sin\big(\frac{2\pi i}{5}\big)\ $.

When computing the $\ 5^n$-long array $\ \big\{\big(B(j_0)\big)_{k_0}\big\}_{j_0=0\text{-}4;\ k_0=0\text{-}5^{n-1}-1}\ $ from the $\ 5^n$-long array $\ A\ $ you first initialize the former array to zero, then either:

• Loop through the indices, $\ 5^{n-1}k_1+k_0\ $, of $\ A\ $, multiply the entry at each such index by each of the five complex numbers $\ e^\frac{2\pi ij_0k_0}{5^n}e^\frac{2\pi ij_0k_1}{5},$$ \,j_0=0,1,\dots,4,\ $ and add the result on to the entry at the appropriate index $\ j_0,k_0,\ $ of $\ B\ $; or
• Looping through the indices, $\ j_0,k_0\ $ of $\ B\ $, compute the entry at that index by multiplying each of the five entries $\ A_{5^{n-1}k_1+k_0},$$ k_1=0,1,\dots4 \ $ of $\ A\ $ by the appropriate complex number , $\ e^\frac{2\pi ij_0k_0}{5^n}e^\frac{2\pi ij_0k_1}{5}\ $, and adding those products together to obtain the value of the entry.

The remaining $\ n-1\ $ stages of the procedure will be similar (though not identical) to this. At each stage you will have to either loop through the the $\ 5^n\ $ indices of the array computed in the previous stage and add five different multiples of the entry at that index to an appropriate entries of the new array under construction, or loop through the $\ 5^n\ $ indices of the new array being computed and calculate the value of the entry at each index by adding together appropriate multiples of the five appropriate entries from the array computed at the previous stage.

Answer 2

Perhaps you could check this YouTube video that introduce FFT by solving polynomial coefficient multiplication problem. Introduction to FFT

Secondly, suppose you would like to explore the graphical version of it. This is also a good reference Graphical Representation of FFT