Graphical Design Techniques for Fixed-point Multiplication

[摘要] This is a tutorial paper that examines the problem of performing fixed-point constantinteger multiplications using as few adders as possible. The driving application is thedesign of digital filters, where it is often required that several products of a singlemultiplicand are produced. Thus two specific problems are examined in detail,i.e.,the one-input/one-output case and the one-input/several-output case. The latter is ofinterest because it can take advantage of redundancy in the different coefficient multipliers.Graphical methods can be used to design multipliers in both cases.For the one-input/one-output case, both optimal and sub-optimal algorithmsintroduced by the author are shown to be the best methods for the design of thesemultipliers. The key to the new methods' success is the use of different graph topologiesto those available under standard methods. The optimal method uses an exhaustivesearch and is limited to short wordlengths, so the suboptimal methods must be used forlong wordlengths. The design is shown to be analogous to the design of algorithms forexponentiation, which is becoming increasingly important in cryptography.For the one-input/several-output (“multiplier block”) case, again new algorithmsdesigned by the author are shown to be the best. When used for designing digital filters,the multiplier block method is more efficient (uses fewer adders) than any other methodthat has been examined. It is so successful at reducing the number of adders used formultiplication that the non-multiplier elements begin to dominate the overall filter cost.It also allows previously unpopular filter structures to compete with structures like thelattice wave structure, despite having more coefficients of longer wordlength. The use ofmultiplier blocks in filter banks is also described.A third case is examined briefly, that of matrix multiplication (several-input/several-output),which is an area of further research.

[学科分类] 电子、光学、磁材料