O'Reilly logo

VLSI Digital Signal Processing Systems: Design and Implementation by Keshab K. Parhi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 β0, … , β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

image

Consider an N-point sequence h = {h0, h1, … , hN−1} and an L-point sequence x = {x0, x1, … , xL−1}. The linear convolution of h and x can be expressed in terms of polynomial multiplication as follows:

image

where h(p) = hN−1pN−1 + · · · + h1p + h0, x(p) = xL−1pL−1 + · · · + x1p + x0 and s(p) = s L + N−2PL+N−2 + · · · + s1p + s0. 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 β0,β1, … ,β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

image

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required