VLSI Digital Signal Processing Systems: Design and Implementation

8.4    ITERATED CONVOLUTION

The iterated convolution algorithm makes use of efficient short-length convolution algorithms iteratively to build long convolutions [3]. While these algorithms do not achieve minimal multiplication complexity, they achieve a good balance between multiplication and addition complexity.

Example 8.4.1    Construct a 4 × 4 linear convolution algorithm using 2 × 2 short convolution.

Solution

Let h(p) = h₀ + h₁p + h₂p² + h₃p³, x(p) = x₀ + x₁p + x₂p² + x₃p³, and s(p) = h(p)x(p). First we need to decompose the 4 × 4 convolution into a 2 × 2 convolution. Define (p) = x₂ + x₃p, and q = p². Then we have

and

Therefore, the 4 × 4 convolution is decomposed into two levels of nested 2 × 2 convolutions. Let us start from the top-level 2 × 2 convolution, which is expressed in terms of variable q. Using the 2 × 2 convolution algorithm derived from the previous section, we have

which uses 3 polynomial multiplications, 1 degree-1 polynomial addition and 2 degree-2 polynomial ...