/96 Another example:polynomial multiplication X=x0+X1p+X2p2+. h=ho+hp+hp+..... y=hx=xoho+(hohx)p+(h2x++hox2)p2+..... y(0) y(1) y(2) y(0) Xo y() h h 水 y(2) h h h X2 2021年2月 6
2021年2月 6 Another example: polynomial multiplication 2 0 1 2 2 0 1 2 2 0 0 0 1 1 0 2 0 1 1 0 2 ...... ...... ( ) ( ) ...... x x x p x p h h h p h p y hx x h h x h x p h x h x h x p y(0) y(1) y(2) 0 0 1 0 1 2 1 0 2 (0) (1) (2) ... ... ... ... y h x y h h x y h h h x
Fast convolution /96 In this chapter we will discuss two well-known approaches to the design of fast short-length convolution algorithms: ■ Cook-Toom algorithm (based on Lagrange Interpolation) Winograd Algorithm (based on the Chinese remainder theorem) 2021年2月 7
2021年2月 7 Fast convolution In this chapter we will discuss two well-known approaches to the design of fast short-length convolution algorithms: Cook-Toom algorithm (based on Lagrange Interpolation) Winograd Algorithm (based on the Chinese remainder theorem)
8.2 Cook-Toom algorithm /96 A linear convolution algorithm for polynomial multiplication is based on the Lagrange Interpolation Theorem. Lagrange Interpolation Theorem:Letβo,β：，..β be a set of n+1 distinct points,and let f()for i=0,...,n be given.There is exactly one polynomial p)of degree n or less that has value f(B)when evaluated at B for i=0,...,n. (p-B,) fp)=fBA,)T.B-B,) 2021年2月 8
2021年2月 8 8.2 Cook-Toom algorithm A linear convolution algorithm for polynomial multiplication is based on the Lagrange Interpolation Theorem. Lagrange Interpolation Theorem: Let β0,β1,…,βn be a set of n+1 distinct points, and let f (βi) for i=0,…,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,…,n. n i j i i j j i j i p f p f 0 ( ) ( ) ( ) ( )
8.2 Cook-Toom algorithm 96 Polynomial multiplication s(p)=h(p)x(p) x(p)=x-1p-+●+xp+x0 h(p)=hw-1pN-+●●+hp+h degree s(p)=2+N-2D+N2++Sp+S0 L+N-1 coefficients If s(B),for i=0,1,...,L+N-2 are known,the unique s(p)can be computed as: L+N-2 s(p)=∑s(B,) Πp-B) i=0 Π(B,-B,) 9
9 8.2 Cook-Toom algorithm s( p) h( p)x( p) 1 0 1 1 h( p) h p h p h N N 1 1 1 0 ( ) L L x p x p x p x 2 2 1 0 ( ) L N L N s p s p s p s 2 0 ( ) ( ) ( ) ( ) L N i j i i j j i j i p s p s Polynomial multiplication If s(βi), for i=0,1,…,L+N-2 are known, the unique s(p) can be computed as: degree L+N-1 coefficients
Cook-Toom algorithm 96 Algorithm Steps: ■Choose L+W-1 different real numbersβ，β，..，B+w2 Compute/B)and x(B)for i=0,...,L+N-2 ■Compute s(β)=hβ)x(β)fori=0,..,L+N-2 Compute s(p)using Π(p-B;) sp)=空g)7iB,-B L+N-2 i=0 2021年2月 10
2021年2月 10 Cook-Toom algorithm Algorithm Steps: Choose L+N-1 different real numbers β0,β1,…,βL+N-2 Compute h(βi) and x(βi) for i=0,…,L+N-2 Compute s(βi)=h(βi)x(βi) for i=0,…,L+N-2 Compute s(p) using 2 0 ( ) ( ) ( ) ( ) L N i j i i j j i j i p s p s