Yay! It may not seem that you helped, but you guys did. Octave helped, too. Nice to have a known-good implementation to compare to. Multiplication, as it turns out, is multiplication. -- Les Cargill
My convolution using FFT now works.
Started by ●April 1, 2012
Reply by ●April 1, 20122012-04-01
On 4/1/12 12:02 AM, Les Cargill wrote:> > Yay! It may not seem that you helped, but you guys did. > > Octave helped, too. Nice to have a known-good implementation to compare to. > > Multiplication, as it turns out, is multiplication. >so Les, what did you do to get linear convolution out of a circular convolving mechanism (which is what you get with an FFT)? the only methods i know of are overlap-add (OLA) or overlap-save (OLS). Phil mentioned this and Dilip aptly recognized that i would resonate quickly to the issue (adapting a tool that is circular to do a job that is linear). so i am curious about what you did with that. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●April 1, 20122012-04-01
robert bristow-johnson wrote:> On 4/1/12 12:02 AM, Les Cargill wrote: >> >> Yay! It may not seem that you helped, but you guys did. >> >> Octave helped, too. Nice to have a known-good implementation to >> compare to. >> >> Multiplication, as it turns out, is multiplication. >> > > so Les, what did you do to get linear convolution out of a circular > convolving mechanism (which is what you get with an FFT)? the only > methods i know of are overlap-add (OLA) or overlap-save (OLS). >I'm not sure what it's called - the "power of two method?" The FFT for both the input data array and the convolution kernel were dimensioned to be the next power of two up: D = (n+1) + (m+1) - 1 N = 2 ^ ceil(log2(D)) So if n=2, m=2: D = (3+3)-1 = 5 ceil(log2(5)) = 3 N = 8 So in the trivial [ 10 10 ] x [ 10 10 ] case, the vectors to be fft'd would both be: [ 10 10 0 0 0 0 0 0 ] ( the real parts, anyway ) I picked apart fftfilt.m from Octave... I suppose that's cheating, but ... it works :) The main thing was going back and enforcing better code hygiene and rigor....> Phil mentioned this and Dilip aptly recognized that i would resonate > quickly to the issue (adapting a tool that is circular to do a job that > is linear). so i am curious about what you did with that. >I'll tackle OLA/OLS later on. I think I understand it, but need to know if you can "reset" a plan in FFTW ( I think you can ). It then becomes an exercise in buffer slinging. Small steps. This isn't "for" anything production, just trying to get to where I can have a feel for the way this works. -- Les Cargill
Reply by ●April 1, 20122012-04-01
On 4/1/2012 8:57 AM, Les Cargill wrote:> I'm not sure what it's called - the "power of two method?"Well, I don't hardly use such fancy expressions; only N+M-1 is the minimum. You can't go wrong with that. I guess that my N (the number of samples in a sequence) is your n+1, etc. Then, if you must have length a power of 2, just pick it to be greater than the minimum. Of course, that's what your expressions say. Fred
Reply by ●April 1, 20122012-04-01
On 3/31/2012 11:05 PM, robert bristow-johnson wrote:> get linear convolution out of a circular convolving mechanism (which is > what you get with an FFT)? the only methods i know of are overlap-add > (OLA) or overlap-save (OLS).Only if you're streaming. Otherwise just make the arrays large enough with zero padding. Looks like that's what Les did. Fred
Reply by ●April 1, 20122012-04-01
Fred Marshall wrote:> On 4/1/2012 8:57 AM, Les Cargill wrote: >> I'm not sure what it's called - the "power of two method?" > > Well, I don't hardly use such fancy expressions; only N+M-1 is the > minimum.Correct me if I am wrong, but I believe that both FFT-objects must be of the same order...> You can't go wrong with that.I'll try N+M+1 and see if it works.> I guess that my N (the number of samples in a sequence) is your n+1, etc. > Then, if you must have length a power of 2, just pick it to be greater > than the minimum. > Of course, that's what your expressions say. > > Fred-- Les Cargill
Reply by ●April 1, 20122012-04-01
Les Cargill wrote:> Fred Marshall wrote: >> On 4/1/2012 8:57 AM, Les Cargill wrote: >>> I'm not sure what it's called - the "power of two method?" >> >> Well, I don't hardly use such fancy expressions; only N+M-1 is the >> minimum. > > Correct me if I am wrong, but I believe that both FFT-objects > must be of the same order... > >> You can't go wrong with that. > > I'll try N+M+1 and see if it works. >It works, but as various people have said on them there Innerwebs, a power-of-2 size is considerably ( 3xish in my test case ) faster.>> I guess that my N (the number of samples in a sequence) is your n+1, etc. >> Then, if you must have length a power of 2, just pick it to be greater >> than the minimum. >> Of course, that's what your expressions say. >> >> Fred > > -- > Les Cargill-- Les Cargill
Reply by ●April 2, 20122012-04-02
On 4/1/2012 5:18 PM, Les Cargill wrote:> Les Cargill wrote: >> Fred Marshall wrote: >>> On 4/1/2012 8:57 AM, Les Cargill wrote: >>>> I'm not sure what it's called - the "power of two method?" >>> >>> Well, I don't hardly use such fancy expressions; only N+M-1 is the >>> minimum. >> >> Correct me if I am wrong, but I believe that both FFT-objects >> must be of the same order... >> >>> You can't go wrong with that. >> >> I'll try N+M+1 and see if it works. >> > > It works, but as various people have said on them there Innerwebs, a > power-of-2 size is considerably ( 3xish in my test case ) faster. > >>> I guess that my N (the number of samples in a sequence) is your n+1, >>> etc. >>> Then, if you must have length a power of 2, just pick it to be greater >>> than the minimum. >>> Of course, that's what your expressions say. >>> >>> Fred >> >> -- >> Les Cargill > > -- > Les CargillI don/t know about the 3xish faster in the modern world. It used to be that n^2 was important. I think the world has somewhat passed this by for two reasons: 1) the algorithms improved since. 2) the relative speed improved since. (i.e. saving time is not the issue it once was on a relative basis). Fred
Reply by ●April 3, 20122012-04-03
Fred Marshall wrote:> On 4/1/2012 5:18 PM, Les Cargill wrote: >> Les Cargill wrote: >>> Fred Marshall wrote: >>>> On 4/1/2012 8:57 AM, Les Cargill wrote: >>>>> I'm not sure what it's called - the "power of two method?" >>>> >>>> Well, I don't hardly use such fancy expressions; only N+M-1 is the >>>> minimum. >>> >>> Correct me if I am wrong, but I believe that both FFT-objects >>> must be of the same order... >>> >>>> You can't go wrong with that. >>> >>> I'll try N+M+1 and see if it works. >>> >> >> It works, but as various people have said on them there Innerwebs, a >> power-of-2 size is considerably ( 3xish in my test case ) faster. >> >>>> I guess that my N (the number of samples in a sequence) is your n+1, >>>> etc. >>>> Then, if you must have length a power of 2, just pick it to be greater >>>> than the minimum. >>>> Of course, that's what your expressions say. >>>> >>>> Fred >>> >>> -- >>> Les Cargill >> >> -- >> Les Cargill > > I don/t know about the 3xish faster in the modern world.it turns out to be true with FFTW. It's a change of one line - either do all the ceil() stuff to produce the order of the two FFT, or use (N+M+1). So it's not likely that a sidestream error occurred - I'd bet on the one liner. The FFT are implemented as C++ classes layered over FFTW calls, with a parameter to override the order of the FFT. I love this note from the FFTW website: "Our code generator also produces new algorithms that we do not yet completely understand" http://www.nanophys.kth.se/nanophys/fftw-info/fftw_1.html> It used to be that n^2 was important. > I think the world has somewhat passed this by for two reasons: > 1) the algorithms improved since. > 2) the relative speed improved since. (i.e. saving time is not the issue > it once was on a relative basis). >Absolutely.> Fred-- Les Cargill
Reply by ●April 3, 20122012-04-03
