# What kind of discrete convolution is this?

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

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

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