# Thread: DFT for convolution like operation

1. ## DFT for convolution like operation

Hi,

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

2. ## Re: DFT for convolution like operation

let $X_k, Y_k$ be the DFT's of $x_n, y_n$ respectively.

let $z_n=f_n \odot g_n = \displaystyle{\sum_{m=0}^{N-1}} f_{n-m} g_n$

then $Z_k = DFT\{z_n\} = X_k Y_k$

and of course $z_n = IDFT\{Z_k\}$

use the FFT to take your DFT's and IDFT and I think this is what you are after.

3. ## Re: DFT for convolution like operation

Hi,

The problem is that z is not the convolution of x and y. the sum in the definition in zn is from zero to n and not from zero to N-1.

4. ## Re: DFT for convolution like operation

Originally Posted by menahemkrief
Hi,

The problem is that z is not the convolution of x and y. the sum in the definition in zn is from zero to n and not from zero to N-1.
that's an odd summation. Is it to $n$ or to $N$ ?

$z_0$ has zero terms in it's sum. Are you sure this is the expression you want?

5. ## Re: DFT for convolution like operation

Hi,
Yes, this is exactly the issue.
The sum of zn is from zero to n not N-1 and therefore its not a convolution. I tried to overcome it by using step function but I got stuck (see my first message).

z0 has one term to sum - z0=x0*y0.

Thank you

6. ## Re: DFT for convolution like operation

Originally Posted by menahemkrief
Hi,
Yes, this is exactly the issue.
The sum of zn is from zero to n not N-1 and therefore its not a convolution. I tried to overcome it by using step function but I got stuck (see my first message).

z0 has one term to sum - z0=x0*y0.

Thank you
what you want to do I think, I haven't checked it yet, is to pad both x and y with N zeros.

Then the first N-1 terms of a 2N cyclic correlation of these padded sequences should be what you are after.

This should be able to be done using the FFT. I'll look into it more tomorrow.

7. ## Re: DFT for convolution like operation

Originally Posted by romsek
what you want to do I think, I haven't checked it yet, is to pad both x and y with N zeros.

Then the first N-1 terms of a 2N cyclic correlation of these padded sequences should be what you are after.

This should be able to be done using the FFT. I'll look into it more tomorrow.
yeah, this does it.

8. ## Re: DFT for convolution like operation

Hi,

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!

9. ## Re: DFT for convolution like operation

Originally Posted by menahemkrief
Hi,

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!
I did do it in the frequency domain. Do you understand Mathematica code? Take another look at the attached sheet a couple posts back.

10. ## Re: DFT for convolution like operation

Hi.

The vector zz is different from the vector z.
zz is of length 2N and z is of length N.
The first N values of zz equals to those of z.

The problem is, that, say, I want to perform the above operation twice. I cant multiply twice in the frequency domain, because fzz is not the DFT of z!

I want to perform the operation many many times, in the frequency domain without going back to the time domain and truncating every time i perform the operation.

11. ## Re: DFT for convolution like operation

Originally Posted by menahemkrief
Hi.

The vector zz is different from the vector z.
zz is of length 2N and z is of length N.
The first N values of zz equals to those of z.

The problem is, that, say, I want to perform the above operation twice. I cant multiply twice in the frequency domain, because fzz is not the DFT of z!

I want to perform the operation many many times, in the frequency domain without going back to the time domain and truncating every time i perform the operation.

12. ## Re: DFT for convolution like operation

let

be M sequences of length N (for each i in {0,...,M-1} there is a different sequence defined on {0,...,N-1}).
all the g's are smaller then N.

Now an operation F on any two sequences a,b on 0,..,N-1 , is defined to give a new sequence F(a,b) according to:

Now define recursively the following M sequences all of defined on{0,...,N-1}:

I need an efficient way for calculating the last sequence x(M-1).

If F was exactly the convolution of its two operands it would be easy - The FFT of x0 and all the y's are known analitically so i can multiply all of these FFT's in the frequency domain and transform back - only one IFFT is required! so this whole recursive calculation can be done in NlogN.

so is there a way to do this recursive operation entirely in the frequency domain?

thank you

13. ## Re: DFT for convolution like operation

Originally Posted by menahemkrief
let

be M sequences of length N (for each i in {0,...,M-1} there is a different sequence defined on {0,...,N-1}).
all the g's are smaller then N.

Now an operation F on any two sequences a,b on 0,..,N-1 , is defined to give a new sequence F(a,b) according to:

Now define recursively the following M sequences all of defined on{0,...,N-1}:

I need an efficient way for calculating the last sequence x(M-1).

If F was exactly the convolution of its two operands it would be easy - The FFT of x0 and all the y's are known analitically so i can multiply all of these FFT's in the frequency domain and transform back - only one IFFT is required! so this whole recursive calculation can be done in NlogN.

so is there a way to do this recursive operation entirely in the frequency domain?

thank you
any way you could post this a bit larger. I can't read some of the finer print.

If you are in the frequency domain after having multiplied the DFTs of the 2 padded sequences you would then

a) IDFT the resulting length 2N sequence to obtain a length 2N sequence in the time domain corresponding to a full 2N convolution. You only want the first half of this so

b) take the first N elements of this 2N sequence to obtain the next "x" sequence you are going to convolve.

Now. What's that look like in the frequency domain. You're essentially multiplying the full 2N convolution with a rectangular time window that's half the sequence length wide.

In the frequency domain this corresponds to convolving the length 2N frequency response with the DFT of the rectangular window, i.e. a phase shifted sinc function. If you're going to have to do this you might as well take it back to the time domain, truncate it, re-pad it, and bring it back to the frequency domain.

Maybe I can find something trickier once I can fully read the problem.

14. ## Re: DFT for convolution like operation

Hi,
sorry for the small pictures.

Attached a pdf describing the problem.

Thank you!