966 Algorithm Complexity The goal of the fast-convolution algorithm is to reduce the multiplication complexity.So,if B's are chosen properly,the computation in step-2 involves some additions and multiplications by small constants. By Cook-Toom algorithm,the number of multiplications is reduced from O(LN)to L+N-1 at the expense of an increase in the number of additions. An adder has much less area and computation time than a multiplier.So,the Cook-Toom algorithm lead to large savings in hardware(VLSI)complexity and generate computationally efficient implementation. 2021年2月 11
2021年2月 11 Algorithm Complexity The goal of the fast-convolution algorithm is to reduce the multiplication complexity. So, if βi`s are chosen properly, the computation in step-2 involves some additions and multiplications by small constants. By Cook-Toom algorithm, the number of multiplications is reduced from O(LN) to L+N-1 at the expense of an increase in the number of additions. An adder has much less area and computation time than a multiplier. So, the Cook-Toom algorithm lead to large savings in hardware (VLSI) complexity and generate computationally efficient implementation
Example 8.2.1 /96 Construct a 2x2 convolution algorithm using Cook-Toom algorithm withβ={0,1，-1}. Write 2x2 convolution in polynomial multiplication form as s(p)=h(p)x(p) where h(p)=ho+hiP,X(p)=Xo+X1P,S(p)=So+SP+S2p2. The direct implementation is: s0 h0 hl s2 hl 4 multiplications and 1 additions 2021年2月 12
2021年2月 12 Example 8.2.1 Construct a 2x2 convolution algorithm using Cook-Toom algorithm with β={0,1,-1}. Write 2x2 convolution in polynomial multiplication form as s(p)=h(p)x(p) where h(p)=h0+h1p, x(p)=x0+x1p, s(p)=s0+s1p+s2p 2 . The direct implementation is: s0 s1 s2 h0 h1 h0 h1 x0 x1 4 multiplications and 1 additions
96 Cook-Toom algorithm: Step 1:choose B=10,1,-1}. "Step2:compute h(β)andx(β；) B。=0 h(B。)=h x(B0)=x0 B=1 h(B)=ho+h x(B)=xo+x B2=-1 h(B2)=ho-h x(B2)=xo-x1 Step 3:compute s(B) s(Bo)=h(Bo)x(Bo) s(B)=h(B)x(B) s(B2)=h(B2)x(B2) 2021年2月 13
2021年2月 13 Cook-Toom algorithm: Step 1: choose β={0,1,-1}. Step 2: compute h(βi ) and x(βi ) Step 3: compute s(βi ) 1 1 0 2 1 0 2 0 1 1 0 1 0 0 ( ) ( ) ( ) h h h h h h h h 2 0 1 1 0 1 0 0 ( ) ( ) ( ) x x x x x x x x 0 0 0 1 1 1 2 2 2 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) s h x s h x s h x
966 Step 4:compute s(p) 风a公-公a--会g-1风-风2- (B2-B)(B2-B) =2X-p+0+2P+a)22 =s(B)+p(B)-s(B+B)+BB) 2 2 十 So S1 S2 2021年2月 14
2021年2月 14 1 2 0 2 0 1 0 1 2 0 1 0 2 1 0 1 2 2 0 2 1 2 2 2 0 1 2 1 2 1 2 2 0 0 ( )( ) ( )( ) ( )( ) ( ) ( ) ( ) ( ) ( )( ) ( )( ) ( )( ) ( )( 1) ( ) ( ) 2 2 ( ) ( ) ( ) ( ) ( ) ( ) ( ( ) ) 2 2 p p p p p p s p s s s p p p p s p s s s s s s s p p s Step 4: compute s(p) s0 s1 s2
/966 0 011 s(B。) S1 = 1-1 s(B:)/2 52 11 s(B2)/2 0 0 h(B。) 0 0 x(B。) -1 0 h(B:)/2 0 x(B:) 1 0 0 h(B2)/2」Lx(B) 0 0 0 0 (h。+h)/2 0 1 1 -1 1 0 0 (h。-h)/2j 1 -1 preaddition postaddition Step I Step II Step III 3 multiplications and 5 additions 2021年2月 15
2021年2月 15 Step I Step II Step III 3 multiplications and 5 additions postaddition preaddition