Cook Toom Algorithm

OVERVIEW
 CONVOLUTION
 FAST CONVOLUTION
 COOK-TOOM ALGORITHM
 EXAMPLE
 ALGORITHM
 MODIFIED COOK-TOOM ALGORITHM
 IMPLEMENTATION OF FILTERBANK
 ADVANTAGES
 REFERENCES
CONVOLUTION
 Mathematical operation on two functions to produce a third
variable, typically viewed as a modified version of the
original function.
 The convolution theorem allows one to mathematically
convolve in the time domain by simply multiplying in the

frequency domain.
 Two types: linear and cyclic
 Linear-(M-1)(N-1) additions and MN multiplications

 Cyclic-N(N-1) additions and N*N multiplications
 For speeding up the calculation-FFT
 Commonly used for fast computation of convolutions
 Disadvantage-complex arithmetic
 Another method is to convert 1D convolution into

multidimensional convolution
 By using efficient short length algorithms

FAST CONVOLUTION
 Convolution using fewer number of operations
 Algorithmic strength reduction: Number of strong

operations is reduced at the expense of an increase in
the number of weak operations.
 Best suited for implementation using programmable

or dedicated hardware.
 Assume (a+jb)(c+jd) = e+jf ,
where (a+jb) is the signal sample
(c+jd) is a coefficient
implemented using 4 multiplications and 2 additions
 Using fast convolution algorithm arithmetic complexity

is reduced to 3 multiplications and 3 additions
COOK-TOOM ALGORITHM
 Minimum number of multiplications
 For non cyclic convolution
( 1)
 This requires 2N-1 multiplications

 Define the generating polynomial of a sequence xi, by
(2)
 Then W(z)=X(z)H(z), (3)
where H(z) and W(z) are generating polynomials of hi

and wi.
 W(z) is a 2N-2 degree polynomial
 To determine the 2N- 1 wi's, select 2N- 1 distinct

numbers αj, j = 0, 1, . . , 2N - 2, and substitute them
for z in (3) to obtain the 2N - 1 products
mj=W(α j)=H(α j)X(αj), j=0,1,…..2N-2 (4)

 Using Lagrange interpolation formula
 (5)
 Cost is 2N-1 multiplications

 (4) can be written in matrix form as, m = ( Ah)x(Ax)
where
 From (5) the coefficients of W(z) will be the linear
combinations of the mj’s and can be written as
w=C*m
where C* is a 2N-1 by 2N-1 matrix
 To calculate cyclic convolution, compute
Y(z)=W(z)mod(zN-1)
which leads to y=Cm, where C is an N by 2N-1 matrix

obtained from C* by performing row operations.
 General form is m=(Ah)x(Bx)
 Value of (Ah) is precomputed.
 B and C will have no multiplications
 Only multiplications are the element by element

multiplication of Ah by Bx.
 Cook-Toom algorithm yields large integer coefficients

in A,B,C matrices which is costly as multiplication.
Example
 (Qn). Calculate the non cyclic 2 point convolution
Using (1)
wo=hoxo
w1=h0x1+h1x0
w2=h1x1
 In terms of z transforms, this is equivalent to
w0+w1z+w2z2=hoxo +(h0x1+h1x0)z+h1x1z2
= ho(x0+x1z)+h1z(x0+x1z)
= (h0+h1z)(x0+x1z)
 Let αj=-1,0,1 for j=0,1,2 in (4)
m0=(h0-h1)(x0-x1)
m1=h0x0
m2=(ho+h1)(x0+x1)
[put z=-1,0,1 in the above eqn. to obtain m0,m1,m2)
 From (5)
So that
w0=m1
w1=(m2-m0)/2
w2=[(m0+m2)/2]-m1
 Transferring denominators from C to A matrix,

combine the factor ½ with hj’s and store the
precomputed constants
a0=(h0-h1)/2
a1=h0
a2=(h0+h1)/2
 Hence
m0=a0(x0-x1)
m1=a1x0
m2=a2(x0-x1)
w0 = m 1
w1=m2-m0
w2=m0+m2-m1
 Only 3 multiplications and 5 additions are required
instead of 4 multiplications and 3 addition
Algorithm
1. Choose L+N-1 different real numbers β0, β1,…. βL+N-2
2. Compute h(βi) and x(βi), for i=0,1,….L+N-2
3. Compute s(βi)=h(βi)x(βi), for i=0,1,….L+N-2
4. Compute s(p) using the equation

 Reduction of operation count occurs if the numbers
β0, β1,…. Βn are carefully chosen
 A better algorithm using Chinese remainder theorem

to compute the convolution as:
S(x)=[D(x)G(x)mod
Modified Cook-Toom Algorithm
 Choose L+N-2 different real numbers β1,… β0, βL+N-2
 Compute h(βi) and x(βi),for i=0,1,…L+N-3
 Compute s(βi)=h(βi)x(βi), for i=0,1,…L+N-3
 Compute s’(βi)= s(βi)-sL+N-2 βiL+N-2, for i=0,1,…L+N-3
 Compute s’(p) using the equation
 Compute s(p)= s’(p)+sL+N-2pL+N-2

IMPLEMENTATION OF FILTER BANK
 Consider two polynomials, g(z-1 )=g0+g1z-1+….+gL-1z-L+1 and
u(z-1)=u0+u1z-1+…uN-1z-N+1
 By computing in normal form it’s product y(z-1) requires
NL multiplications
 Cook-toom algorithm will reduce it to M>=N+L-1
 First, choose a set of interpolation points{ρi}i=0:M-1 that

are the roots of r(z-1) =
 Evaluate y(ρi)=g(ρi)u(ρi)
 Perform Lagrange interpolation to restore
y(z-1)= with
Li(z-1)=
 Eg: Consider g(z-1)=g0+g1z-1(L=2), and u(z-1)=u0+u1z-1 (N=2)
 Choose interpolation points{0,1,-1}
 Then y(0)=u0g0
y(1)=(u0+u1)(g0+g1)
y(-1)=(u0-u1)(g0-g1)
 Lagrange polynomials are calculated as
L0(z-1)=(1-z-2)
L1(z-1)=(z-1+z-2)/2
L-1(z-1)=(-z-1+z-2)/2
ie, y(z-1)=y(0)L0(z-1)+y(1)L1(z-1)+y(-1)L-1(z-1) is
reconstructed
 Multiplication can be written as y=Gu, then algorithm can be
represented as the matrix decomposition G=CDA, with
D=diag(Bg)
 G is the (N+L-1) x N Toeplitz matrix defining the filter g(z-1)
 A is the Vandermonde matrix with Am,n= (n=0:N-1)
 B is also the MxL Vandermonde matrix with Bm,l= (l=0:L-1)
 C is the (N+L-1) x M matrix whose ith column contains the first

N+L-1 coefficients of Li(z-1)
ADVANTAGES
 The number of multiplications have been reduced to
L+N-1 at the expense of an increase in the number of
additions
 Adder has much smaller area and computation time
than multiplier
 Low hardware complexity
 Pre addition and post addition matrices are not simple

REFERENCES
[1]. Zdenka Babic,Danilo P.Mandic, “A Fast Algorithm for
Linear Convolution of Discrete Time signals” , TELSIKS,
pp.no-595-598,September 2001.
[2]. Yuke Wang,Keshab Parhi, “Explicit Cook-Toom Algorithm
for linear convolution” ,IEEE,2000.
[3]. Geert Van Meerbergen, Marc Moonen, Hugo De Man,
“Critically Subsampled filterbanks implementing Reed-
Solomon codes” ,vol 2, pp.no-989-992,IEEE,2004
[4].Keshab K. Parhi, “VLSI digital signal Processing Systems,
Design and Implementation”, pp.no:227-237,New
Delhi,1999.
[5].Ivan W.Selesnick,C. Sidney Burrus, “Fast Convolution and
Filtering” , Digital Signal Processing Handbook, CRC Press
LLC, 1999.
[6]. R. Meyer, R. Reng and K. Schwarz, Convolution
Algorithms On DSP Processors, IEEE,1991.
[7].R.E.Blahut, “Fast Convolution Algorithms for Digital
Signal Processing” , Addison-Wesley,1985.
[8]. H.J.Nussbaumer, “Fast Fourier Transform and
Convolution Algorithms” , Springer-Verlag, Berlin,
Heidelberg, and New York,1981
[9]. Ramesh C Agarwal,James W. Cooley, ”New Algorithms for
Digital Convolution”, IEEE Transactions on Accoustics,
Speech and Signal Processing, Vol. ASSP-25, No.5,October
1997.
[10]. Alberto Zanoni, Toom-”Cook 8-way For Long Integers
Multiplication”, 11th International Symposium on Symbolic
and Numeric Algorithms for Scientific Computing,2009

Cook Toom Algorithm

Uploaded by

Copyright:

Available Formats

Cook Toom Algorithm

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Cook Toom Algorithm

Uploaded by

Copyright:

Available Formats

OVERVIEW

convolve in the time domain by simply multiplying in the

 Linear-(M-1)(N-1) additions and MN multiplications

 For speeding up the calculation-FFT

 Commonly used for fast computation of convolutions

 Another method is to convert 1D convolution into

 By using efficient short length algorithms

 Algorithmic strength reduction: Number of strong

 Best suited for implementation using programmable

where (a+jb) is the signal sample

implemented using 4 multiplications and 2 additions

 Using fast convolution algorithm arithmetic complexity

 This requires 2N-1 multiplications

where H(z) and W(z) are generating polynomials of hi

 W(z) is a 2N-2 degree polynomial

 To determine the 2N- 1 wi's, select 2N- 1 distinct

mj=W(α j)=H(α j)X(αj), j=0,1,…..2N-2 (4)

 Cost is 2N-1 multiplications

where C* is a 2N-1 by 2N-1 matrix

 To calculate cyclic convolution, compute

which leads to y=Cm, where C is an N by 2N-1 matrix

 Value of (Ah) is precomputed.

 B and C will have no multiplications

 Only multiplications are the element by element

 Cook-Toom algorithm yields large integer coefficients

 Transferring denominators from C to A matrix,

2. Compute h(βi) and x(βi), for i=0,1,….L+N-2

3. Compute s(βi)=h(βi)x(βi), for i=0,1,….L+N-2

4. Compute s(p) using the equation

 A better algorithm using Chinese remainder theorem

 Compute s(p)= s’(p)+sL+N-2pL+N-2

 First, choose a set of interpolation points{ρi}i=0:M-1 that

 Eg: Consider g(z-1)=g0+g1z-1(L=2), and u(z-1)=u0+u1z-1 (N=2)

 Choose interpolation points{0,1,-1}

represented as the matrix decomposition G=CDA, with

 G is the (N+L-1) x N Toeplitz matrix defining the filter g(z-1)

 A is the Vandermonde matrix with Am,n= (n=0:N-1)

 B is also the MxL Vandermonde matrix with Bm,l= (l=0:L-1)

 C is the (N+L-1) x M matrix whose ith column contains the first

 Pre addition and post addition matrices are not simple

You might also like