Why is the output length N + M - 1 and not N + M?

The first non-zero output sample is y[0] = x[0]·h[0] and the last is y[N+M-2] = x[N-1]·h[M-1]. That is N + M - 1 samples total (indices 0 through N+M-2). The "-1" comes from the fact that both sequences share one overlapping end point.

What is the difference between linear and circular convolution?

Linear convolution produces N + M - 1 output samples and has no wrap-around. Circular convolution of period L produces exactly L samples by wrapping (aliasing) the linear result. To make circular convolution equivalent to linear convolution, zero-pad both sequences to at least N + M - 1 points before taking the DFT.

Why does autocorrelation give 2N - 1 points?

Autocorrelation is the cross-correlation of a sequence with itself, so both sequences have length N, giving N + N - 1 = 2N - 1. The result is symmetric around lag 0, which sits at index N - 1 of the output array.

What is the minimum FFT size shown by this tool?

It is the smallest power of 2 that is greater than or equal to the output length (N + M - 1). Using this size for zero-padded FFTs allows you to recover the full linear convolution from a single DFT pair multiply and inverse DFT, which is the basis of overlap-add processing.

Does this apply to 2D convolution (images)?

Yes, the same rule applies along each dimension independently. A 2D kernel of size R×C convolved with an image of size H×W produces an output of (H + R - 1) × (W + C - 1) when using full linear convolution.

Convolution Length Calculator

Name: Convolution Length Calculator
Availability: InStock
Author: Nham Vu

Enter the lengths of two sequences and get the exact output length for linear convolution, cross-correlation, or autocorrelation.

Sequence Parameters

Operation

Linear Convolution N + M − 1 Cross-Correlation N + M − 1 Autocorrelation 2N − 1

Length N — first sequence

Length M — second sequence

Enter sequence lengths and press Calculate.

Summary

Enter the lengths of two sequences and get the exact output length for linear convolution, cross-correlation, or autocorrelation.

How it works

Enter the length N of the first sequence (signal or filter input).
Enter the length M of the second sequence (filter impulse response or kernel).
Select the operation: linear convolution, cross-correlation, or autocorrelation.
The output length is computed instantly: N + M - 1 for convolution and cross-correlation, 2N - 1 for autocorrelation.
The minimum zero-padded FFT size (next power of 2 at or above the output length) is shown for efficient frequency-domain processing.
The number of appended zeros needed for circular-to-linear equivalence is also displayed.

Use cases

Determine buffer sizes when implementing FIR filters in real-time DSP systems.
Calculate the output frame size for overlap-add or overlap-save convolution.
Verify the expected length of a cross-correlation result in a matched-filter receiver.
Size FFT buffers before writing convolution code to avoid off-by-one allocation errors.
Teach or study the fundamental relationship between sequence lengths and convolution output.
Quickly check whether a convolution output fits within a fixed-size memory block.

Frequently Asked Questions

Last updated: 2026-07-22 · Reviewed by Nham Vu