Reply by Les Cargill June 25, 20102010-06-25
dbd wrote:
> On Jun 24, 9:15 am, Les Cargill<lcargil...@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
Reply by dbd June 24, 20102010-06-24
On Jun 24, 9:15&#2013266080;am, Les Cargill <lcargil...@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
Reply by Les Cargill June 24, 20102010-06-24
Jason wrote:
> On Jun 24, 10:02 am, Les Cargill<lcargil...@yahoo.com> wrote: >> Rune Allnor wrote: >>> On 30 Mai, 18:20, Les Cargill<lcargil...@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
Reply by Jason June 24, 20102010-06-24
On Jun 24, 10:02 am, Les Cargill <lcargil...@yahoo.com> wrote:
> Rune Allnor wrote: > > On 30 Mai, 18:20, Les Cargill<lcargil...@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
Reply by Les Cargill June 24, 20102010-06-24
Rune Allnor wrote:
> On 30 Mai, 18:20, Les Cargill<lcargil...@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
Reply by Les Cargill May 30, 20102010-05-30
dbd wrote:
> On May 30, 9:20 am, Les Cargill<lcargil...@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? >> >> -- >> Les Cargill > > Take a look at the example in > > The Scientist and Engineer's Guide to Digital Signal Processing > By Steven W. Smith, Ph.D. > > at > > http://www.dspguide.com/ch18/1.htm > > Dale B. Dalrymple
Beautiful! Thanks much. -- Les Cargill
Reply by Rune Allnor May 30, 20102010-05-30
On 30 Mai, 18:20, Les Cargill <lcargil...@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
Reply by dbd May 30, 20102010-05-30
On May 30, 9:20&#2013266080;am, Les Cargill <lcargil...@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? > > -- > Les Cargill
Take a look at the example in The Scientist and Engineer's Guide to Digital Signal Processing By Steven W. Smith, Ph.D. at http://www.dspguide.com/ch18/1.htm Dale B. Dalrymple
Reply by Les Cargill May 30, 20102010-05-30
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?

--
Les Cargill