0
$\begingroup$

I have been trying to understand a publication here where Short time fourier transform is applied over n samples in steps of m samples each (m is the size of the moving window). I understand that the computational complexity of the Short time fourier transform for m samples is mlogm.

The operation also consists of extracting energy from the samples. Since there are m samples in the window, I believe it should be O(m) in the worst case. So , as per my understanding, the complexity of the whole operation should be O(n/m * (mlogm + m)) = O(nm). Since there n/m windows and each window has mlogm for fourier transform and m for signal strength extraction.

But the publication shows the complexity as O(nmlogm). Please help me understanding this.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

evidently the author is performing an FFT $n$ times (or, if the window hop is not 1 sample, it would be proportional to $n$) and each FFT costs something proportional to $m \log(m)$). all this is quite normal.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks,.. but wouldn't the number of window hops be just n/m given that the window size is m? Also, if in the worst case , m is 1 and FFT could be done n times.. that would lead to nmlogm but m = 1 would make it zero.. $\endgroup$
    – quirkystack
    Feb 21, 2014 at 3:36
  • $\begingroup$ no. the windows (or "frames") can overlap. the degree of overlap is a parameter that someone sets for a particular purpose. a 50% overlapping window would have a hop of $\frac{m}{2}$. given a hop displacement of $k$ samples, the percent overlap would be $\frac{m-k}{m} \times$ 100%. or you can derive the window hop displacement given the percent overlap. but even if the hop displacement is a function of the window length $m$ or not, the number of windows (or frames) is $\mathrm{ceil}\left(\frac{n}{k}\right)$ which is virtually proportional to $n$. $\endgroup$
    – robert bristow-johnson
    Feb 21, 2014 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.