where for outside the region This article uses common abstract notations, such as or in which it is understood that the functions should be thought of in their totality, rather than at specific instants (see Convolution#Notation).
Fig 1: A sequence of five plots depicts one cycle of the overlap-add convolution algorithm. The first plot is a long sequence of data to be processed with a lowpass FIR filter. The 2nd plot is one segment of the data to be processed in piecewise fashion. The 3rd plot is the filtered segment, including the filter rise and fall transients. The 4th plot indicates where the new data will be added with the result of previous segments. The 5th plot is the updated output stream. The FIR filter is a boxcar lowpass with samples, the length of the segments is samples and the overlap is 15 samples.
The concept is to divide the problem into multiple convolutions of with short segments of :
where is an arbitrary segment length. Then:
and can be written as a sum of short convolutions:[1]
where the linear convolution is zero outside the region And for any parameter [upper-alpha 1] it is equivalent to the -point circular convolution of with in the region The advantage is that the circular convolution can be computed more efficiently than linear convolution, according to the circular convolution theorem:
(Eq.2)
where:
DFTN and IDFTN refer to the Discrete Fourier transform and its inverse, evaluated over discrete points, and
is customarily chosen such that is an integer power-of-2, and the transforms are implemented with the FFT algorithm, for efficiency.