Explicit Cook-Toom algorithm for linear convolution
Y. Wang, Keshab K. Parhi · 2002
The short length linear convolution, conventionally computed by the Cook-Toom algorithm, is important since it is the building block of large convolution algorithms. To compute the linear convolution of N and M points, the Cook-Toom algorithm computes the Lagrange interpolation at L=N+M-1 real numbers. However, the computation is often tedious and has only been carried out for special integers. We present an explicit general formula for linear convolutions which calculates the interpolation at L-2 general non-zero points. We further investigate the linear convolution from VLSI implementation point of view.