An Approach for the Realization of Multithreshold Threshold Elements

Abstract

An algorithm for the realization of k-threshold threshold realizable functions is presented. Instead of solving the set of linear inequalities, where the unknowns are the weights corresponding to the input variables, incremental weights are sought. The procedure reduces to that of resolving contradicting pairs of vertices by the incremental weights. The minimum number of thresholds are sought for each complementation and permutation of input variables. A definition of an optimal multithreshold weight threshold vector is derived from the reliability viewpoint. The desired solution is obtained through a search of all possible obtainable realization vectors of the function. For single-threshold realizable functions, permutation and complementation of input variables need not be considered if the input variables of the function are ordered and positivized. The procedure is systematic and has been programmed in FORTRAN IV. As a comparison with Haring and Ohori's tabulation on the 221 equivalence classes of four variable Boolean functions under the NPN1 operation, it can be seen that 42 of the 221 equivalence classes need fewer numbers of thresholds for their realization. For the same number of thresholds, 58 equivalence classes have less absolute sum of weights. Finally, with the number of thresholds and absolute sum of weights being equal, 36 equivalence classes have lower threshold values.