Continue to Site

DFT for somthing similar to convolution

Status
Not open for further replies.

menahemkrief

Newbie level 1
Newbie level 1
Joined
Apr 3, 2014
Messages
1
Helped
0
Reputation
0
Reaction score
0
Trophy points
1
Activity points
9
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
35akubq.jpg

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:
10421hy.jpg



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
 

Hi there,
I am not sure about the notations used in the above mentioned proof. If you want to use DFT to find linear convolution of x and y, then take the DFT for x and y of 2N-1 samples (by zero padding). This will give a 2N-1 size DFT of z which can be used to find the sequence z.
Hope this helps.
MHanif
 

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top