Forums

overlap in the frequency domain

Started by gary njp March 24, 2007
Hi,

Anyone know a way to overlap successive blocks of FFT data in the
frequency domain as opposed to having to IFFT then overlap in the time
domain, as part of a partioned convolution process im doing:
 
loop x { FFT > Multiply > IFFT } overlap/accumulate > output (and so x
IFFTs)

when ide like to do:

loop x { FFT > Multiply > overlap/accumulate } IFFT > output (just 1
IFFT)

but im not sure how to overlap the FFT data, i did try summing them but
the result wasnt good.

thanks
Gary
gary njp wrote:
> Hi, > > Anyone know a way to overlap successive blocks of FFT data in the > frequency domain as opposed to having to IFFT then overlap in the time > domain, as part of a partioned convolution process im doing: > > loop x { FFT > Multiply > IFFT } overlap/accumulate > output (and so x > IFFTs) > > when ide like to do: > > loop x { FFT > Multiply > overlap/accumulate } IFFT > output (just 1 > IFFT) > > but im not sure how to overlap the FFT data, i did try summing them but > the result wasnt good.
You are filtering. You want as many output samples as you have input samples. How big must the "just one" IFFT be? If you can do an IFFT that big, just do one FFT the same size and be done with it. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
>gary njp wrote: >> Hi, >> >> Anyone know a way to overlap successive blocks of FFT data in the >> frequency domain as opposed to having to IFFT then overlap in the time >> domain, as part of a partioned convolution process im doing: >> >> loop x { FFT > Multiply > IFFT } overlap/accumulate > output (and so x >> IFFTs) >> >> when ide like to do: >> >> loop x { FFT > Multiply > overlap/accumulate } IFFT > output (just 1 >> IFFT) >> >> but im not sure how to overlap the FFT data, i did try summing them
but
>> the result wasnt good. > >You are filtering. You want as many output samples as you have input >samples. How big must the "just one" IFFT be? If you can do an IFFT that
>big, just do one FFT the same size and be done with it. > >Jerry
>You are filtering. You want as many output samples as you have input >samples. How big must the "just one" IFFT be? If you can do an IFFT that
>big, just do one FFT the same size and be done with it. > >Jerry
Hi Jerry im doing realtime partioned convolution, the input is 512 long zero padded to 1024 for the overlap, i loop through multiple 512 blocks of likewise padded IR, ideally the IFFT would be 512 samples long to get the input back, im just wondering if i can overlap/accumulate in the frequency domain rather than the time domain - maybe a naive question?
gary njp wrote:
>> gary njp wrote: >>> Hi, >>> >>> Anyone know a way to overlap successive blocks of FFT data in the >>> frequency domain as opposed to having to IFFT then overlap in the time >>> domain, as part of a partioned convolution process im doing: >>> >>> loop x { FFT > Multiply > IFFT } overlap/accumulate > output (and so x >>> IFFTs) >>> >>> when ide like to do: >>> >>> loop x { FFT > Multiply > overlap/accumulate } IFFT > output (just 1 >>> IFFT) >>> >>> but im not sure how to overlap the FFT data, i did try summing them > but >>> the result wasnt good. >> You are filtering. You want as many output samples as you have input >> samples. How big must the "just one" IFFT be? If you can do an IFFT that > >> big, just do one FFT the same size and be done with it. >> >> Jerry > >> You are filtering. You want as many output samples as you have input >> samples. How big must the "just one" IFFT be? If you can do an IFFT that > >> big, just do one FFT the same size and be done with it. >> >> Jerry > > Hi Jerry > im doing realtime partioned convolution, the input is 512 long zero > padded > to 1024 for the overlap, i loop through multiple 512 blocks of likewise > padded IR, ideally the IFFT would be 512 samples long to get the input > back, im just wondering if i can overlap/accumulate in the frequency > domain rather than the time domain - maybe a naive question?
I don't think you can. What would your "convolution" mean if you started with 20 512-sample-long blocks (each padded to 1024) and ended up with 512 results? A real convolution would have 10239 plus the length of what the blocks were convolved with. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
On 24 Mar, 13:49, "gary njp" <gary...@yahoo.co.jp> wrote:
> Hi, > > Anyone know a way to overlap successive blocks of FFT data in the > frequency domain as opposed to having to IFFT then overlap in the time > domain, as part of a partioned convolution process im doing: > > loop x { FFT > Multiply > IFFT } overlap/accumulate > output (and so x > IFFTs) > > when ide like to do: > > loop x { FFT > Multiply > overlap/accumulate } IFFT > output (just 1 > IFFT) > > but im not sure how to overlap the FFT data, i did try summing them but > the result wasnt good.
When you work with a frame of length N, you get an N length IFFT. When you work with a frame of length N+1, you get an N+1 length IFFT. You keep the same sampling frequency fs. What, then, are the differences between the two? The bin width. In the length N case, the bin width is 1/N*(2*pi*fs). In the length N+1 case, the bin width is 1/(N+1)*(2*pi*fs). So what you need to do, is to somehow interleave the spectrum coefficients from each frame, while preserving casualty, symmetry and all that. I don't know what you hope to achieve by this exercise, but I can assure you you will not save any work or find a simpler way to handle things, by choosing this approach. Rune
On 24 Mrz., 15:50, "gary njp" <gary...@yahoo.co.jp> wrote:
> >gary njp wrote: > >> Hi, > > >> Anyone know a way to overlap successive blocks of FFT data in the > >> frequency domain as opposed to having to IFFT then overlap in the time > >> domain, as part of a partioned convolution process im doing: > > >> loop x { FFT > Multiply > IFFT } overlap/accumulate > output (and so x > >> IFFTs) > > >> when ide like to do: > > >> loop x { FFT > Multiply > overlap/accumulate } IFFT > output (just 1 > >> IFFT) > > >> but im not sure how to overlap the FFT data, i did try summing them > but > >> the result wasnt good. > > >You are filtering. You want as many output samples as you have input > >samples. How big must the "just one" IFFT be? If you can do an IFFT that > >big, just do one FFT the same size and be done with it. > > >Jerry > >You are filtering. You want as many output samples as you have input > >samples. How big must the "just one" IFFT be? If you can do an IFFT that > >big, just do one FFT the same size and be done with it. > > >Jerry > > Hi Jerry > im doing realtime partioned convolution, the input is 512 long zero > padded > to 1024 for the overlap, i loop through multiple 512 blocks of likewise > padded IR, ideally the IFFT would be 512 samples long to get the input > back, im just wondering if i can overlap/accumulate in the frequency > domain rather than the time domain - maybe a naive question?
Gary, the question is not naive. You are looking for the concept of frequency domain delay line (FDL) convolution. You'll find some stuff here: http://pcfarina.eng.unipr.it/Public/AES-113/ especially the Garcia preprint, which explains the FDL concept. Robert, you asked about the MS patent on fast convolution. It is also available from that link, plus some comments of Farina with regards to the validity of that patent. There seems to be quite a mess and number of players regarding patents on this fast convolution stuff. I wonder if this will ever be settled: who first published the idea? Regards, Andor
>Gary, the question is not naive. You are looking for the concept of >frequency domain delay line (FDL) convolution. You'll find some stuff >here: > >http://pcfarina.eng.unipr.it/Public/AES-113/
Thanks for supplying the name to the concept Andor, ill check that out.
>I don't know what you hope to achieve by this exercise, >but I can assure you you will not save any work or >find a simpler way to handle things, by choosing this >approach. >Rune
As i said (perhaps not to clearly) originally, to cut the iffts from possibly hundreds per pass down to one by keeping a running buffer of FFT data, rather than real data, of course if the calculations are heavier in doing so it would be self defeating. Gary
>>Gary, the question is not naive. You are looking for the concept of >>frequency domain delay line (FDL) convolution. You'll find some stuff >>here: >> >>http://pcfarina.eng.unipr.it/Public/AES-113/ > >Thanks for supplying the name to the concept Andor, ill check >that out.
Kulp-PrePrint2694.pdf: "Secondly, instead of saving the final convolution results of each segment, why not Just save the multiplied FFTs? Then, when it comes time to play back a certain segment in time, we would first add together all the multiplied FFTs that correspond to that time segment, and then perform Just one inverse FFT per output segment. This is permissible because of the principles of linearity and superposition." The Kulp paper outlines the concept, but im still unclear how to actually add the FFTs back together, considering overlap in the frequency domain, the Garcia paper goes into more detail as Andor mentioned but the equations are a little beyond my grasp.