Title :
Optimal-depth threshold circuits for multiplication and related problems
Author :
Yeh, Chi-Hsiang ; Varvarigos, E.A. ; Parhami, B. ; Lee, H.
Author_Institution :
Dept. of Electr. & Comput. Eng., Queen´´s Univ., Kingston, Ont., Canada
Abstract :
Multiplication is one of the most fundamental operations in arithmetic and algebraic computations. We present depth-optimal circuits for performing multiplication, multioperand addition, and symmetric function evaluation with small size and restricted fan-in. In particular, we show that the product of two n-bit numbers can be computed using a unit-weight threshold circuit of fan-in k, depth 3 log/sub k/n+log/sub 2/d/log/sub 2/(1+/spl radic/5)-1+o(log/sub k/n+logd)+O(1), and edge complexity O(n/sup 2+1/d/log(d+1)), for any integer d>0. All the circuits proposed in this paper have constant depth when log/sub k/n is a constant and are depth-optimal within small constant factors for any fan-in k.
Keywords :
adders; circuit optimisation; digital arithmetic; function evaluation; multiplying circuits; threshold logic; Boolean function; algebraic computations; arithmetic; constant depth circuits; edge complexity; iterated addition; iterated multiplication; maximum fan-in; multioperand addition; multiplication; optimal-depth threshold circuits; product; symmetric function evaluation; unit-weight threshold circuit; Boolean functions; Computational modeling; Computer networks; Digital arithmetic; Input variables; Integrated circuit interconnections; Neural networks; Performance evaluation;
Conference_Titel :
Signals, Systems, and Computers, 1999. Conference Record of the Thirty-Third Asilomar Conference on
Conference_Location :
Pacific Grove, CA, USA
Print_ISBN :
0-7803-5700-0
DOI :
10.1109/ACSSC.1999.831923
