VLSI Digital Signal Processing Systems: Design and Implementation

8.2    COOK-TOOM ALGORITHM

The Cook-Toom algorithm is a linear convolution algorithm for polynomial multiplication. It is based on the Lagrange interpolation theorem. The Lagrange interpolation theorem states that,

“Let β₀, … , β_n be a set of n + 1 distinct points, and let f(β_i), for i = 0, 1, … , n be given. There is exactly one polynomial f(p) of degree n or less that has value f(β_i) when evaluated at β_i for i = 0, 1, … , n. It is given by

Consider an N-point sequence h = {h₀, h1, … , h_N−1} and an L-point sequence x = {x₀, x₁, … , x_L−1}. The linear convolution of h and x can be expressed in terms of polynomial multiplication as follows:

where h(p) = h_N−1p^N−1 + · · · + h₁p + h₀, x(p) = x_L−1p^L−1 + · · · + x₁p + x₀ and s(p) = s _{L + N−2}P^L+N−2 + · · · + s₁p + s₀. The output polynomial s(p) has degree L + N – 2 and has L + N – 1 different coefficients. Therefore, it can be uniquely determined by its values at L + N − 1 different points. Let β₀,β₁, … ,β_L+N−2 be L + N − 1 different real numbers. If s(β_i), for i = 0, 1, … , L + N − 2 are known, s(p) can be computed using the Lagrange interpolation theorem as

It can be proved that (8.5) is the unique solution for s(p) given the values of ...