COOK TOOM .com



Chapter 5

Fast convolution

1. Introduction

Convolution is a very commonly used operation in digital signal processing. It is very computation intensive and therefore, an efficient way of performing this operation is very useful.

Fast Convolution is a way of implementing convolution algorithm using fewer strong operations like multiplication. i.e. those operations that consume a lot of silicon area.

Algorithmic Strength Reduction is a technique of reducing the number of strong operations, possibly at the expense of an increase in the number of weak operations (such as addition operations).

As an example of Algorithmic Strength Reduction, consider the task of complex number multiplication:

Let (a+jb)(c+jd)=e+jf.

Here a and b are considered as signals and c and d are constants. The calculations can be expressed using the matrix form as follows,

[pic] = [pic] ...(5.1)

( e = ac – bd

( f = ad + bc

This direct multiplication requires 4 multiplication and 2 additions. But the complexity can be reduced to 3 multiplications using following identities,

ac– bd = a (c- d) + d (a-b)

and ad + bc = b (c+d) + d (a-b)

We can verify the identities by opening the brackets.

a (c- d) + d (a-b) = ac –ad + ad– bd = ac– bd

b (c+d) + d (a-b) = bc+ bd + ad– bd = ad + bc

We can observe that the term d(a-b) is reused in the second equation, thus reducing the number of multiplications from 4 to 3. The result consists of a set of three elements,

{(c- d)a (c+d)b d (a-b)}

It can be considered as a dot product of two vectors, {c-d, c+d, d} and {a, b, a-b}. It is convenient to express it as a multiplication of a diagonal matrix and a column matrix as shown below.

(c- d)a c-d 0 0 a

(c+d)b = 0 c+d 0 b ...(5.2)

(d)(a-b) 0 0 d a-b

The column matrix (a, b, a-b)T can be further split into two. Accordingly, above eq. 5.2 can be written as a product of 2x3, 3x3, 3x2 matrices.

= [pic] ...(5.3)

= [C][H][D] [pic][pic]

This is the final answer. We can verify the correctness by multiplying the matrices as follows.

= [pic]

The constant multiplier matrix of eq. 5.1 has been factorized into 3 factors in eq. 5.3. Let us call these factors as C, H and D. D is called pre computation matrix. It requires one addition(actually subtraction, a-b). H is the main computation matrix which requires 3 multiplications. We will not count (c-d) and (c+d) as subtractions as they are constants. C is the post addition matrix and it requires two additions.

The above example illustrates the general strategy for factorizing the multiplier matrix and reusing the multiplied terms. It is very difficult to find such factorizations by manual inspection. There are two algorithms which make this job automatic, namely Cook Toom algorithm and Winograd algorithm. These algorithms are suited for small length convolutions but as we will show later, we can use them as building blocks to construct algorithms for lengthier convolutions.

2. Cook Toom algorithm

5.2.1 Convolution as matrix multiplication:

Consider {h0 h1 ….. hN-1} and {x0 x1 ….. xL-1} as N point and L point in sequences.

For example, let N = 2, L = 3. So h = {h0 h1} x = {x0 x1x2}

H(z) = h0 + h1z-1 X(z) = x0 + x1z-1 + x2 z -2

Convolution in time domain is multiplication H(z) X(z).

x0 + x1 z -1 + x2 z -2

× h0 + h1 z -1

h0 x0 + h0x1 z -1 + h0x2 z -2

+ h1x0 z -1 + h1x1 z -2 + h1x2 z -3

h0 x0 + (h0x1+h1x0) z -1 + (h0x2+h1x1) z -2+ h1x2 z -3

This is nothing but polynomial multiplication

For convenience, we will replace z-1 with p. Thus h and x sequences are polynomials in p.

Convolution S(p) =h(p) x(p). No. of Multiplications required = LN = 6

5.2.2 Lagrange’s Interpolation Theorem

We use this theorem for factorization of convolution matrix.

Consider s(p), an nth degree polynomial. If we know value s(p) at (n+1) points of p, i.e. s((0), s((1) ……s((n).

Then n degree polynomial s(p) can be found out as,

s (p) = [pic] ...(5.4)

The original formula was meant to find s(p) from numerical values of s(βi). But in our case, s(βi) = h(βi) x(βi) where hi and xi are variables.

5.2.3 Cook Toom Algorithm

1) Choose L + N -1 different real numbers (0 (1……(L + N -2. They should be small numbers so that x((i) should be trivial.

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

For example if h=(h0 h1 h2) then h(p) = h0 + h1p+ h2p2

(h((o) = h0+ h1(o + h2(o2

Note that (i are given as numerical values; hi are variable.

Consider (o = -1, h((o) = h0 - h1 + h2

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

Just write the polynomials h((i) x((i) in brackets. Don’t open brackets to multiply at this stage.

Example: S((o) = (h0 - h1+ h2) (x0 – x1)

4) Compute S(p) by expanding Lagrange’s formula and substituting values of (i. Expand the brackets and collect powers of p together. Now find coefficient of S(p) in terms of S((i) i.e. in terms of h((i) x((i).

Then represent S(p) in matrix form, i.e. pre-op and post-op matrices.

If (i are very small integers like 0, +1, +2 then calculation of h((i) and x((i) is trivial. It may require some additions, possibly a shift. We can use positive and negative signed powers of 2 for choice of ( values. These multiplications which are actually shifts, are not counted as calculations.

The main load of multiplications is in step 3 i.e. S((i) = h((i) x((i)

These are L+N-1 multiplications. Thus complexity is reduced from O(LN) to O(L+N-1), at the expenses of increased additions.

Example 5.1( 8.2.1)Construct a 2x2 convolution algorithm using Cook Toom algorithm with ( = 0, 1, -1

Solution:

1) Check L=N=2 ( L+N-1 = 3

We have 3 values of ( = 0 1 -1. It is OK.

2) h(p) = h0 + h1p x(p) = x0 + x1p

(o = 0 h((o) = h0 x((o) = x0

(1 = 1 h((1) = h0+ h1 x((1) = x0 +x1

(2 = -1 h((2) = h0 – h1 x((2) = x0 – x1

3) (o = 0 s((o) = h((o) x((o) = h0x0

(1 = 1 s((1) = h((1) x((1) = (h0+ h1) (x0 +x1)

(2 = -1 s((2) = h((2) x((2) = (h0 – h1) (x0 – x1)

4) (o = 0, (1 = 1, (2 = -1 Write expanded Lagrange's formula.

[pic]

= [pic]

= [pic]

[pic]

= [pic])

= S0 + S1p + S2p2

Equate co-efficient of p in both expressions and write in matrix form.

[pic] ...(5.5)

Keep denominators in S(() column vector and negative signs in the square matrix. So matrix elements are positive / negative and the column vector elements are of the form S((i) / Ki.

Now replace S((i) in column vector with h((i) x((i) from step 3 and express it is a product of a diagonal matrix and a column matrix as illustrated in eq. 5.2.

[pic]

Now replace x((i) as per step 2 and write in matrix form.

[pic]

[pic]

Thus S = C H D x

Computation Method

1) Compute H0 = h0 H1 = [pic] H2 = [pic] (Precomputed)

2) Compute X0 = x0 X1 = x0 + x1 X2 = x0 – x1

This requires 2 additions.

[pic]

3) Find S0 = H0X0 S1= H1X1 S2 = H0X2

This requires 3 multiplications.

[pic][pic]

s0 = H0X0

s1 = H1X1 - H2X2

s2 = -H0X0 + H1X1 + H2X2

This requires 2 additions.

Thus in all, this algorithm requires 5 additions and 3 multiplications. Let us compare it with direct computation.The direct computation matrix is as follows.

[pic]

This requires 4 multiplications and 1 addition.

Example 5.2 (8.4) Construct 2x2 Cook Toom algorithm with ( = 0, 1, 2

Solution:

1) Check L=N=2 ( L+N-1 = 3

We have 3 values of ( = 0 1 2

2) h(p) = h0 + h1p x(p) = x0 x1p

(o = 0 h((o) = h0+ h1x 0 = h0 x((o) = x0 +x1 × 0 =x0

(1 = 1 h((1) = h0 + h1 x 1 = h0 + h1 x((1) = x0 +x1 × 2 = x0 + 2x1

(2 = 2 h((2) = h0 + h1 x 1 = h0 + 2h1 x((2) = x0 – x1 × 2 = x0 + 2x1

3) S((i) = h((i) x((i)

S((o) = h0x0

S((1) = (h0 + h1) (x0 +x1)

S((2) = (h0 – h1) (x0 – x1)

4) Find S(p) by Lagrange formula.

S(p) = [pic]

[pic]

= [pic]

= [pic]

= [pic]

[pic]

= S0 + S1p + S2p2

[pic] = [pic]

[pic] = - [pic]

[pic] =[pic]

Denominator is retained in [pic] vector and – sign transferred to matrix.

[pic]

[pic]

[pic]

Pre addition requires two additions. 2 x1 is computed by left shifting x1 and it is not counted. Post addition requires 4 additions. Total 3 multiplications and & 6 additions are required.

Example 5.3(8.2.2) Construct 2x3 Cook Toom algorithm with ( = {0, 1, -1, 2}

1) L= 3 N = 2 ( L+N-2 = 4

We have 4 values of ( = {0 1 -1 2}

2) h = {h0 h1} x = {x0 x1 x2}

h(p) = h0 + h1p x(p) = x0+ x1p+ x2p2

(o = 0 h((o) = h0 x((o) = x0

(1 = 1 h((1) = h0 + h1 x((1) = x0 +x1+ x2

(2 = -1 h((2) = h0 – h1 x((2) = x0 – x1 + x2

(3 = 2 h((3) = h0 – h1 x((3) = x0+ 2x1+ 4x2

3) S((i) = h((i) x((i)

S((o) = h0x0

S((1) = (h0 + h1) (x0 +x1+ x2)

S((2) = (h0 – h1) (x0 – x1+ x2)

S((3) = (h0+ 2h1) (x0+2x1+ 4x2)

4) Find S(p) by Lagrange

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

Computation Sequence:

1) Precomputed values:

Ho = h0/2

H1 = (h0 + h1)/2

H2 = (h0 – h1)/6

H3 = (h0 + 2h1)/6

2) Preadditions

X0 = x0 0 additions

X1 = (x0 + x2)+x1 2 additions

X2 = (x0 + x2)– x1 1 addition (x0 + x2) is shared

X3 = (x0+ 2x1)+ 4x2 2 additions, shift of x1 is ignored

5 Total Additions

3) So =H0 X0

S1 = H1 X1

S2 = H2 X2 4 Multiplications

S3 = H3 X3

4) so = 2S0 0 additions

s1 = -(S0 + S3) + 2(S1 - S2) 3 additions

s2 = -2S0 + S1 + 3S2 2 additions

s3 = (S0 + S3) -(S1 + S2) 2 2 additions as (S0 + S3) is shared

7 Total Additions

So a total of 12 adders and 4 multiplications are required. Direct computation requires 6 multiplications and 2 additions.

3. Modified Cook Toom algorithm

Finding convolution of an L point sequence with N point sequence with Cook Toom algorithm requires L+N-1 values of ( and results in an L+N-2 degree polynomial s(p). However the coefficient of the highest power of p can be written by simple inspection. Consider the example,

h(p) = h0 + h1p + …… hN-1pN-1

and x(p) = x0 + x1p + …… xL-1pL-1

s(p) = S0 + S1p + ....... SN+L-2 pN+L-2

Highest power of p in s(p) = h(p)x(p) is hN-1 xL-1pN+L-2

Since we know this, we let SN+L-2 = hN-1 xL-1and concentrate on finding remaining terms of polynomial which we will call s’(p).

Thus s’(p) = s(p) - SN+L-2 pL+ N-2

Therefore the degree of s'(p) is L + N -3 .

Modified Algorithm steps

First 3 steps are same as original Cook Toom Algorithm.

1) Choose L+N–2 different numbers as (o, (1….. (L+N-2

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

3) Find S((i) = h((i) x((i)

4) Find S’((i) = S((i) - SN+L-2 (i L+ N-2 for i= 0; L+N-2

5) Find S’(p) using Lagrange formula in expanded form. Open the brackets and collect powers of p to get coefficients of s'(p).

6) Compute S(p) = S’(p) + SN+L-2 pL+ N-2

To do this, we need to enlarge the coefficient multiplier matrix by 1 row & 1 column adding SN+L-2 at bottom right i.e. h01 xL1.

Example 5.4(8.2.3)

Derive 2 x 2 Modified Cook Toom algorithm with (0 = 0 (1 = -1.

1) As L = N = 2, we need 2+2-2 = 2 values of (.

2) h(p) = h0 + h1p x(p) = x0 + x1p

SN+L-2 = h1 x1 (highest powers of h & x)

3) (0 = 0 : h((0) = h0 x((0) = x0

(1 = -1: h((1) = h0 - h1 x((1) = x0– x1

4) S’((i) = S((i) – h1x1 p2

(0 = 0: S’((0) = h((0) x((0) - h1x1(02 = h0x0

(1 = -1: S’((1) = h((1) x((1) - h1x1(12 = (h0 - h1) (x0 - x1) - h1x1

5) S’(p) = S’((0) [pic]

= S’((0) [pic]

= S’((0) [pic]

= S’((0) [pic]

Note that this is much simpler. We can write this in matrix form.

S'0 = 1 0 S’((0)

S'1 1 -1 S’((1)

Now expand the matrix by adding a row and a column to accommodate SN+L-2 i.e. h1x1p2.

S(p) = S’(p) + h1x1p2 = S’((0) + [pic] + h1x1p2

We can write this in matrix form.

[pic] ...(5.6)

Relation between S’((i) and S((i) is as follows.

S’((0) = S((0) - h1x1x(02 = S((0)

S’((1) = S((1) - h1x1x(12 = S((1) – h1x1

Let us write this in matrix form.

[pic]

Substitute this in the column vector on the R.H.S. of eq. 5.6

[pic]

= [pic]

= [pic]

Calculations:

1) H0 = h0 H1 =[pic] H2 =[pic] (Precomputed)

2) X0 = x0 X1 = x0 - x1 X2 = x1 (One addition)

3) S0 = H0X0 S1 = H1X1 S2 = H2X2 (3 Multiplications)

4) s0 = S0 s1 = S0 - S1 + S2 s2 = S2 (2 additions)

This requires total 3 multiplications & 3 Additions.

The calculation Sequence is:

[pic]

[pic]

Example 5.5(8.2.4)Construct a 2x3 Modified Cook Toom algorithm with ( = 0, +1

Solution:

1) N=2 L=3 ( L+N-2 = 3 ( = {0 1 -1}

2) (o = 0 : h((o) = h0 x((o) = x0

(1 = 1 : h((1) = h0 + h1 x((1) = x0 + x1+x2

(2 = -1 : h((2) = h0 - h1 x((2) = x0 – x1+x2

3) S’((i) = S((i) - x2[pic]((i)3

S’((o) = h0x0 - [pic]

S’((1) = (h0 + h1) (x0 +x1+x2) - h1 x2 13

S’((2) = (h0 – h1) (x0 – x1+x2) - h1 x2(- 1)3

4) Find S'(p) by Lagrange formula.

s'(p)

= [pic]

= [pic]

= S’((o) + p[pic] + p2(-S’((o) + [pic] )

s(p) = s’(p) + [pic]3 = s0 + s1p + s2p2[pic]3

= S’((o) + p[pic] + p2(-S’((o) + [pic] )+[pic]3

[pic] ...(5.7)

But s’((i) = s((i) - h1 x2 ((i)3 So from step 3,

s’((o) = s((0) - [pic]

s’((1) = s((1) - [pic]3 = S((1) - [pic]

s’((2) = s((2) - [pic]3 = S((2) + [pic]

Write the relation between S’((i) and S((i) in matrix form.

Substitute this in RHS of eq. 5.7 and expand S((i)

[pic]

Multiply the left two matrices, expand S((i) as a product of diagonal matrix and a column matrix and also expand the column matrix as a product of two matrices. Denominators go to H Matrix.

Finally we have:

[pic]

[pic]

Calculation sequence:

1) H0 = h0 H1 =[pic] H2 = [pic] H3=[pic] (Precomputed)

2) X0 = x0 X1 = (x0 +x2)+ x1 X2 = (x0 +x2) - x1 X3 = x3

(As x0 +x2 term is reused, there are 3 additions)

3) S0 = H0X0 S1 = H1X1 S2 = H2X2 S3 = H3X3 (4 Multiplications)

4) s0 = S0 s1 = S1 - S2- S3 s2 = - S0 + S1 + S2 s3 = S3

(These are 4 additions)

So there are total 7 additions & 4 Multiplications.

4. Winograd algorithm

5. Modified Winograd algorithm

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download