0.12 Convolution algorithms  (Page 6/7)

Distributed arithmetic

Rather than grouping the individual scalar data values in a discrete-time signal into blocks, the scalar values can be partitioned into groups ofbits. Because multiplication of integers, multiplication of polynomials, and discrete-time convolution are the same operations, the bit-leveldescription of multiplication can be mixed with the convolution of the signal processing. The resulting structure is called distributedarithmetic [link] , [link] . It can be used to create an efficient tablelook-up scheme to implement an FIR or IIR filter using no multiplications by fetching previously calculated partial products which are stored in atable. Distributed arithmetic, block processing, and multi-dimensional formulations can be combined into an integrated powerful description toimplement digital filters and processors. There may be a new form of distributed arithmetic using the ideas in [link] , [link] .

Direct fast convolution and rectangular transforms

A relatively new approach uses index mapping directly to convert a one dimensional convolution into a multidimensionalconvolution [link] , [link] . This can be done by either a type-1 or type-2 map. The short convolutions along each dimension are thendone by Winograd's optimal algorithms. Unlike for the case of the DFT, there is no savings of arithmetic from the index mapping alone.All the savings comes from efficient short algorithms. In the case of index mapping with convolution, the multiplications must benested together in the center of the algorithm in the same way as for the WFTA. There is no equivalent to the PFA structure forconvolution. The multidimensional convolution can not be calculated by row and column convolutions as the DFT was by row and columnDFTs.

It would first seem that applying the index mapping and optimal short algorithms directly to convolution would be moreefficient than using DFTs and converting them to convolution to be calculated by the same optimal algorithms. In practical algorithms,however, the DFT method seems to be more efficient [link] .

A method that is attractive for special purpose hardware uses distributed arithmetic [link] . This approach uses a table look up of precomputed partial products to produce a system thatdoes convolution without requiring multiplications [link] .

Another method that requires special hardware uses number theoretic transforms [link] , [link] , [link] to calculate convolution. These transforms are defined over finite fields orrings with arithmetic performed modulo special numbers. These transforms have rather limited flexibility, but when they can beused, they are very efficient.

Number theoretic transforms for convolution

Results from number theory

A basic review of the number theory useful for signal processing algorithms will be given here with specific emphasis on the congruencetheory for number theoretic transforms [link] , [link] , [link] , [link] , [link] .

Number theoretic transforms

Here we look at the conditions placed on a general linear transform in order for it to support cyclic convolution. The form of a lineartransformation of a length-N sequence of number is given by