Comments on “Minimum number of adders for implementing amultiplier and its application to the design of multiplierless digitalfilters”

摘要

For the original paper see ibid., vol. 42 p. 453-460 (July 1995).nIn the aforementioned paper by D. Li, a method of designing integernmultipliers that uses fewer adders than canonic signed-digit (CSD)ncoding was described. This method is claimed by the author to benoptimal, i.e., it produces a multiplier with the least possible adders.nThe commenters claim that they have presented a similar method,nimplemented using the MAG algorithm, to perform the same task, which wasnshown to be optimal. Comparing the two techniques shows that Li's methodnis not necessarily optimal. Both methods perform an exhaustive searchnover a set of multiplier configurations. In the commenters' paper, theyndescribed these configurations in terms of graphs. It is said that thisnmethod proves to be quite useful in that it becomes easy to describe thencases not covered by Li's algorithm. It is stated that the algorithmnproposed by Li is suboptimal because: 1) graphs produced usingnfundamentals (intermediate vertices) of lower cost graphs are notnconsidered; 2) tree-structured graphs are not considered; 3) rightnshifts (divide-by-two) are not allowed, causing some multipliers tonrequire too many adders