Minimizing the number of threshold gates in an error correcting network using multiplexing techniques

Date

1969

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

In this thesis, three methods were discussed for designing error-correcting capabilities into threshold gate networks so that the logic gates themselves will correct errors of other gates. These methods are extensions of work presented by Bargainer and Coates (1). Method II is a procedure for taking a given threshold logic network and finding the minimum number of gates required to correct t errors using multiplexing techniques. It requires that all weights remain the same as read in. Method III is also a procedure for taking a given threshold logic network and finding the minimum number of gates required to correct t errors using multiplexing techniques. However, in Method III a search is performed over the weights for one gate feeding into another gate ([beta][subscript ij]) in an attempt to optimize the [beta][subscript ij] values. Both Method II and Method III modify a given realization by the addition of redundant gates to obtain an error-correcting network. The methods require that an error of any specified number of gates be corrected in the next level of logic. This is known as a multiplexed realization. Errors of the output gate are not corrected. The procedure developed, in this paper, for both Method II and Method III requires the minimization of some cost function. The cost function consists of the sum of all gates required to correct a specified number of errors, plus an error factor due to the constraints not being satisfied. The number of gates in each set {A[subscript i]} are adjusted by a multi-dimensional search technique with the minimization of the cost function as a performance criterion. The search is accomplished by means of a digital computer program. Method III goes one step further than Method II and an attempt is made to reduce the number of gates even further by searching for better weights for inputs from other gates. The results of problems run by both methods are shown in Chapter V. Method II finds the minimum number of gates necessary to correct the specified number of errors, using the weights of the original realization. Method III finds the minimum number of gates necessary to correct the specified number of errors, using an optimum value for the weights of inputs from other gates. Either method may have a minimum gap for all gates specified, to insure that the solution have gates with a reasonable gap width. The procedure to specify a minimum gap is also presented in Chapter V.

Description

Keywords

Citation