Hi, Ethan. Thanks for your email, all good points. From the top of your head, could you please point me to a reference for the measurement of calculations needed in direct-form filters?
Best, Dario On Thu, 19 Mar 2020 at 17:28, Ethan Duni <ethan.d...@gmail.com> wrote: > > > On Thu, Mar 19, 2020 at 8:11 AM Dario Sanfilippo < > sanfilippo.da...@gmail.com> wrote: > >> >> I believe that the time complexity of FFT is O(nlog(n)); would you >> perhaps have a list or reference to a paper that shows the time >> complexity of common DSP systems such as a 1-pole filter? >> > > The complexity depends on the topology. The cheapest topologies (direct > forms) are something like 2*M operations per sample, where M is the filter > order. Other topologies are optimized for other properties (such as noise > robustness, modulation robustness, etc.) and exhibit higher complexity - > generic state-variable topologies can scale as M^2 operations per sample, > for example. > > >> If simply comparing two algorithms by the number of operations needed to >> compute a sample, would you include delays in filters as an operation? I'm >> just wondering as some papers about FFT only include real multiplications >> and additions as operations. >> > > Delays usually get accounted as memory requirements in this type of > analysis. That isn't to say that copying data around in a real computer > doesn't take time, but this is usually abstracted away in the generic DSP > algorithm accounting. The underlying assumption being that the DSP > throughput is essentially computation bound, and so reducing the total > number of MACs is the goal. But that's not terribly appropriate for a > software system running on a modern personal computer, for example. > > Ethan > > > >> >> Thanks for your help, >> Dario >> _______________________________________________ >> dupswapdrop: music-dsp mailing list >> music-dsp@music.columbia.edu >> https://lists.columbia.edu/mailman/listinfo/music-dsp > > _______________________________________________ > dupswapdrop: music-dsp mailing list > music-dsp@music.columbia.edu > https://lists.columbia.edu/mailman/listinfo/music-dsp
_______________________________________________ dupswapdrop: music-dsp mailing list music-dsp@music.columbia.edu https://lists.columbia.edu/mailman/listinfo/music-dsp
