A comparison of methods for computing sum-of-products in programmable logic devices

In this thesis, the calculation of a sum of products in a programmable logic device using three multiplication methods was investigated. The multiplication approaches analyzed were add-shift, distributed arithmetic, and serial-parallel algorithm multiplication. During the investigation of the algorithms the distributed arithmetic and add-shift proved to be equivalent; thus, only the distributed arithmetic approach was analyzed thoroughly. The VHSIC Hardware Description Language (VHDL) was used to describe the multiplication and summation hardware. The objective of this investigation was to compare the use of logic resources and computation time for the different methods when used in digital filters. The results of the VHDL designs were compared and analyzed to determine the most efficient method in terms of logic cells, as well as the fastest method for digital filter computation.

Representative implementations of the methods were described in VHDL and compiled to an Altera lOK-series programmable logic device. After completion, the design was simulated using Altera Max-i-Plus 11 software. Each multiplier's timing characteristics were examined, as well as the number of logic devices used to implement the design. These results were then generalized to other cases.

The serial-parallel method can be implemented via two schemes. These schemes are external-coefficient and constant-coefficient implementations. The constant coefficient serial-parallel method proved to be the best of all methods in terms of speed, but was found to use a large number of logic cells when many products are required.

With a constraint on the number of logic cells, either the distributed arithmetic or the external-coefficient serial-parallel algorithms offers the best implementation, but at a lower speed. External-coefficient serial-parallel multiplication was found to be slower for larger numbers of products, yet for the application of adaptive filters, has the benefit of allowing the coefficients to be easily modified. However, for increasing numbers of products the distributed arithmetic method has a greater speed advantage over external-coefficient serial-parallel.

The comparisons done in this thesis show that high-order digital filters (512 or more FIR filters taps) can be implemented in current PLDs. Depending on the number of filter taps and bits of precision, the filter sample rate can be several MHz.