A Threshold Gate Feed-Forward Switching Net Algorithm

Citation

Hughes, Gordon Frierson (1964) A Threshold Gate Feed-Forward Switching Net Algorithm. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/K8X1-1697. https://resolver.caltech.edu/CaltechETD:etd-09202002-135451

Abstract

A general algorithm is presented for the efficient computation of feed-forward nets of general threshold gates which realize given bi-valued switching functions. A simplified version of the algorithm is presented for the case of symmetric threshold nets which realize symmetric switching functions. These algorithms produce near-minimal gate nets, and the results of a digital computer program for the general algorithm are presented to illustrate the degree of efficiency and minimality obtained in practice. Both algorithms are proved to give a minimal one-gate net if one exists for a given switching function; a necessary criterion is given for the symmetric algorithm to produce a minimal two-gate net if one exists; and two-gate minimality is also demonstrated for the general algorithm, for a certain class of two-gate switching functions. The case of partially defined switching functions is also treated.

Thesis Files