Block Convolution using Overlap Add Method
Overlap Add Method:
The overlap–add method is an efficient way to evaluate the discrete convolution of a very long signal with a finite impulse response (FIR) filter where h[m] = 0 for m outside the region [1, M].The concept here is to divide the problem into multiple convolutions of h[n] with short segments of x[n], where L is an arbitrary segment length. Because of this y[n] can be written as a sum of short convolutions.
Algorithm:
The signal is first partitioned into non-overlapping sequences, then the discrete Fourier transforms of the sequences are evaluated by multiplying the FFT xk[n] of with the FFT of h[n]. After recovering of yk[n] by inverse FFT, the resulting output signal is reconstructed by overlapping and adding the yk[n]. The overlap arises from the fact that a linear convolution is always longer than the original sequences. In the early days of development of the fast Fourier transform, L was often chosen to be a power of 2 for efficiency, but further development has revealed efficient transforms for larger prime factorizations of L, reducing computational sensitivity to this parameter.
A pseudo-code of the algorithm is the following:
Algorithm 1 (OA for linear convolution)
Evaluate the best value of N and L
H = FFT(h,N) (zero-padded FFT)
i = 1
while i <= Nx
il = min(i+L-1,Nx)
yt = IFFT( FFT(x(i:il),N) * H, N)
k = min(i+N-1,Nx)
y(i:k) = y(i:k) + yt (add the overlapped output blocks)
i = i+L
end
Note: The following method uses the block convolution algorithm to compute the convolution
Citar como
Sourangsu Banerji (2024). Block Convolution using Overlap Add Method (https://www.mathworks.com/matlabcentral/fileexchange/41338-block-convolution-using-overlap-add-method), MATLAB Central File Exchange. Recuperado .
Compatibilidad con la versión de MATLAB
Compatibilidad con las plataformas
Windows macOS LinuxCategorías
- Signal Processing > Signal Processing Toolbox > Transforms, Correlation, and Modeling > Transforms > Discrete Fourier and Cosine Transforms > Fast Fourier Transforms >
Etiquetas
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Descubra Live Editor
Cree scripts con código, salida y texto formateado en un documento ejecutable.
Versión | Publicado | Notas de la versión | |
---|---|---|---|
1.0.0.0 |