when should one perform fft based filtering?
in [DSP]
|
From: steveu on 26 Jul 2010 02:11 >On 7/24/2010 11:08 AM, Steve Pope wrote: > >> I so often here a question of the form, "How do I use an FFT >> to do X", without the questioner having considered that >> they can solve their problem in the time domain. >> > >The teacher keep telling our class that the most common operation in >digital world is convolution, and fft is a fast way to do this. So why >would any one do convolution in time domain? isn't that much slower? so, >for convolution, first choice is fft, right? > >I am just talking about convolution here. btw, the overlap save >procedure (and there was another one like it?) was hard to understand >for me, but luckly we did not get that in the exam, else I might have >failed. If your teacher makes only the simple blanket statement they must be a pretty hopeless teacher. - I do many 8 tap FIRs - I do many multi-thousand tap FIRs Do you think both kinds are faster when implemented through transforms? Steve
From: Rune Allnor on 26 Jul 2010 05:14 On 26 Jul, 05:27, robert bristow-johnson <r...(a)audioimagination.com> wrote: > On Jul 25, 1:03 pm, Rune Allnor <all...(a)tele.ntnu.no> wrote: > > > > > > > On 25 Jul, 18:43, robert bristow-johnson <r...(a)audioimagination.com> > > wrote: > > > > On Jul 25, 8:39 am, Rune Allnor <all...(a)tele.ntnu.no> wrote: > > > ... > > > > > Sure, embedded devices might be able to do stuff like FFTs > > > > very efficiently, but they would struggle with the control > > > > loops necessary to fuse subsequent frames. > > > > bookkeeping. > > > > > Again, the only relevance I can see for overlap-add/save these > > > > days, is to reduce numerical noise in large *offline* work. > > > > how about a real-time convolution reverberator based on an measured > > > impulse response of an actual large room (like a venerated auditorium > > > or cathedral)? FIR with a couple hundred thousand taps? > > > What about it? > > well, it would be a helluva convolution machine to do it solely in the > time-domain. Of course it would. > being that a reverberator is an audio device, its > sampling rate would need to be about 44.1 kHz or higher. for a > monophonic reverb (what good is that?), 44100 samples/second x 200000 > multiplies/sample is about 9 giga-OPs. how many might it be if this > were done with fast convolution? Sure, if you *only* count flops, the overlap-add/save will beat the TD straight-forward stuff. But you mentioned *real* *time* convolution with these beasts. If you have a sample rate of ~50 kHz and "FIR with a couple hundred thousand taps" you will necessarily need to delay the input signal for a few seconds, to fill up the FFT buffers. As I understand it, you need to have *all* the impulse response in one FFT buffer to get this to work, right? A delay of several seconds on, say, a recorder mic with instant playback to producer / artist is hardly "real time", is it? If you add the reverb as an effect after the recording has been done, then yes, the fast convolution is the preferred way. However, in my book that's offline processing: All the data is already available, no strict requirements to latency (although one would want the job to be done ASAP. But isn't that always the case?) Rune
From: Richard Dobson on 26 Jul 2010 06:53 On 26/07/2010 10:14, Rune Allnor wrote: ... ... > But you mentioned *real* *time* convolution with these beasts. > If you have a sample rate of ~50 kHz and "FIR with a couple > hundred thousand taps" you will necessarily need to delay the > input signal for a few seconds, to fill up the FFT buffers. > As I understand it, you need to have *all* the impulse response > in one FFT buffer to get this to work, right? > > A delay of several seconds on, say, a recorder mic with instant > playback to producer / artist is hardly "real time", is it? > ... Partitioned convolution (via FFT) is a very widely employed method to do convolution-based reverb with low latency. The generic method uses a single partition size (we have one in Csound for example, that runs very nicely in real time). Lake DSP patented (inevitably, controversially) a method using exponentially increasing partition sizes and (a special feature of their patent IIRC) a time-domain FIR for the first and shortest block, to reduce latency to what is often described in consumer literature as "zero". In any case, since acoustic reverb pretty well by definition presents measurable delay (typ 10-70 msecs) between the direct signal and the very first reflection, even the vanilla partitioned convolution can be sufficient, for the large room sizes most musicians seem interested to work with. The canonical reference for the above is Bill Gardner, "Efficient Convolution Without Input/Output Delay", JAES 1995, but widely available to download. Richard Dobson
From: Jerry Avins on 26 Jul 2010 14:05 On 7/24/2010 3:10 PM, Nasser M. Abbasi wrote: ... > The teacher keep telling our class that the most common operation in > digital world is convolution, and fft is a fast way to do this.... Are you sure you understood completely? Any teacher who said that is no better than my third-grade teacher who asserted that words ending in /ly/ are adverbs. We started chanting, "only" "ugly" "daily" "lonely" "brotherly" ... until she screamed at us to stop. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
From: robert bristow-johnson on 26 Jul 2010 16:29
On Jul 26, 6:53 am, Richard Dobson <richarddob...(a)blueyonder.co.uk> wrote: > On 26/07/2010 10:14, Rune Allnor wrote: > .. > ..> But you mentioned *real* *time* convolution with these beasts. > > If you have a sample rate of ~50 kHz and "FIR with a couple > > hundred thousand taps" you will necessarily need to delay the > > input signal for a few seconds, to fill up the FFT buffers. > > As I understand it, you need to have *all* the impulse response > > in one FFT buffer to get this to work, right? > > > A delay of several seconds on, say, a recorder mic with instant > > playback to producer / artist is hardly "real time", is it? > > .. > > Partitioned convolution (via FFT) is a very widely employed method to do > convolution-based reverb with low latency. The generic method uses a > single partition size (we have one in Csound for example, that runs very > nicely in real time). Lake DSP patented (inevitably, controversially) a > method using exponentially increasing partition sizes and (a special > feature of their patent IIRC) a time-domain FIR for the first and > shortest block, to reduce latency to what is often described in consumer > literature as "zero". In any case, since acoustic reverb pretty well by > definition presents measurable delay (typ 10-70 msecs) between the > direct signal and the very first reflection, even the vanilla > partitioned convolution can be sufficient, for the large room sizes most > musicians seem interested to work with. > > The canonical reference for the above is Bill Gardner, "Efficient > Convolution Without Input/Output Delay", JAES 1995, but widely available > to download. these are good references. when Richard says "partitioned", that's what i mean when i said "segmented". Richard is referring to a Csound implementation where the segments of the very long impulse are all the same length and Bill Gardner's idea (that was patented by Lake DSP at about the same time) is that the segments of the impulse response that come earlier, are smaller than the segments that come later. also, most reverb algs (even the non-convolutional ones, like those based on Schroeder's ideas), have a "predelay" parameter which is the minimum delay that the wet reverb comes back as. that pre-delay can be taken advantage of, when using this fast convolution to implement the later part of the reverb response. also, reverb responses are usually divided into the "early reflections" portion (which can be efficiently implemented as a simple sparse multitap FIR) and the later, denser reflections (which needs a reverb alg to do efficiently). i know how to optimize the choice of FFT length (N) for an unsegmented fast convolution (and have posted this) and i can do it for partitioned fast convolution with equal-sized segments (assuming an FFT size and then determining the segment size). but i don't know exactly how to approach this Gardner thing to optimize partitioning decisions with unequal segments. that's a hard problem. r b-j |