On 2020-03-19, Dario Sanfilippo wrote:
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?
The best computational complexity in direct form convolution is
guaranteed to be zero-delay convolution in the Gardner form, so O(N log
M) where N is the number of samples processed and M is the support of
the eventual weight/measure of the nonzero portion of the LTI impulse
response. (There are methods which lead to longer responses at lower
cost, but they all trade in something for something. At full innovation
density/critical sampling, you cannot do any better.) This is because
this sort of processing can be reduced to a binary sorting problem,
which is guaranteed to asymptotically take as much time. (It is a
research problem whether non-binary sorting algorithms could perchance
be generalized to this setting as well; no such generalizations exist as
of now.)
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=2ahUKEwi74uPM56foAhWnxcQBHeG1BU0QFjAAegQIAxAB&url=http%3A%2F%2Fwww.cs.ust.hk%2Fmjg_lib%2Fbibs%2FDPSu%2FDPSu.Files%2FGa95.PDF&usg=AOvVaw1lFWuE1IrzjRZDOD-VAP05
Gardner's algorithm is then best in more than one way. It doesn't just
yield the best asymptotic performance, but exactly zero delay as well.
And the guy didn't even stop there. He also broke the traditional
overlap-add-FFT-convolution algorithm in running parts, so that it 1)
becomes an exponential cascade of overlapping processes, whose running
time sums to constant one, instead of peaking at any stage, even as a
whole, and 2) it optimally reuses previous half-results in order to
derive the next one. (That has a lot to do with both the OLA structure,
and at the same time with how FFT is a realization of a full Fourier
rotation in a function space, by coordinate-wise, parallel rotations, in
a logarithmic/divide-and-conquer cascade.)
I've in fact thought that I should apply the algorithm to certain coding
theoretic problems, just now. Because, since it's guaranteed to be
zero-delay, you can apply it willy-nilly in decision feedback decoding,
on the coding side. And since it's guaranteed to be optimal on the LTI
side of things, and it's a fully neutral, general, and provably
efficient LTI-DSP primitive, why not take advantage of it...? ;)
--
Sampo Syreeni, aka decoy - de...@iki.fi, http://decoy.iki.fi/front
+358-40-3751464, 025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2
_______________________________________________
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp
