Im trying to get a feel for when Taking the FFT and doing frequency domain processing is more computationally efficient than doing discrete convolution. Does anyone have any specific examples? I understand that very long FIR filtering may have a beneifit if filter is done via FFT then IFFT. Is most real time filtering done in the time domain?
FFT vs discrete convoultion
Started by ●October 17, 2008
Reply by ●October 17, 20082008-10-17
On 17 Okt, 20:32, "westocl" <cwest...@hotmail.com> wrote:> Im trying to get a feel for �when Taking the FFT and doing frequency domain > processing is more computationally efficient than doing discrete > convolution. > > Does anyone have any specific examples?No. It's impossible to answer this without discussing the specifics of the setup - CPU,FFT implementations etc.>�I understand that very long FIR > filtering may have a beneifit if filter is done via FFT then IFFT.Again, you would need to define 'very long', which might depend on the details of the setup. But yes, filtering an N-length sequence with an M-length FIR filter takes O(MN) operations in time domain, whereas the FFT/multiply/IFFT algorithm takes O(NlogN). So everything depends on the relation between M and logN, and all the lower-order terms and constants that are ignored in the 'big oh' notation.> Is most > real time filtering done in the time domain? �Yes. But that's because there usually is a latency constraint on the processing: One can only wait so long for the answer. The question is if there is enough latency allowed to first accumulate data to fill a large buffer, and then process it. Remember, in on-line operations the time-constraints on the results beat any overall computation loads. If the choise stands between two algorithms where one has a low FLOP count but takes too long to get a result (possibly because of data buffering), and the other gives a higher FLOP count but comes up with the result within time spec, the latter is chosen. Half the job in engineering is to prioritize between operational constraints. Rune
Reply by ●October 17, 20082008-10-17
On Oct 17, 2:32�pm, "westocl" <cwest...@hotmail.com> wrote:> Im trying to get a feel for �when Taking the FFT and doing frequency domain > processing is more computationally efficient than doing discrete > convolution. > > Does anyone have any specific examples? �I understand that very long FIR > filtering may have a beneifit if filter is done via FFT then IFFT. Is most > real time filtering done in the time domain? �You are kidding. Look in a DSP book for the FFT caclulations, look again for the convolution calculations or compute those yourself, and figure it out. This is such a trivial, basic calculation, I vote you "The Laziest Person of the Day in comp.dsp". Please don't ever post here again. Dirk BTW, lazy people will not succeed in DSP, quit while you are ahead.
Reply by ●October 17, 20082008-10-17
westocl wrote:> Im trying to get a feel for �when Taking the FFT and doing frequency > domain processing is more computationally efficient than doing discrete > convolution.I calculated this for the SHARC DSP here: http://groups.google.com/group/comp.dsp/browse_frm/thread/0985ad0ca9d10309/e416169ba33926a0?hl=de&#e416169ba33926a0 On the SHARC, the breakeven point (where frequency domain FIR filtering is becomes more efficient than time domain FIR filtering) is between 31 and 32 taps.> Does anyone have any specific examples? �I understand that very long FIR > filtering may have a beneifit if filter is done via FFT then IFFT. Is > most real time filtering done in the time domain?I don't know. Even though it is more efficient, frequency domain filtering demands much more effort to implement. Whether its worth the effort is a simple economic calculation. It should also be noted (in reply to Rune's post) that the latency of frequency domain calculation can be reduced (at the cost of computational efficiency). If latency is an issue (for example in real- time room simulators for musical purposes), you can divide the impulse response into blocks, just like you divide the signal into blocks. The most complex algorithms uses several different block sizes, simultaneously using zero latency time domain filtering and large blocks for frequency domain filtering. The classic reference is [1]. Regards, Andor [1] W. G. Gardner, "Efficient convolution without input-output delay", J.AES vol. 43, n. 3, 1995 March, pp. 127-136.
Reply by ●October 17, 20082008-10-17
>Im trying to get a feel for when Taking the FFT and doing frequencydomain>processing is more computationally efficient than doing discrete >convolution. > >Does anyone have any specific examples? I understand that very long FIR >filtering may have a beneifit if filter is done via FFT then IFFT. Ismost>real time filtering done in the time domain? >First, remember that 95% of the people that post here are glad to provide whatever assistance they can. The other 5% range from kooks to people in a chronically bad mood. You should ignore these post. Answering them just provides more motivation for their rants. Now for your question. Twenty years ago there was an easy answer to this-- it simply came down to which of the algorithms used more clock cycles. However, computers are now so fast that other factors are important, such the transfer of data within the processor. To get started, here is a link that describes the clock-cycle method. Regards, Steve http://www.dspguide.com/ch18/3.htm
Reply by ●October 17, 20082008-10-17
>westocl wrote: >> Im trying to get a feel for =A0when Taking the FFT and doing frequency >> domain processing is more computationally efficient than doingdiscrete>> convolution. > >I calculated this for the SHARC DSP here: > >http://groups.google.com/group/comp.dsp/browse_frm/thread/0985ad0ca9d10309/= >e416169ba33926a0?hl=3Dde&#e416169ba33926a0 > >On the SHARC, the breakeven point (where frequency domain FIR >filtering is becomes more efficient than time domain FIR filtering) is >between 31 and 32 taps. > >> Does anyone have any specific examples? =A0I understand that very longFI=>R >> filtering may have a beneifit if filter is done via FFT then IFFT. Is >> most real time filtering done in the time domain? > >I don't know. > >Even though it is more efficient, frequency domain filtering demands >much more effort to implement. Whether its worth the effort is a >simple economic calculation. > >It should also be noted (in reply to Rune's post) that the latency of >frequency domain calculation can be reduced (at the cost of >computational efficiency). If latency is an issue (for example in real- >time room simulators for musical purposes), you can divide the impulse >response into blocks, just like you divide the signal into blocks. The >most complex algorithms uses several different block sizes, >simultaneously using zero latency time domain filtering and large >blocks for frequency domain filtering. The classic reference is [1]. > >Regards, >Andor > >[1] W. G. Gardner, "Efficient convolution without input-output delay", >J.AES vol. 43, n. 3, 1995 March, pp. 127-136. >Thanks all. The 32 taps type answer (i understand this is for a SHARK) is what i was trying to get a feel for and the latentcy type tradeoff.
Reply by ●October 17, 20082008-10-17
On Oct 17, 2:32�pm, "westocl" <cwest...@hotmail.com> wrote:> Im trying to get a feel for �when Taking the FFT and doing frequency domain > processing is more computationally efficient than doing discrete > convolution. > > Does anyone have any specific examples? �I understand that very long FIR > filtering may have a beneifit if filter is done via FFT then IFFT. Is most > real time filtering done in the time domain? �if you're asking about where it's more efficient to use fast convolution (using Overlap-Add or Overlap-Save to undo the circularness of the circular convolution that naturally happens with the FFT) there is a form that is, i think, general enough to model the cost per sample over a wide variety of hardware. one of the first times i mentioned this was at: http://groups.google.com/group/comp.dsp/msg/2c39faa0ad42f00c later: http://groups.google.com/group/comp.dsp/msg/f3481616ba98456e while Rune is strictly right, there is a general way to look at this. and i think i don't agree with Dirk that this is the most obvious thing to answer. but it's answerable. r b-j
Reply by ●October 17, 20082008-10-17
On Fri, 17 Oct 2008 15:02:20 -0500, "SteveSmith" <Steve.Smith1@SpectrumSDI.com> wrote:>First, remember that 95% of the people that post here are glad to provide >whatever assistance they can. The other 5% range from kooks to people in a >chronically bad mood. You should ignore these post. Answering them just >provides more motivation for their rants.Thanks, Steve, for a good Friday afternoon chuckle. ;) Eric Jacobsen Minister of Algorithms Abineau Communications http://www.ericjacobsen.org Blog: http://www.dsprelated.com/blogs-1/hf/Eric_Jacobsen.php
Reply by ●October 18, 20082008-10-18
On Oct 17, 6:17�pm, robert bristow-johnson <r...@audioimagination.com> wrote:> On Oct 17, 2:32�pm, "westocl" <cwest...@hotmail.com> wrote: > > > Im trying to get a feel for �when Taking the FFT and doing frequency domain > > processing is more computationally efficient than doing discrete > > convolution. > > > Does anyone have any specific examples? �I understand that very long FIR > > filtering may have a beneifit if filter is done via FFT then IFFT. Is most > > real time filtering done in the time domain? � > > if you're asking about where it's more efficient to use fast > convolution (using Overlap-Add or Overlap-Save to undo the > circularness of the circular convolution that naturally happens with > the FFT) there is a form that is, i think, general enough to model the > cost per sample over a wide variety of hardware. �one of the first > times i mentioned this was at: > > http://groups.google.com/group/comp.dsp/msg/2c39faa0ad42f00c > > later: > > http://groups.google.com/group/comp.dsp/msg/f3481616ba98456e > > while Rune is strictly right, there is a general way to look at this. > and i think i don't agree with Dirk that this is the most obvious > thing to answer. �but it's answerable. > > r b-jHi r b-j, When I was in college I did not like English Literature class because the instructers "interpreted" the stories making huge leaps of faith as to what the author "really meant" based on nothing you could discern from the text (I found a catalog loophole to avoid taking the second semester). The OP's post got some good responses, but they seem remenicient of literature class, with people "interpreting" what the OP meant by his simple question, making the complexities of the post's "meaning" go far beyond what the language of the original post can really justify. I think if the OP really meant all of the complexities covered in the responses, he would have asked a different, much more precise, question. I still think it was the question of a lazy person. If Steve likes helping people who don't try to answer their own question before they ask it here, he is quite charitable; I actually need for OPs to first make an identifiable effort before I can derive any satisfaction from my giving them the time for anything more than a short answer. I want them to learn something. IMHO, over the last few years this group has been attracted too many people that want something so they don't have to do the any work (solution, solution manual, MATLAB code, C code,...). To me, the original post sounded amazingly like more of this. Dirk
Reply by ●October 18, 20082008-10-18
>On Oct 17, 2:32=A0pm, "westocl" <cwest...@hotmail.com> wrote:> >Dirk > >BTW, lazy people will not succeed in DSP, quit while you are ahead. >There are very cool DSP guys here :) Dirk, generally I agree with you. It's easy to defined what better is - direct convolution or convolution via FFT. But... There are so many factors that is necessary to take into consideration... For example: 1) FIR is implemented very equally for all DSPs. Usually it takes 1 cycle for 2 taps. But DSPs are not optimized for FFT. All of them take very different number of cycles for butterfly. TMS55 demands 5 cycles, ZSP540 - 2.5 cycles, Russian DSP Multicore - 1, etc. So your FFT application could be efficient on the Multicore and be not efficient on the TMS55. 2) Very often FIR use for decimation. In this case convolution via FFT could be efficient not so much. 3) FFT corrupts a signal more than FIR. It a very difficult thing to get good result in 16-bit FFT for 256 points. .............. N) FFT is not the best. Maybe Vinograd's algorithm is better?... :))) It seems Rune Allnor is not so wrong. But as it was told above, it's easy to define which convolution is better. If convolution has length more than 100 then I use FFT, otherwise I use direct method. So I think you both are right :)
