电子科技大学：《DSP算法实现技术与架构 VLSI Digital Signal Processing Systems Design and Implementation》课程教学资源（课件讲稿）Chapter 08 快速卷积 Fast Convolution

电子种越女学 University of Electroale Science and Technelery of China 986 Chapter 8 Fast Convolution Dr.Ling National Key Lab of Science and Technology on Communications

Chapter 8 Fast Convolution Dr. Ling National Key Lab of Science and Technology on Communications

8.1 Introduction 986 What is convolution 00 y(n)=x(n)*h(n)=>x(k)h(n-k) k=-00 x(k) ↑x(k) ↑x(k) x(k) h(0-k) h(1-k) h(2-k) h(6-k) 0 y(n) Multiplication Shift n ■Accumulation 2021年2月 2

2021年2月 2 k k 0 0 x(k) h(0-k) k k 0 0 x(k) h(1-k) k k 0 0 x(k) h(2-k) k k 0 0 x(k) h(6-k) n y(n) 0 …… 8.1 Introduction  Multiplication  Shift  Accumulation  What is convolution ?       k y(n) x(n)*h(n) x(k)h(n k)

Fast convolution /96 Fast Convolution:implementation of convolution algorithm using fewer multiplication operations by algorithmic strength reduction. Algorithmic Strength Reduction:Number of strong operations(such as multiplication operations)is reduced at the expense of an increase in the number of weak operations (such as addition operations).These are best suited for implementation using either programmable or dedicated hardware. 2021年2月 3

2021年2月 3 Fast convolution  Fast Convolution: implementation of convolution algorithm using fewer multiplication operations by algorithmic strength reduction.  Algorithmic Strength Reduction: Number of strong operations (such as multiplication operations) is reduced at the expense of an increase in the number of weak operations (such as addition operations). These are best suited for implementation using either programmable or dedicated hardware

966 The examples of algorithms strength reduction e+if=(a+jb)(c+jd)=(ac-bd)+j(bc+ad) Direct implementation 调 4 multiplications and 2 additions 2021年2月 4

2021年2月 4  The examples of algorithms strength reduction  Direct implementation e  jf  (a  jb)(c  jd )  (ac  bd)  j(bc  ad) 4 multiplications and 2 additions

/966 Reduced implementation Using ac-bd a(c-d)+d(a-b) ad+bc=b(c+d)+d(a-b) Rewrite it into matrix form,its coefficient matrix can be decomposed as the product of three matrix: 世服胸 Pre-computed coefficient Step I Step IⅢ Step III 3 multiplications and 3 additions.Thus 1 multiplier saved. 2021年2月 5

2021年2月 5  Reduced implementation  Using  Rewrite it into matrix form, its coefficient matrix can be decomposed as the product of three matrix: ( ) ( ) ( ) ( ) ad bc b c d d a b ac bd a c d d a b           3 multiplications and 3 additions. Thus 1 multiplier saved. Pre-computed coefficient Step I Step II Step III

/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    