Convolution and FFTW question.
in [DSP]
|
From: Les Cargill on 30 May 2010 12:20 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
From: dbd on 30 May 2010 13:25 On May 30, 9:20 am, 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? > > -- > 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
From: Rune Allnor on 30 May 2010 13:37 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
From: Les Cargill on 30 May 2010 13:55 dbd wrote: > On May 30, 9:20 am, 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? >> >> -- >> 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
From: Les Cargill on 24 Jun 2010 10:02 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
|
Next
|
Last
Pages: 1 2 Prev: orthogonal and correlation Next: Compensating for reverbation FIR gain |