>>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.
Reply by gary njp●March 24, 20072007-03-24
>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
Reply by Andor●March 24, 20072007-03-24
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
Reply by Rune Allnor●March 24, 20072007-03-24
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
Reply by Jerry Avins●March 24, 20072007-03-24
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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by gary njp●March 24, 20072007-03-24
>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?
Reply by Jerry Avins●March 24, 20072007-03-24
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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by gary njp●March 24, 20072007-03-24
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