when should one perform fft based filtering?
in [DSP]
|
From: Rune Allnor on 27 Jul 2010 08:11 On 27 Jul, 14:01, Richard Dobson <richarddob...(a)blueyonder.co.uk> wrote: > On 27/07/2010 11:10, Rune Allnor wrote: > > > > > > > On 27 Jul, 02:02, Richard Dobson<richarddob...(a)blueyonder.co.uk> > > wrote: > > >> Others on this list can answer this from a proper technical dsp > >> perspective; but the basic principle is that it is an exact match, not > >> an approximation. FFT fast convolution is just as its name suggests - > >> basically a (very) fast way to do exactly what a FIR filter does; and a > >> reverb is nothing more or less than a mammoth FIR filter. It is of > >> course down to the designer (and to the hardware precision employed) to > >> ensure there are no numeric compromises that would have audible > >> consequences. Done right, the outputs of FFT and direct convolution > >> should be identical. > > > I'm a bit doubtful about all this. Again, you can not do FFTs > > on data that have not yet been collected. Which means there is > > significant delays involved in FFT-based processing. I still > > can't see that FFTs are useful for real-time work that also > > requires low latency. > > > Rune > > Well of course it is not literally 'zero latency" despite what some > commercial spin will suggest, but it is "low latency", and in the posh > Lake-Dsp style partitioned convolution which actually puts a small FIR > at the head of the process with parallel and overlapping progressively > longer blocks using FFTs, all I can say is, it works. OK, so we are comparing apples and oranges. This thread started from a question about filtering implemented as FFTs vs TD convolution, where my opinions ought to be well known by now. What you are describing is some sort of audio effect that from a purely technical POV is *not* strict convolution, but rather a composite filter. Rune
From: Richard Dobson on 27 Jul 2010 09:52 On 27/07/2010 13:11, Rune Allnor wrote: ... >> >> Well of course it is not literally 'zero latency" despite what some >> commercial spin will suggest, but it is "low latency", and in the posh >> Lake-Dsp style partitioned convolution which actually puts a small FIR >> at the head of the process with parallel and overlapping progressively >> longer blocks using FFTs, all I can say is, it works. > > OK, so we are comparing apples and oranges. This thread started from > a question about filtering implemented as FFTs vs TD convolution, > where > my opinions ought to be well known by now. What you are describing is > some sort of audio effect that from a purely technical POV is *not* > strict convolution, but rather a composite filter. > > Rune Erm, partitioned convolution is still convolution (and can as described be done entirely with FFTs). There is even a description in Numerical Recipes. And reverb is hardly "some sort of audio effect" - it is one of the most standard and mainstream processes around, albeit one with infinite varieties. A reverb impulse response is still "just" an impulse response, except it is somewhat longer than your typical FIR filter response. So the only apples/oranges comparison is in the length of the IR, and in the methods to reduce latency. But it is still convolution. At least, that is what all the published papers say it is! Richard Dobson
From: Rune Allnor on 27 Jul 2010 10:24 On 27 Jul, 15:52, Richard Dobson <richarddob...(a)blueyonder.co.uk> wrote: > On 27/07/2010 13:11, Rune Allnor wrote: > .. > > > > >> Well of course it is not literally 'zero latency" despite what some > >> commercial spin will suggest, but it is "low latency", and in the posh > >> Lake-Dsp style partitioned convolution which actually puts a small FIR > >> at the head of the process with parallel and overlapping progressively > >> longer blocks using FFTs, all I can say is, it works. > > > OK, so we are comparing apples and oranges. This thread started from > > a question about filtering implemented as FFTs vs TD convolution, > > where > > my opinions ought to be well known by now. What you are describing is > > some sort of audio effect that from a purely technical POV is *not* > > strict convolution, but rather a composite filter. > > > Rune > > Erm, partitioned convolution is still convolution (and can as described > be done entirely with FFTs). There is even a description in Numerical > Recipes. And reverb is hardly "some sort of audio effect" - it is one of > the most standard and mainstream processes around, albeit one with > infinite varieties. A reverb impulse response is still "just" an impulse > response, except it is somewhat longer than your typical FIR filter > response. So the only apples/oranges comparison is in the length of the > IR, and in the methods to reduce latency. But it is still convolution. > At least, that is what all the published papers say it is! It might be *equivalent* to a convolution, the same way that impelmenting the direct form I or II of the IIR is *equivalent* to convolving with the IIR's IR. But the computational algorithms - and thus the computational workloads - are different. Rune
From: Jerry Avins on 27 Jul 2010 16:45 On 7/27/2010 10:24 AM, Rune Allnor wrote: ... > But the computational algorithms - and thus the computational > workloads - are different. The algorithms, workloads, and latencies differ, but the results can be bit exact. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
From: robert bristow-johnson on 27 Jul 2010 18:16
On Jul 27, 4:45 pm, Jerry Avins <j...(a)ieee.org> wrote: > On 7/27/2010 10:24 AM, Rune Allnor wrote: > > ... > > > But the computational algorithms - and thus the computational > > workloads - are different. > > The algorithms, workloads, and latencies differ, but the results can be > bit exact. "bit exact" means that the round-off error would be identical in both cases. let's assume no dither (since that would, of course, affect non-deterministically the round-off). a straight-forward convolution with a double-width accumulator and a single roundoff at the very end of the summation might not be *exactly* the same bits of the same convolution done with FFT and overlap-add or overlap-save. that said, Rune, doing this frequency-domain convolution in real time *does* entail some delay (could be a half second, i dunno, depends on the size of the FFT), but it's seldom the entire algorithm. say it's a 4096 FFT, right there is 1/10 second delay, maybe doing the FFT, frequency-domain multiplication, iFFT and overlap-whatever could be done in about the same time. for the dense tail of a reverb impulse response, 200 ms delay might be good enough and any reflections that are earlier are sparse and done in the time domain with that result added. also, in terms of semantics, "convolution" is convolution whether it's done in the time domain or frequency domain. "time-domain convolution" means any convolution that does not use or require any transformation to the frequency domain. as far as i can tell, there are only a couple of methods of doing that and they require one MAC instruction for each tap. there are multiple products that implement this convolutional reverb (McDSP, Waves, Digidesign, i think). i am *sure* that fast convolution is used for at least the dense reverb tail. i do not know what the throughput delay is, but i know that they're real-time or can be real-time. at least that's how i see it. r b-j |