0
$\begingroup$

Let x[n] and y[n] be defined for n=0,1, ..., N-1.

This (for example with Python's scipy fft / ifft)

a = ifft (fft(x) * fft(y))

should give the convolution

$$a[k] = (x * y)[k] = \sum_{n=0}^{N-1} x[n] y[k-n]$$

But is it done with

  • y[i] = 0 if $i<0$ ?

or

  • y[i] = y[N+i] if $i<0$ ? (ex : y[-3] = y[N-3] ) (in this case do we call it circular convolution?)

Note : More generally, I have good books about signal processing / Fourier transform in general, but they are not really handy handbooks for discrete finite signals (x[n] for n=0,1, ..., N-1). Do you have a good reference of handbook for this case (discrete finite signals) ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Fast (FFT/IFFT) convolution results in circular convolution.

(But if sufficient zero-padding is explicitly added before the initial FFTs, circular and linear convolution would then produce identical results.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ thanks. Is there an amount of zero-padding for which we are sure the results are identical ? $\endgroup$
    – Basj
    Commented Nov 26, 2013 at 16:21
  • 2
    $\begingroup$ The length of both signals after zero padding has to be length(x) + length(y) - 1 $\endgroup$
    – Deve
    Commented Nov 26, 2013 at 16:31
  • 1
    $\begingroup$ Has to be at least that length, however one can zero pad to a greater length for a faster FFT (better factorable length). $\endgroup$
    – hotpaw2
    Commented Nov 26, 2013 at 16:35
  • $\begingroup$ @hotpaw2: and in python that faster length is the nearest 5-smooth number: github.com/scipy/scipy/issues/2146 stackoverflow.com/a/19649737/125507 $\endgroup$
    – endolith
    Commented Nov 27, 2013 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.