Abstract—It is shown that there exist finite-state universal sequential machines which are also feedback-shift-register realizable. This proves from another point of view the recently proved fact that any arbitrary sequential machine can be realized with two shift registers: one which is not always binary, stores the input, and has no feedback; and the other which is always binary, is driven from the first shift register, and has feedback. In addition, it is proved that the communication between the two shift registers can be reduced to a single binary line.

Abstract—A reliability criterion and a technique for improving the reliability of threshold elements which have the "perfect-zero" property are suggested. Normally, additional inputs with negative weights are required, but examples are given in which the technique does not require additional circuitry.

A synthesis procedure is introduced for obtaining multithreshold threshold-element realizations of arbitrary Boolean functions (including functions with don't cares). Through transforms of multithreshold threshold-element realizations, the procedure is also applicable to threshold-element-network realizations of functions. The procedure is useful for hand calculations for functions with a small number of variables, and has been programmed on a computer for functions having up to 11 variables-the number of variables is presently limited by storage allocation. The function to be realized is first completely decomposed about its variables to form a tree. The functions resulting at the tips of the tree branches from the complete decomposition have simple ``value functions'' (which specify a set of multithreshold realizations) that are uniquely determined by the weight chosen for the final variable in the decomposition. After choosing this weight, the given function is systematically reconstructed from the tree by choosing the weight of one variable at a time through the combined use of a theorem that specifies the allowable weights of the new variable and an analysis of the minimum possible number of thresholds required as a result of a given allowable weight. Experimental results of hand and computer calculations show the procedure to be fast in producing realizations with a small number of thresholds and a small sum of weight magnitudes.

This paper presents a tabular method for synthesizing Boolean functions having four or less variables with multithreshold threshold elements. The method is similar to that used for conventional single-threshold threshold elements. All 224functions of four variables are divided into 221 equivalence classes by variable complementations and/or permutations and/or function complementation. Each equivalence class is characterized by a subset of its corresponding Rademacher-Walsh coefficients, the size of the subset being determined by the number of thresholds required to realize that equivalence class. An arbitrary Boolean function of four or less variables is synthesized by systematically calculating subsets of its Rademacher-Walsh coefficients until, through simple equivalence operations, the equivalence class of the function is found in a table of the 221 equivalence classes. The table indicates a multithreshold realization of the given function. The table shows that any 4-variable function can be realized with at most five thresholds, or by a network of conventional, or single-threshold, threshold elements with at most three gates in which each gate has the identical weight vector for the four input variables.

In this correspondence it is shown that by applying Gavrilov's test algorithm to any Boolean function numerically represented by its "constrained designation numbers", introduced by Ledley, a very suitable program for the automatic determination of the prime implicants and of the prime implicant table can be established.

A multi-threshold element is one in which several thresholds are used to separate the true inputs from the false inputs. Many circuit elements and configurations can be described by this model. An approach, based on conventional single-threshold threshold elements, is developed for the analysis and synthesis of multithreshold threshold elements. It is shown that the basic properties of such elements are similar to conventional threshold elements, and that k-threshold threshold-element realizability of an arbitrary n-variable Boolean function can be related to conventional threshold-element realizability of a related (n+k-1)-variable Boolean function. Foundations for two basically different methods for the synthesis of a single-element realization of an arbitrary Boolean function are developed, as are procedures for transforming such a realization into both two-level and multilevel loop-free networks of k-threshold threshold elements k≥1. Every element in the networks has the identical weight vector for the independent variables, which is some-times desirable. The transformation technique is a useful approach to the synthesis of functions by networks of conventional threshold elements. It is proved that if the given function requires a k-threshold threshold element, then at least [k/2+I] conventional threshold elements in a two-level network or [1+log2k] such elements in a multilevel network are required. Transformations are given for corresponding minimum-gate networks. Electronic-circuit realizations of multi-threshold elements and some logical-design applications of the multi-threshold approach to network design are discussed. The latter indicate that this approach can be easy to use and can result in economical realizations.