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) ?

$\endgroup$
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.)

$\endgroup$
4
  • $\begingroup$ thanks. Is there an amount of zero-padding for which we are sure the results are identical ? $\endgroup$
    – Basj
    Nov 26 '13 at 16:21
  • 2
    $\begingroup$ The length of both signals after zero padding has to be length(x) + length(y) - 1 $\endgroup$
    – Deve
    Nov 26 '13 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
    Nov 26 '13 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
    Nov 27 '13 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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