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?

  • $\begingroup$ 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" $\endgroup$ – pajczur Apr 5 '18 at 18:07
  • $\begingroup$ Ah, sorry. Missed that. $\endgroup$ – Marcus Müller Apr 5 '18 at 18:08
  • $\begingroup$ OK. No problem. By the way, could you help me with my question? :) $\endgroup$ – pajczur Apr 5 '18 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.