8.1    INTRODUCTION

This chapter addresses implementation of convolution algorithms using fewer multiplication operations. These algorithms, referred to as fast convolution algorithms, belong to the class of algorithmic strength reduction, where the number of strong operations, such as multiplication operations, is reduced possibly at the expense of an increase in the number of weaker operations, such as addition operations. These implementations are best suited for implementation using either programmable or dedicated hardware.

The importance of the fast algorithms in reducing the arithmetic complexity becomes obvious from the following complex multiplication example. Assume (a + jb)(c + jd) = e + jf, where (a + jb) is a signal sample and (c + jd) is a coefficient. This can be expressed using the matrix form

image

This direct implementation requires 4 multiplications and 2 additions. However, using the identities

image

the coefficient matrix can be decomposed as the product of a 2 × 3, a 3 × 3 and a 3 × 2 matrix:

image

The image is the precomputation matrix, which requires 1 addition.

Note that . The is ...

Get VLSI Digital Signal Processing Systems: Design and Implementation now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.