CODEWITHSUNDEEP
fft
Samuel
Samuel

Reputation: 6247

How to compute the convolution of two unequal length vectors

I know the convolution can computed with FFT.
F*H = IDFT[DFT(F)DFT(H)]. * means convolution.

what if the length of F and H is unequal. then the length of DFT(H) and DFT(F) is unequal. so how to compute the element-wise multiply between two unequal length vectors. Did I forget something?

Upvotes: 4

Views: 4138

Answers (1)

hotpaw2
hotpaw2

Reputation: 70743

To do a linear fast convolution of two vectors of length H and F, one normally zero-pads both to the same length, a length of at least H+F-1 or longer, possibly to the next greater length that is the product of very small prime factors (such as 2^n).

Any shorter length than H+F-1 results in a circular convolution, which may or may not be what you want.

Upvotes: 2

Related Questions