TY - JOUR
T1 - On the circuit and VLSI complexity of threshold gate COMPARISON
AU - Beiu, Valeriu
N1 - Funding Information:
This research work has been partly supported under the Human Capital and Mobility programme of the European Community by an Individual Research Training Fellowship for a project entitled: “Programmable Neural Arrays” (contract no. ERBCHBICT941741), and partly by a Directors' Funded Postdoctoral Fellowship offered by Los Alamos National Laboratory, USA.
PY - 1998/4/21
Y1 - 1998/4/21
N2 - The paper overviews recent developments concerning optimal (from the point of view of size and depth) implementations of COMPARISON using threshold gates. We detail a class of solutions which also covers other particular solutions, and spans from constant to logarithmic depths. These theoretical circuit complexity results are extended to VLSI complexity ones, having practical applications to: (i) hardware implementations of integrated circuits; (ii) VLSI-friendly neural learning algorithms (i.e., constructive, or ontogenetic algorithms); and (iii) synthesis methods for mixed digital/analog technologies. In order to estimate the area (A) and the delay (T), as well as the classical AT2, we make use of the following 'cost functions': (i) the connectivity (i.e., sum of fan-ins) and the number-of- bits for representing the weights and thresholds are used as closer approximations of the area; while (ii) the fan-ins and the length of the wires are used for closer estimates of the delay. Such approximations will allow us to compare several solutions - which present very interesting fan- in-dependent depth-size and area-delay tradeoffs - with respect to AT2.
AB - The paper overviews recent developments concerning optimal (from the point of view of size and depth) implementations of COMPARISON using threshold gates. We detail a class of solutions which also covers other particular solutions, and spans from constant to logarithmic depths. These theoretical circuit complexity results are extended to VLSI complexity ones, having practical applications to: (i) hardware implementations of integrated circuits; (ii) VLSI-friendly neural learning algorithms (i.e., constructive, or ontogenetic algorithms); and (iii) synthesis methods for mixed digital/analog technologies. In order to estimate the area (A) and the delay (T), as well as the classical AT2, we make use of the following 'cost functions': (i) the connectivity (i.e., sum of fan-ins) and the number-of- bits for representing the weights and thresholds are used as closer approximations of the area; while (ii) the fan-ins and the length of the wires are used for closer estimates of the delay. Such approximations will allow us to compare several solutions - which present very interesting fan- in-dependent depth-size and area-delay tradeoffs - with respect to AT2.
KW - Area-time complexity
KW - COMPARISON
KW - Circuit complexity
KW - Threshold gates/circuits
KW - VLSI complexity
UR - http://www.scopus.com/inward/record.url?scp=0345698818&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0345698818&partnerID=8YFLogxK
U2 - 10.1016/S0925-2312(97)00099-4
DO - 10.1016/S0925-2312(97)00099-4
M3 - Article
AN - SCOPUS:0345698818
SN - 0925-2312
VL - 19
SP - 77
EP - 98
JO - Neurocomputing
JF - Neurocomputing
IS - 1-3
ER -