Re: FFT convolution giving different results from convolution



Bob Cain wrote: 


Michel Rouzic wrote:

um... i'm trying to do a convolution with a input signal of 2,103,154
samples and a kernel filter of 3 samples, both brought back to
2,103,156 samples. is that wrong?


If you are under the constraint of dealing with arbitrary length sequences then for the FFT to work, padding to a power of two greater than or equal to the sum of the lengths is correct. Your numbers sum to just a bit greater than 2^21 requiring you to pad both to 2^24 (4,194,204) to do it directly without an overlap add/save type implementation of the convolution. If one sequence is always going to be a good deal smaller than the other, using overlap add/save will give signifigant savings.

Actually, generalized FFT's can be done on arbitary lengths but the saving in calculation is highly variable and depends on the number of factors of the number. The more the better. If your length is prime, the generalized FFT won't be any faster than a naive DFT.


Good FFTs based on 2s, 3s and 5s are easy to come by once you realize
that they exist. The next composite number having only factors of 2, 3
and 5 and that is larger than 2,000,000 will almost surely be less than
5% larger. If I recall the details, by the time your get to around
10,000 the increase is always below 5% and it only gets better as the
size goes up. And you only need the sum of the supports of the two
sequences to avoid the circular convolution artifacts.


Bob 
.

Relevant Pages

  • Re: FFT convolution giving different results from convolution
    ... length sequences then for the FFT to work, padding to a power of two greater than or equal to the sum of the lengths is correct. ... If one sequence is always going to be a good deal smaller than the other, using overlap add/save will give signifigant savings. ... the generalized FFT won't be any faster than a naive DFT. ...
    (comp.dsp)
  • Re: Randomness of ten digits
    ... I've been playing around with a gap test in which I square the gap ... It would be interesting to find out the distribution curve for the sum ... different for even and odd length sequences of such numbers. ...
    (sci.math.num-analysis)
  • Re: Randomness of ten digits
    ... I've been playing around with a gap test in which I square the gap ... It would be interesting to find out the distribution curve for the sum ... I have looked at similar before but just summed the absolute values of the ... different for even and odd length sequences of such numbers. ...
    (sci.math.num-analysis)
  • Re: how these numbers are called
    ... combination of these numbers which can have the same sum. ... the sequences that I gave were just an example. ... In a binary representation, these numbers have a group of leading 1's, ... If the restriction is that this decomposition includes only ...
    (sci.math.research)
  • Re: Theory Puzzle
    ... to the interval distance in semitones. ... Both are invalid but lead to different sequences. ... Change the order of a 4 and 3 in the sum and it changes the value. ... There might be a special generating function that "Draws" the solutions out ...
    (rec.music.theory)