Prev: orthogonal and correlation
Next: Compensating for reverbation FIR gain
From: Jason on 24 Jun 2010 10:41
On Jun 24, 10:02 am, Les Cargill <lcargil...(a)yahoo.com> wrote:
> Rune Allnor wrote:
> > On 30 Mai, 18:20, Les Cargill<lcargil...(a)yahoo.com> wrote:
> >> Seems dumb*, but what the hey:
> >> (data sets are 1D PCM audio data)
>
> >> Convolution is O(n*m) where n is the length of one vector to be
> >> convolved, m is the length of the other vector. Convolution
> >> using FFT is alleged to be O(n log(n))...
>
> >> *part of this is things I can't easily find in the FFTW docs.
>
> >> 1) The product of a DFT from FFTW is of the same length as the
> >> original PCM stream to which the DFT was applied.
>
> >> 2) "Multiplying" two DFT of length n and m seems to take exactly
> >> the same amount of compute power ( O(n*m) ) as calculating the
> >> convolution by definition.
>
> >> What am I missing?
>
> > You have made a wromg turn somewhere.
>
> > Assume you want to convolve one M-length sequence with a
> > N-length sequence. Then:
>
> > - The direct implementation of convolution is O(M*N)
> > - The FFTs will be O(KlogK) where K = M+N
> > - The frequency-domain multiply will be O(M+N)
>
> > Rune
>
> What sort of transform is this "frequency domain multiply"?
> It's not a dot product; it's not a cross product. It's
> not a pointwise multiply*. What is it?
>
> *I mean when I take small 2 to 4 sample vectors, convolve
> them by the definition ( the O(N+M) multiply of the original
> sample data ) and then take the DFT of the signal & kernel,
> and of the convolution result, it does not turn out to match
> what a pointwise multiply would produce
>
> Maybe I'm doing it wrong, or I'm not recognizing the
> result properly.
>
> --
> Les Cargill
>
> --
> Les Cargill

You do want a pointwise complex multiply. Your confusion comes from a
subtlety of the DFT convolution property: multiplication in the
frequency domain is equivalent to *circular* convolution in the time
domain. This is not the same as what is typically just termed
convolution, which is linear convolution. There are techniques to
implement linear convolution using FFTs (overlap-save, overlap-add),
but if you just do what you noted above, then you will get a vector
representing the circular convolution of the two input vectors.

Jason
From: Les Cargill on 24 Jun 2010 12:15
Jason wrote:
> On Jun 24, 10:02 am, Les Cargill<lcargil...(a)yahoo.com> wrote:
>> Rune Allnor wrote:
>>> On 30 Mai, 18:20, Les Cargill<lcargil...(a)yahoo.com> wrote:
>>>> Seems dumb*, but what the hey:
>>>> (data sets are 1D PCM audio data)
>>
>>>> Convolution is O(n*m) where n is the length of one vector to be
>>>> convolved, m is the length of the other vector. Convolution
>>>> using FFT is alleged to be O(n log(n))...
>>
>>>> *part of this is things I can't easily find in the FFTW docs.
>>
>>>> 1) The product of a DFT from FFTW is of the same length as the
>>>> original PCM stream to which the DFT was applied.
>>
>>>> 2) "Multiplying" two DFT of length n and m seems to take exactly
>>>> the same amount of compute power ( O(n*m) ) as calculating the
>>>> convolution by definition.
>>
>>>> What am I missing?
>>
>>> You have made a wromg turn somewhere.
>>
>>> Assume you want to convolve one M-length sequence with a
>>> N-length sequence. Then:
>>
>>> - The direct implementation of convolution is O(M*N)
>>> - The FFTs will be O(KlogK) where K = M+N
>>> - The frequency-domain multiply will be O(M+N)
>>
>>> Rune
>>
>> What sort of transform is this "frequency domain multiply"?
>> It's not a dot product; it's not a cross product. It's
>> not a pointwise multiply*. What is it?
>>
>> *I mean when I take small 2 to 4 sample vectors, convolve
>> them by the definition ( the O(N+M) multiply of the original
>> sample data ) and then take the DFT of the signal& kernel,
>> and of the convolution result, it does not turn out to match
>> what a pointwise multiply would produce
>>
>> Maybe I'm doing it wrong, or I'm not recognizing the
>> result properly.
>>
>> --
>> Les Cargill
>>
>> --
>> Les Cargill
>
> You do want a pointwise complex multiply. Your confusion comes from a
> subtlety of the DFT convolution property: multiplication in the
> frequency domain is equivalent to *circular* convolution in the time
> domain. This is not the same as what is typically just termed
> convolution, which is linear convolution. There are techniques to
> implement linear convolution using FFTs (overlap-save, overlap-add),
> but if you just do what you noted above, then you will get a vector
> representing the circular convolution of the two input vectors.
>
> Jason

Thanks, Jason - for some reason, I thought the overlap-add
method as Dale pointed me to was for the "by definition"
convolution, not for the multiplication of DFTs.

--
Les Cargill
From: dbd on 24 Jun 2010 19:02
On Jun 24, 9:15 am, Les Cargill <lcargil...(a)yahoo.com> wrote:
....
> Thanks, Jason - for some reason, I thought the overlap-add
> method as Dale pointed me to was for the "by definition"
> convolution, not for the multiplication of DFTs.
>
> --
> Les Cargill

The overlap-add method is used to perform linear convolutions by
people who understand that the required dft size must be at least N +
M -1 to give a linear convolution of an N length with an M length
vector. Zero fill is used to convert the N and M length vectors to the
required size before the forward dft's.

Dale B. Dalrymple
From: Les Cargill on 25 Jun 2010 10:25
dbd wrote:
> On Jun 24, 9:15 am, Les Cargill<lcargil...(a)yahoo.com> wrote:
> ...
>> Thanks, Jason - for some reason, I thought the overlap-add
>> method as Dale pointed me to was for the "by definition"
>> convolution, not for the multiplication of DFTs.
>>
>> --
>> Les Cargill
>
> The overlap-add method is used to perform linear convolutions by
> people who understand that the required dft size must be at least N +
> M -1 to give a linear convolution of an N length with an M length
> vector.

I'm reasonably sure I got that part....

> Zero fill is used to convert the N and M length vectors to the
> required size before the forward dft's.
>

Right.

> Dale B. Dalrymple

--
Les Cargill
First  |  Prev  | 
Pages: 1 2
Prev: orthogonal and correlation
Next: Compensating for reverbation FIR gain