READING: Chapters 6-7
(Oppenheim and Schafer provide an alternate discussion of the FFT.)
y[n] = y[n-1] + x[n] - x[n-N] with y[-1] = 0
Notes: In the text's explanation, the number of rows, L, is the radix of the transform (2 in our case). Thus since the number of elements in the original transform is N, the number of columns, M, would be .
Additionally, most trivial multiplications are not counted. (Strictly speaking, fewer than non-trivial complex multiplies are required. Why is that?)
Lastly, figure 7.12 does not exactly reflect the text's algorithm in that it shows some terms being the sum of one term multiplied by and another term multiplied by , thus involving two multiplies. The algorithm on pages 121-122 instead subtracts one term from the other (via DFT ) and multiplies the difference by , requiring only 1 complex multiply. This will yield the correct result as well as the correct number of multiplies for this problem.
Again, don't count trivial multiplications.