Thesis Abstract

Human brains are by far superior to computers in solving hard problems like combinatorial optimization and image and speech recognition, although their basic building blocks are several orders of magnitude slower. This observation has boosted interest in the field of artificial neural networks [Hopfield82], [Rumelhart82]. The latter are built by interconnecting artificial neurons whose behavior is inspired by that of biological neurons. In this thesis we consider the Boolean version of an artificial neuron, namely, a Linear Threshold (LT) element, which computes a neural-like Boolean function of n binary inputs [Muroga71]. An LT element outputs the sign of a weighted sum of its Boolean inputs. The main issues in the study of networks (circuits) consisting of LT elements, called LT circuits, include the estimation of their computational capabilities and limitations and the comparison of their properties with those of traditional Boolean logic circuits based on AND, OR and NOT gates (called AON circuits). For example, there is a strong evidence that LT circuits are more efficient than AON circuits in implementing a number of important functions including the addition, product and division of integers [Siu93], [Siu94].

It is easy to see that an LT element is more powerful than an AON gate, simply because of the freedom one has in selecting the weights. Indeed, different choices of weights produce different Boolean functions. As a matter of fact, the number of n-input Boolean functions that can be implemented by a single LT element is of the order of 2 to the power of n square, [Schlafli1850], [Irmatov96]. That additional power comes at the cost of added complexity. Some LT functions require weights that are very different in magnitude, potentially rendering difficult hardware or software implementations of the correponding LT elements. For that reason, theoretical research in the field of LT circuits has focused on the weights, in particular the power of LT elements with restricted weights. As early as 1971, Muroga, [Muroga71], proved that any linear threshold element can be implemented with integer weights. That is, by restricting the magnitudes of the weigths to natural numbers, one does not lose any of the power of the original LT element. We generalize this result to arbitrary subsets of the set of real numbers. For example, we show that one can restrict the weights to be the squares of integers, and still be able to realize all LT functions. We ask the following question. What are the conditions on the set D which guarantee that all LT functions can be implemented with weights drawn from it?

Another aspect of the complexity of the weights is their growth as the number of inputs increases. It has been shown [Hastad94], [Myhill61], [Shawe-Taylor92], [Siu91] that there exist linear threshold functions that can be implemented by a single threshold element with exponentially growing weights, but cannot be implemented by a threshold element with smaller : polynomialy growing weights. In light of that result the above question was dealt with by defining a class, called \widehat{LT}, within the set of linear threshold functions : the class of functions with ``small'' (i.e. polynomialy growing) weights [siu91]. We focus on a single LT element. Our contribution consists in two novel methods for constructing threshold functions with minimal weights, which allows us to fill up the gap between polynomial and exponential weight growth by further refining the separation. Namely, we prove that the class of linear threshold functions with polynomial-size weights can be divided into subclasses, \widehat{LT}^{(d)}, according to the degree, d, of the polynomial. In fact, we prove a more general result---that there exists a linear threshold function for any arbitrary number of inputs and any weight size.

Even though some LT functions require weights that grow exponentially with the number of input variables, it has been shown recently, in [Goldmann93], [Hofmeister96], that such functions can be replaced by a two-layer circuit composed of LT gates with polynomially growing, i.e., small weights. We improve the best known bound on the size of that circuit, presented in [Hofmeister96] by focusing on a particular function with large coefficients. We also derive explicit two-layer circuits. Two-layer LT circuits are in general composed of different linear threshold elements, but for some useful Boolean functions, such as parity, addition and product, the gates of the first layer are almost identical. To take advantage of this fact we introduce a new Boolean computing element. Instead of the sign function, it computes an arbitrary (with polynomialy many transitions) Boolean function of the weighted sum of its inputs. We call the new computing element an LTM element, which stands for Linear Threshold with Multiple transitions. The advantages of LTM become apparent in the context of VLSI implementation. Indeed, this new model reduces the layout area of the corresponding symmetric function from O(n^2) to O(n). We present a VLSI implementations of both LT and LTM elements. Two kinds of elements were fabricated, programmable and hardwired. The programmable elements use the charge on a floating gate in order to store the values of the weights.

For many years, the topic of linear threshold logic, has been approached in two different ways, theory, i.e. computational circuit complexity, [Shawe-Taylor92], [Yao90], and hardware implementation, [Dao77], [Shibata92]. Surprisingly, there has been very little interaction between those two approaches. As a whole, the present thesis is one step towards establishing a connection between the theory and implementation of threshold circuits. Its constributions are at three levels. At the theoretical level, new classes of functions such as \widehat{LT}^{(d)} and LTM are defined and their computational power is estimated. At the algorithmic level, we show how to convert real weights to weights drawn from an arbitrary subset of the real numbers, e.g., integer weights, we also show how to construct LT functions with minimal weights, and finally we present an algorithm that produces an \widehat{LT}_2 circuit (circuit composed of gates with small weights), that computes the comparison function, COMP. We also present LTM circuits computing useful functions, such as XOR, ADD, PRODUCT. At the implementation level, we show the design, layout and testing of the VLSI implementation of LT and LTM. Establishing a connection between the theoretical and practical aspects of threshold logic will profit both domains by providing solutions for practical problems and by defining new theoretical questions inspired by implementation issues.

M.Goldmann and M.Karpinski. Simulating threshold circuits by majority circuits. Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 551-56, 1993.

J.Hastad. On the size of weights for threshold gates. SIAM Journal of Discrete Mathematics, 7:484-492, 1994.

T.Hofmeister. A note on the simulation of exponential threshold weights. CONCOON conference, 1996.

J.Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the USA National Academy of Sciences, 79:2554-2558, 1982.

A.A. Irmatov. Estimations of the number of threshold functions. Discrete Mathematics and Applications, 6(6):569-583, 1996.

M.Muroga. Threshold logic and its applications. Wiley-Interscience, 1971.

J.Myhill and W.H. Kautz. On the size of weights required for linear-input switching functions. IRE Transactions on Electronic Computers, 10:288-290, 1961.

D.Rumelhart and J.McClelland. Parallel distributed processing: Explorations in the microstructure of cognition. MIT Press, 1982.

J.S. Shawe-Taylor, M.H.G. Anthony, and W.Kern. Classes of feedforward neural networks and their circuit complexity. Neural Networks, 5:971-977, 1992.

T.Shibata and T.Ohmi. A functional MOS transistor featuring gate-level weighted sum and threshold operations. IEEE Transactions on Electron Devices, 39(6), June 1992.

L.Shläfli. Gesamelte mathematische abhandlugen. Band 1, 1850. Basel: Verlag Birkhäuzer.

K.Siu and J.Bruck. On the power of threshold circuits with small weights. SIAM Journal of Discrete Mathematics, 4(3):423-435, August 1991.

K.Siu, J.Bruck, T.Kailath, and T.Hofmeister. Depth efficient neural networks for division and related problems. IEEE Transactions on Information Theory, 39(3):423-435, May 1993.

K.Siu and V.P. Roychowdhury. On optimal depth threshold circuits for multiplication and related problems. SIAM Journal of Discrete Mathematics, 7(2):284-292, May 1994.

T.Tich-Dao. Threshold I2L and its applications to binary symmetric functions and multivalued logic. IEEE Journal of Solid-State Circuits, 12(5), October 1977.

A.C. Yao. On ACC and threshold circuits. Proceedings of the 31th IEEE Symposium on Foundations of Computer Science, pages 619-627, 1990.