FFT cyclicity with and without zero-padding

An FFT evaluates a discrete Fourier transform and therefore assumes periodic data. As a result, multiplication of two spectra followed by an inverse FFT produces circular convolution. This example places a signal close to the right boundary so that the wrapped part is easy to see.


import matplotlib.pyplot as plt
import numpy as np

A finite signal and an impulse response

The signal occupies samples near the end of a window of length $N=64$ . The one-sided decaying kernel spreads it further to the right, beyond the window boundary.


n_signal = 64
n_kernel = 17
 
signal = np.zeros(n_signal)
signal[50:56] = 1.0
 
kernel = np.exp(-np.arange(n_kernel) / 4.0)
kernel /= kernel.sum()
 
fig, axes = plt.subplots(1, 2, figsize=(11, 3))
axes[0].stem(np.arange(n_signal), signal, basefmt=" ")
axes[0].set(title="Input signal", xlabel="sample n", ylabel="amplitude")
axes[1].stem(np.arange(n_kernel), kernel, basefmt=" ")
axes[1].set(title="Impulse response", xlabel="sample n")
fig.tight_layout()

No padding: the tail wraps around

The direct convolution is linear and has length $N+K-1$ . An $N$ -point FFT has room for only $N$ samples, so the missing tail is folded back modulo $N$ and added at the beginning.


linear = np.convolve(signal, kernel, mode="full")
 
circular = np.fft.ifft(
    np.fft.fft(signal, n=n_signal) * np.fft.fft(kernel, n=n_signal)
).real
 
# Fold the tail of the linear convolution back into its first N samples.
folded_linear = linear[:n_signal].copy()
folded_linear[: n_kernel - 1] += linear[n_signal:]
 
assert np.allclose(circular, folded_linear, atol=1e-12)
 
fig, axes = plt.subplots(2, 1, figsize=(11, 6), sharex=True)
axes[0].plot(linear[:n_signal], label="linear convolution: first N samples", lw=2)
axes[0].plot(circular, "--", label="N-point FFT: circular convolution", lw=2)
axes[0].axvspan(0, n_kernel - 2, color="tab:red", alpha=0.12, label="wrapped tail")
axes[0].set_ylabel("amplitude")
axes[0].legend()
 
axes[1].plot(circular - linear[:n_signal], color="tab:red")
axes[1].axhline(0.0, color="black", lw=0.8)
axes[1].set(xlabel="sample n", ylabel="circular - linear")
fig.suptitle("Without padding, the response crosses the periodic boundary")
fig.tight_layout()

With zero-padding: FFT convolution becomes linear

For arrays of lengths $N$ and $K$ , a transform length of at least $N+K-1$ keeps all samples separate. The next power of two is convenient for many FFT implementations, although it is not mathematically required.


min_fft_size = n_signal + n_kernel - 1
fft_size = 1 << (min_fft_size - 1).bit_length()
 
with_padding = np.fft.ifft(
    np.fft.fft(signal, n=fft_size) * np.fft.fft(kernel, n=fft_size)
).real[:min_fft_size]
 
assert np.allclose(with_padding, linear, atol=1e-12)
 
fig, axes = plt.subplots(2, 1, figsize=(11, 6), sharex=True)
axes[0].plot(linear, label="direct linear convolution", lw=3, alpha=0.65)
axes[0].plot(with_padding, "--", label=f"FFT with zero-padding to {fft_size}", lw=2)
axes[0].axvline(n_signal - 1, color="black", ls=":", label="original boundary")
axes[0].set_ylabel("amplitude")
axes[0].legend()
 
axes[1].plot(with_padding - linear, color="tab:green")
axes[1].axhline(0.0, color="black", lw=0.8)
axes[1].set(xlabel="sample n", ylabel="FFT - direct")
fig.suptitle("With sufficient padding, no samples wrap around")
fig.tight_layout()
 
print(f"Original length: {n_signal}")
print(f"Linear-convolution length: {min_fft_size}")
print(f"Padded FFT length: {fft_size}")
print(f"Maximum error after padding: {np.max(np.abs(with_padding - linear)):.3e}")

The same mechanism acts independently along both axes of a sampled optical field. In an FFT-based angular spectrum calculation, insufficient empty space makes radiation that leaves one edge reappear at the opposite edge. SVETlANNa’s zpASM enlarges the computational window with zeros before propagation and then crops it back, reducing this periodic wrap-around.