Suppose I have a system that wants to take an input signal (audio in this case) and wants to output a Discrete Fourier Transform of it in real time (ie every sample).

My initial thought is that if you are just every sample adding a new sample and bumping off a the oldest sample you could reuse the some of the computation from the last sample.

After googling around I wasn't able to find anything like that on the web.

So my question is this:

Does an algorithm like this exist and what is it called?

  • 3
    $\begingroup$ Search for "streaming DFT" or "online DFT". $\endgroup$ – MBaz Oct 7 '20 at 22:58
  • $\begingroup$ @MBaz Thanks....this appears to be what I was looking for $\endgroup$ – DarthRubik Oct 7 '20 at 23:03
  • $\begingroup$ ...which only leaves us with the question of how to close this question gracefully (?). Maybe @MBaz can provide an answer and DarthRubik accept it? Or if DarthRubik now thinks the question could be deleted (?) You can always comes back about clarification ofcourse. $\endgroup$ – A_A Oct 8 '20 at 8:31
  • 1
    $\begingroup$ @RickLyons (don't know whether that works to summon him) done an IEEE "DSP tricks" article on the "sliding DFT", I sadly can't find it right now, that's what I think you need. $\endgroup$ – Marcus Müller Oct 8 '20 at 8:50
  • 1
    $\begingroup$ @MarcusMüller I think this is it: ieeexplore.ieee.org/abstract/document/1184347 $\endgroup$ – MBaz Oct 8 '20 at 13: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.