DFT for somthing similar to convolution

[menahemkrief]

Hi,

I have the following problem:
Let x,y be finite real valued sequences defined on 0...N-1 and let g be a non negative integer .


define

also on 0..N-1.


In addition, the DFT of y is known in closed form.
Is there a way to write z as some cyclic convolution, so that with the help of the convolution theorem z can be calculated in NLOG N istead of N^2?


I tried following the convolution therem proff but i get stuck:

The problem is that the second sum depends on k so the double sum doesn't factor to the product of DFTs.


what am I missing?


thank you

 

[collinsmark]

Hello menahemkrief,

Welcome to Physics Forums!

Just to be clear, are you trying to mimic linear convolution by using cyclic convolution (which would allow you to use FFT/IFFT algorithms)?

If so, the number of non-zero elements in $z_n$ is $2N-1$. So you won't be able to accomplish this by taking the DFTs of $x_n$ and $y_n$ directly (then multiplying them together).

But you can accomplish your goal by first zero-padding $x_n$ and $y_n$ with an additional $N - 1$ samples, minimum.

Or, are you rather trying to perform cyclic convolution from the get-go? In that case, there's no need for zero-padding. But there will be a lot of overlap in the convolution -- the convolution will not be linear convolution.

 

[collinsmark]

Or, if your $y_n$ represents a (large) stream of samples, and $x_n$ represents the impulse response of a FIR filter, you might be interested in the "overlap and add" and/or "overlap and save" methods of convolution, which implement DFTs. These methods can significantly decrease the computational requirements of the filtering. But they are limited to FIR filters (as opposed to IIR filters), because the impulse response needs to be of finite length, and then zero-padded.

 

[menahemkrief]

Hi,
Thank you for your answer.

What I really want is to perform the above operation in the frequency domain.
I need to perform this operation many times (a few tens of millions, while the signals are short N<40) so if its simpler in the frequency domain I rather do it there many times and transform back at the end.

Now the thing is that this operation is not exactly a linear convolution. z MUST be of length N (and not 2N-1 as is the linear convolution) or it can be zero padded for some larger length then N.

If I zero pad x,y to length 2N-1, transform,multiply and take the IFFT the result coincide with z only for n<N but for N≤n≤2N-1 the IFFT is not zero but z must be zero.
I can't just ignore the values of the IFFT for N≤n≤2N-1 because I want to stay in frequency domain.
What i can do is to perform a convolution with a sinc in the frequency domain (that is multiplication with a window that eliminates the value of the IFFT for N≤n≤2N-1) but this is again time consuming.

Is there a way to perform the calculation of z in the frequency domain only (so that z in the time domain will have only its first N elements non zero)?

thank you!

 

[collinsmark]

Hi,
Thank you for your answer.

What I really want is to perform the above operation in the frequency domain.
I need to perform this operation many times (a few tens of millions, while the signals are short N<40) so if its simpler in the frequency domain I rather do it there many times and transform back at the end.

Yes, multiplication in the frequency domain is the same thing as convolution in the time domain.

But if you want to mimic linear convolution of two waveforms of equal size, by using FFTs, you'll have to zero-pad your time domain waveforms.

Consider the function

****
****

convolved with

****
****

where the x-axis is the time domain, and the y-axis is the signal's amplitude.

To convolve them, we take one of them and flip it about the y-axis, then shift it up through the other, multiplying each step of the way. The result is

   *
  ***
 *****
*******

Note that even though there were only 4 non-zero samples in the original, the result spans 7 non-zero samples. 7 is 2(4) - 1, or 2N-1.

You can do this using DFTs (with FFT algorithms) by first zero-padding the inputs such that they contain 7 or more samples (logically, you would want to pad them to 8 samples in this case, since 8 is the next power of 2 greater than 7).

The DFT has the implicit assumption that the time domain waveforms are periodic. So by zero-padding the time domain waveforms we convolve

    ****    ****    ****    ****    ****    ****    ****    ****
... ****    ****    ****    ****    ****    ****    ****    **** ...

with

    ****    ****    ****    ****    ****    ****    ****    ****
... ****    ****    ****    ****    ****    ****    ****    **** ...

resulting in

   *       *       *       *       *       *       *       *
  ***     ***     ***     ***     ***     ***     ***     ***
 *****   *****   *****   *****   *****   *****   *****   *****
******* ******* ******* ******* ******* ******* ******* *******

This is done just by taking the FFT of both waveforms, multiplying them together, then taking the IFFT.

Of which, one period of that represents the linear convolution. Note that we couldn't have done that without the zero padding, due to the effects of overlap.

Now the thing is that this operation is not exactly a linear convolution. z MUST be of length N (and not 2N-1 as is the linear convolution) or it can be zero padded for some larger length then N.

If I zero pad x,y to length 2N-1, transform,multiply and take the IFFT the result coincide with z only for n<N but for N≤n≤2N-1 the IFFT is not zero but z must be zero.
I can't just ignore the values of the IFFT for N≤n≤2N-1 because I want to stay in frequency domain.
What i can do is to perform a convolution with a sinc in the frequency domain (that is multiplication with a window that eliminates the value of the IFFT for N≤n≤2N-1) but this is again time consuming.

Is there a way to perform the calculation of z in the frequency domain only (so that z in the time domain will have only its first N elements non zero)?

thank you!

I'm not quite following what type of convolution you need to perform. But if you are trying to convolve a relatively short waveform with a relatively long waveform, there are methods called "overlap and save" and "overlap and add" which you may find useful.

http://en.wikipedia.org/wiki/Overlap%E2%80%93save_method

http://en.wikipedia.org/wiki/Overlap%E2%80%93add_method

The general idea for these methods is that you zero pad the smaller waveform to be equal in size to the larger waveform, then do the FFT, multiply, IFFT, but then you throw away the first N-1 samples of the output, where N corresponds to the original length of the smaller waveform.

Even though you are throwing samples away periodically, it's still more efficient than straight-forward convolution.

If the longer waveform is very long, it can be broken up into smaller chunks (still significantly larger than the original, smaller waveform however), and the result pieced back together after the operation.

[Edit: I prefer the overlap-and-save method to the overlap-and-add method, by the way.]

 

[AlephZero]

What CollinsMark said, but it may be easier to see what is going on if you think about it a slightly different way.

If you reverse the order of your y data, the convolution becomes a linear digital filter that converts the x's into the z's. The y's represent the (finite) impulse response of this filter.

So, what you need to do is implement this filter in the frequency domain:
1. Pad the y's with zeros
2. FFT the x's and y's
3. Do the filtering (multiply the FFT coefficients)
4. Do the inverse FFT to get the z's.

 

[menahemkrief]

Hi,

thanks for your answers.

My problem is that I want to perform this convolution many times, so how should i do it only in the frequency domain? zero paddin in the freq domain is not trivial (convolution with a sinc).

The full problem is described in the attached pdf.

thank you