## Threshold Network Synthesis

The significance of the preceding results is that assuming TGs can be built with a cost and delay comparable to that of logic gates, many basic functions can be computed much faster and/or much cheaper using TGs than using logic gates. This is one of the motivations for investigating devices able to implement TGs. However, the usefulness of threshold logic as a design alternative, in general, is determined not only by the availability, cost, and capabilities of the basic building blocks but also by the existence of synthesis procedures. The problem to be solved at this level can be stated as given a combinational logic function, described in the functional do­main (by means of truth tables, logic expressions, etc.), derive a network of the available building blocks realizing f that is optimal according to some design criteria.

Many logic synthesis algorithms exist for targeting conven­tional logic gates but few have been developed for TGs, al­though the problem was addressed as early as the beginning of the 1970s by Muroga. The procedure described by this au­thor (1) transforms the problem of deriving the smallest (low­est gate count) feed-forward network realizing a given func­tion in a sequence of mixed integer linear programming (MILP) problems. The problem of determining whether a given function f can be realized by a feed-forward threshold network with M gates, and if it can, determining the weights and the threshold for each of the M elements can be formu

Concerning two-level (depth-2) threshold networks, an al­gorithm called LSAT (23), inspired in techniques used in clas­sical two-level minimization of logic circuits, has been devel­oped. The core of the algorithm performs as follows. Suppose we have a two-level threshold network satisfying the follow­ing conditions: (1) weights of first-level TGs are restricted to the range [— z, +z] and (2) weights of the second-level gate are all equal to 1 and the threshold of this gate is S. Another threshold network that also satisfies previous conditions (1) and (2) with a minimal number of gates is obtained. This op­eration is repeated increasing S by 1 until a value of S is reached for which no solution is found. As a two-level AND-OR network is a threshold network of the type handled by the procedure with z = 1, S = 1, the algorithm is started with this network. Such a two-level circuit is easy to obtain and in fact is a standard input for other synthesis tools. LSAT has a run-time polynomial in the input size given by n X z, where n stands for the number of variables and z defines the allowed range for the weights. This means central processing unit (CPU) time increases if large weights are required.

The practical use of synthesis procedures for TGs is not restricted to the design of integrated circuits but to areas such as artificial neural networks or matching learning. Dif­ferent problems encountered in these fields are naturally for­mulated as threshold network synthesis problems