A Caltech Library Service

Neural logic : theory and implementation


Bohossian, Vasken Z. (1998) Neural logic : theory and implementation. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/N0T5-7J92.


NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document. 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 networks [20], [37]. 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 [32]. 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 [44], [45]. 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 […], [42], [22]. 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 corresponding 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, [32], proved that any linear threshold element can be implemented with integer weights. That is, by restricting the magnitudes of the weights to natural numbers, one does not lose any 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 square of integers, and still be able to realize all LT functions. We ask the following question. What are the conditions on the subset […] 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 [17], [33], [38], [43] 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 […], within the set of linear threshold functions: the class of functions with "small" (i.e. polynomialy growing) weights [43]. We focus on a single LT element. Our contribution consists in two novel methods for constructing threshold functions with minimal weights, which allow 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 […], 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 [13], [18], 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 [18] 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 […] 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, [38], [56], and hardware implementation, [48], [40]. 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 contributions are at three levels. At the theoretical level, new classes of functions such as […] 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 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 […] 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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:boolean circuits; boolean logic; circuit complexity; neural networks; neuromorphic engineering; threshold circuits; threshold logic
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computation and Neural Systems
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Bruck, Jehoshua
Thesis Committee:
  • Bruck, Jehoshua (chair)
  • Barr, Alan H.
  • Koch, Christof
  • Perona, Pietro
  • Abu-Mostafa, Yaser S.
Defense Date:17 July 1998
Non-Caltech Author Email:vincent (AT)
Funding AgencyGrant Number
NSF Young Investigator AwardCCR-9457811
Sloan Research FellowshipUNSPECIFIED
IBM Alamaden Research Center GrantUNSPECIFIED
California Trade and Commerce Agency, Office of Strategic TechnologyUNSPECIFIED
Record Number:CaltechETD:etd-05132005-143440
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1775
Deposited By: Imported from ETD-db
Deposited On:16 May 2005
Last Modified:31 Aug 2022 00:07

Thesis Files

PDF (Bohossian_v_1998.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page