# 1D as a 2D FFT - am I understand it properly

in one of my question about non $2^L$ points FFT I got answer with advice to read about that in following book: Rabiner, Lawrence R., and Bernard Gold. "Theory and application of digital signal processing." Englewood Cliffs, NJ, Prentice-Hall, Inc., 1975. 777 p. (1975).

I read that and I found that equation:

There was also explanation how to calculate it, but I could’t understand it - probably because my lack both of English language and math at all.

I was wondering long time what’s the deal with that equation. Let’s say for example I have N=36 point DFT. And make matrix 3x12. There are in equation 4 variables s, r, m, l. So I still need make calculations for each s (which goes from 0 to 11), for each r (from 0 to 2), for each m (0 to 11) and for each l (0 to 2). So it looks like I need to make $12 \cdot 3\cdot12 \cdot 3$ operations. So it’s $36^2$, the same as regular DFT. So where is the deal, where is that FFT efficiency?

But now after some considerations, testing and thinking. I see I can calculate at first:

So for each m (0 to 11), each l (0 to 2) and each s (0 to 2) it gives me $12 \cdot 3 \cdot 3$ calculations. And then I need to calculate that:

and for each m, s and r (0 to 11) I need $12 \cdot 3 \cdot 12$ calculations. And then I need multiply each result by each result from previous equation. So it’s $(12 \cdot 3 \cdot 12)+(12 \cdot 3 \cdot 3)$ which is equal 540, and it’s much less than $36 \cdot 36$. And is it that deal? I am not sure of my way of thinking. Please could anyone help me with understanding it?

• Marcus I am not sure what you mean. But I said the same on the beginning of my question: "... question about NON $\ 2^L$ points FFT" – pajczur Apr 5 '18 at 18:07
• Ah, sorry. Missed that. – Marcus Müller Apr 5 '18 at 18:08
• OK. No problem. By the way, could you help me with my question? :) – pajczur Apr 5 '18 at 18:10