Re: cross correlation and FFT problem

I disagree with the conclusion. Jens, at least you are more diplomatic in your opinions. Bob, you shouldn't claim something is useless, just because you can't find a use for it.

I can see how you'd form your opinion *if* you've mainly worked in the fixed-point world.

I assume everyone here knows that fast convolution filtering becomes increasingly more efficient for longer filter lengths. Below some crossover point, direct convolution is more efficient. Above that point, fast convolution is quicker. I will not spend time talking about this point, since I doubt it is contested.


For a fixed point DSP processor, fast convolution has a couple of strikes against it:
1) lack of dynamic range in a fixed-point FFT. This prohibits large FFTs required for large filters
2) DSP chips are already optimized for direct FIR compution/correlation
Most (all) DSP chips have a single cycle multiply-accumulate operation. This moves the crossover point for direct vs. fast convolution much higher than the theoretical 25-30 taps.
3) Such systems are usually memory-poor.
4) For the applications built on fixed-point DSPs, latency requirements are just as important than throughput requirements.

These factors act to squeeze down the useful range of fast convolution. The filters cannot be too big, because the FFT turns to mush. For a small filter, you'd be better off using direct computation. ON A FIXED POINT PLATFORM.!!!!

On the other hand:
For floating point on a desktop/server processor, fast convolution is my filtering tool of choice. Unless you are using REALLY short filters, you'd probably be better off with fast convolution.

1) The dynamic range of a decent floating point FFT is not really an issue.
2) Efficient SIMD FFT libraries such as FFTW or IPP make the crossover point for direct vs fast filtering much lower than the theoretical 25-30 taps, more like 16 taps.
3) The extra memory required for fast convolution is negligible on a desktop/server.
4) desktop/server DSP applications are often file-based. For these, latency is a non-issue.


-- Mark


Jens Jørgen Nielsen wrote: 
Is there any good examples (like commercial products or standards)
using the frequency domain for efficient convolution/filtering?

I guess that's what Bob's comment is about!?

Jens

I tend to agree with Bob's comment about doing convolution in the
frequency domain. Even though it's theoretically more efficient than
the time domain operation in certain cases I'm not familiar with any
practical implementations

On Wed, 28 Sep 2005 21:59:13 -0700, Bob Cain
<arcane@xxxxxxxxxxxxxxxxx> wrote:


[]
the frequency domain operation is really a circular convolution. 

A rather useless operation IMHO.  :-)


Bob 


.