Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

why we want use DFT to calculate linear convolution?

Status
Not open for further replies.
N

neoflash

Advanced Member level 1
Joined
Jul 2, 2005
Messages
492
Helped
10
Reputation
20
Reaction score
2
Trophy points
1,298
Activity points
4,759
I read from text book that if we pad the series long enough, we can use DFT to calculate the linear convolve between two series.

My question is what's the motivation of doing that?

Another question is that whether padding is going to incur distortion is discrete fourier series domain, albeit not in time domain?

thanks.
 

Hi neoflash,

performing convolution using FFT (so-called fast convolution) is faster than direct convolution.
If you have two sequencies of length N, the complexity of direct convolution is of the order of N^2.
With fast convolution, you have to perform two FFT's (direct and inverse), that have complexity of the order of N*log2(N), plus spectra multiplication, with complexity N. In total, there are only roughly N+2*N*log2(N) operations instead of roughly N^2.
What is calculated in that way is circular convolution. Zero padding is needed in order that it matches ordinary sequence convolution.
Regards

Z
 

    N

    neoflash

    Points: 2
    Helpful Answer Positive Rating
zorro said:
Hi neoflash,

performing convolution using FFT (so-called fast convolution) is faster than direct convolution.
If you have two sequencies of length N, the complexity of direct convolution is of the order of N^2.
With fast convolution, you have to perform two FFT's (direct and inverse), that have complexity of the order of N*log2(N), plus spectra multiplication, with complexity N. In total, there are only roughly N+2*N*log2(N) operations instead of roughly N^2.
What is calculated in that way is circular convolution. Zero padding is needed in order that it matches ordinary sequence convolution.
Regards

Z
Click to expand...
Good explanation. We should emphasize again that the wise-product of two DFT relates to the circular convolution of the two corresponding time-domain sequences. Zero-oadding is thus required.
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top