SYNTHESIS OF THRESHOLD LOGIC NETWORKS,
Abstract
The purpose of the research described in this report is to develop an algorithm for synthesizing Boolean switching functions with a minimum number of threshold logic units, and to apply the algorithm and its supporting theory to the design of switching networks, including multipleoutput networks. The techniques previously available for the logical design of a switching function using threshold logic required considerable insight and did not, in general, yield economical networks. This research develops an original synthesis procedure for designing a threshold logic network to realize an arbitrary switching function with a minimum number of threshold logic units. An algorithm is developed that converts an originally nonlinearly separable problem into a number of linearly separable problems by specifying the intermediate outputs in a threshold logic network. These linearly separable problems are then solved by already existing techniques, such as linear programming. The synthesis procedure is extended to cover the more general synthesis problem of realizing two or more switching functions with a multiple-output network having the fewest number of threshold logic units. Some of the techniques developed in this research are applicable to the field of adaptive systems. In particular, a procedure is given for adapting the weights of a threshold logic unit that will terminate for both linearly separable and nonlinearly separable problems. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1964
- Accession Number
- AD0443108
Entities
People
- John E. Hopcroft
Organizations
- Stanford University