Results 1 to 14 of 14

Math Help - DFT for convolution like operation

  1. #1
    Newbie
    Joined
    Apr 2014
    From
    israel
    Posts
    7

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,648
    Thanks
    1060

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2014
    From
    israel
    Posts
    7

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,648
    Thanks
    1060

    Re: DFT for convolution like operation

    Quote Originally Posted by menahemkrief View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2014
    From
    israel
    Posts
    7

    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,648
    Thanks
    1060

    Re: DFT for convolution like operation

    Quote Originally Posted by menahemkrief View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,648
    Thanks
    1060

    Re: DFT for convolution like operation

    Quote Originally Posted by romsek View Post
    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.

    DFT for convolution like operation-clipboard01.jpg
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Apr 2014
    From
    israel
    Posts
    7

    Re: DFT for convolution like operation

    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!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,648
    Thanks
    1060

    Re: DFT for convolution like operation

    Quote Originally Posted by menahemkrief View Post
    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!
    I did do it in the frequency domain. Do you understand Mathematica code? Take another look at the attached sheet a couple posts back.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Apr 2014
    From
    israel
    Posts
    7

    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,648
    Thanks
    1060

    Re: DFT for convolution like operation

    Quote Originally Posted by menahemkrief View Post
    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.
    please describe the entire problem.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Apr 2014
    From
    israel
    Posts
    7

    Re: DFT for convolution like operation

    let
    DFT for convolution like operation-1.png
    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:
    DFT for convolution like operation-1.png

    Now define recursively the following M sequences all of defined on{0,...,N-1}:
    DFT for convolution like operation-1.png
    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
    Last edited by menahemkrief; April 5th 2014 at 05:15 AM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,648
    Thanks
    1060

    Re: DFT for convolution like operation

    Quote Originally Posted by menahemkrief View Post
    let
    Click image for larger version. 

Name:	1.png 
Views:	3 
Size:	11.0 KB 
ID:	30614
    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:
    Click image for larger version. 

Name:	1.png 
Views:	1 
Size:	5.1 KB 
ID:	30611

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

Name:	1.png 
Views:	1 
Size:	16.2 KB 
ID:	30615
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Apr 2014
    From
    israel
    Posts
    7

    Re: DFT for convolution like operation

    Hi,
    sorry for the small pictures.

    Attached a pdf describing the problem.

    Thank you!
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Convolution: sin(t) * u(t)
    Posted in the Calculus Forum
    Replies: 4
    Last Post: September 26th 2011, 09:25 PM
  2. Convolution
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: June 14th 2011, 05:09 PM
  3. Convolution
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 21st 2011, 02:02 PM
  4. convolution
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: November 25th 2010, 04:38 AM
  5. Convolution
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 18th 2009, 10:07 AM

Search Tags


/mathhelpforum @mathhelpforum