Search

One engineering parameter of importance in the realization of threshold gate networks is the tolerance which must be placed on the coefficients and threshold of the individual components. A previous paper gives a realization procedure which allows this tolerance to be controlled. The present paper gives an alternate realization procedure which also allows the tolerance to be controlled, but which is somewhat different in its application. The new procedure can be considered to be a generalization of an earlier procedure for the single-element realization problem. The function is first decomposed using a generalization of the function tree and then reconstructed using a generalization of the range theorem plus some additional simplification theorems.

The fundamental differences between mechanical and electronic switching circuits are discussed with special emphasis on the problem of pedestals. Based on the fundamental differences it is shown that Boolean algebra fails to express practical requirements of electronic switches. This paper takes a step in the direction of removing this limitation by augmenting the ON-OFF notation of Boolean algebra by a notation of inequalities to handle the problem of pedestal-free switching. The ideal electronic relay is defined and a diode network realization is synthesized. An electronic switch is synthesized to illustrate the design technique's application. Photographs showing the performance of the circuits are given.

This paper develops a systematic method for the synthesis of electronic circuits which must realize symmetric Boolean functions. The ``fold-down'' method, originated by Shannon [1], solves the problem nicely for relay circuits. The electronic circuit, however, composed of ``and,'' ``or,'' and ``not'' elements, does not seem to incorporate the feature of symmetry as readily. It is shown that for symmetric functions a minimal-not condition exists, and that this form is a powerful tool for synthesis. The minimality is not actually proven, except for the case of fundamental symmetric functions. As with the minimal-or circuit, a minimal-not circuit does not necessarily imply the most economical realization, and the design procedure should take account of this fact.

A tabular minimization procedure for ternary switching functions is developed. The theory is analogous to that used in the McCluskey simplification method for Boolean functions. Using the ternary function truth table, the procedure provides a systematic method of applying a limited set of reduction rules in a converging process for obtaining a minimal irredundant form of the function. It is shown how the procedure can be used to derive simplified expressions for arbitrary ternary functions in terms of a particularly attractive system of threshold gating functions. The procedure has more general applications in providing a simple method of finding, for any given function, all binary variables of the function and all variables of which the function is independent.

A systematic digital computational method is given that involves the use of Boolean matrix equations for solving certain types of functional circuit design problems. Specifically, all sets of Boolean functions f1(A1, . . ., A1), . . ., fJ(A1, - . . ., A1) are found such that if circuits with these outputs are connected to a circuit that generates the known Boolean function F(f1, . . . , fJ, X1, . . ., XK), then the output will produce a given desired function E(A1, . . ., A1, X1, . . ., XK). Illustrative examples of the method are presented.

Threshold functions are a class of Boolean Functions which have been studied for several years under different names such as majority functions, linearly separable functions, and linear input functions.

A parenthesis-free notation is introduced for the representation of series-parallel switching networks. The notation facilitates the calculation of circuit parameters and permits an unambiguous characterization of the circuit topology. Given certain criteria for feasibility of a switching network related to the circuit parameter values, it is shown how an infeasible series-parallel network can be transformed into an equivalent feasible network by ``cascading'' operations applied to the two-terminal sub-networks of the original network. A systematic method is developed, resulting in an optimum choice of cascading operations such that the number of switching elements required to implement the transformed circuit is minimized relative to cascading.

A TANT network is a three-level network composed solely of AND-NOT gates (i.e., NAND gates) having only true (i.e. uncomplemented) inputs. The paper presents an algorithm for finding for any given Boolean function a least-cost (i.e. fewest number of gates) TANT network. The method used is similar to the Quine-McCluskey algorithm for two-level AND/OR networks. Certain functions realizable by input gates or second-level gates are preselected as candidates for possible use in an optimal network. This is analogous to the preselecting of prime implicants in two-level minimization. A network is then obtained by choosing a least-cost subset of the candidates which is adequate for realizing the function. This selection phase is analogous to the use of a prime implicant table in two-level minimization. In TANT minimization, however, an extension to a prime implicant table known as a CC-table must be used. The algorithm permits hand solution of typical four-and five-variable problems. A computer program has been written to handle more complex cases.

The synthesis of Boolean functions is a process for converting some specification for circuit behavior into an expression (optimal in some sense) for a Boolean function. It has been conventional to specify this behavior by means of a table of combinations (or truth table) in which for each system of values for the input variables (i.e., input state) there is associated either the value 1 or the value 0 or the symbol d [1]. These are called, respectively, ONE states, ZERO states and DON'T CARE states. This specification then identifies a nonempty class of Boolean functions and the process of Boolean function synthesis is to select from this class of functions one capable of being represented most simply.

This paper deals with the problem of generating a combinatorial network of threshold gates capable of evaluating a partially specified Boolean function. With the additional restriction that the network is to be cycle-free, the procedure described is designed to generate a network of minimum complexity in the sense that it is comprised of the smallest possible number of threshold elements. The essential result is a demonstration of the fact that the question of whether or not parameters exist such that a network of given complexity is capable of evaluating a given Boolean function is equivalent to the feasibility question for an associated integer program. In the case of feasibility the solution to the integer program contains the design of a minimum network realizing the given function.

The geometric map described in this paper is a graphic representation, using vectors, of the conditions desired in the design of switching networks. This mapping technique makes the well-known techniques such as Boolean algebra, the Quine-McCluskey minimization chart, and Huffman's flow table more effective when designing optimum circuits. Its degree of flexibility in the selection of vectors is advantageous in certain problems.

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+log 2 k] 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.

A method is illustrated for the selection of a minimal cost subset of prime implicants of a Boolean function. The selection problem is represented by a table (P-table), which is an extension of a prime implicant table. A technique for P-table reduction is presented, which allows tabular simplifications for cyclic prime implicant tables also.

In connection with the problem of two-level minimization of systems of Boolean functions, formulas are obtained for the following statistical quantities: average number of k cubes, prime k cubes, and essential k cubes of a system of Boolean functions. The parameters appearing in the formulas are the number of variables, the number of functions of the system, and the number of ``one'' vertices of each function. Numerical evaluations are given. Increasing by one the number of variables n of a system of m functions roughly results in multiplying the average numbers of cubes and prime cubes by a factor of about 2.2 to 2.3. The ratio of the average numbers of essential cubes and prime cubes rapidly decreases increasing n or m, so that the minimization algorithms, which obtain the essential cubes before the prime cubes, seem statistically unsuitable to solve ``large'' minimization problems. The average occupation memory occurring in Quine, McCluskey, and Bartee algorithms is also evaluated. Its rate of increase with the number of variables is about 2.5.

Binary square rooting algorithms which yield a root in a redundant representation using digits 1, ?1, and 0 are analyzed, particularly those yielding a root in a representation in which the number of nonzero digits is minimal. An algorithm which may lead to any possible minimal representation of the square root is developed.

It is shown that by using minimum distance three state assignments and considering error states when deriving the input equations, counters tolerant of a single error can be synthesized. Although one flip-flop in the counter might be in error, the other flip-flops will continue to sequence correctly. Thus acceptable sequencing continues with a malfunctioning unit present in the circuit. Because of the error correcting properties of the state assignment, the correct state of the counter can be recovered. A one-bit error introduced by noise or an intermittent malfunction will be automatically corrected. Failure occurs if more than one flip-flop is in error. Redundancy is incorporated as an inherent result of the initial design procedure rather than being included after a nonredundant working design is obtained. Instead of using any of the known methods of simplification of Boolean functions, the synthesis procedure involves the selection of a minimum number of terms which satisfy a concise set of distance and intersection properties. The selection procedure is intrinsically suitable for machine computation. Although specific logic units are discussed, it is believed that the concepts are general in nature and can be applied to any type of logic hardware.

An algorithm is described for mechanizing Boolean switching functions by means of a net of magnetic toroidal cores. The algorithm is referred to as Simplex and, in this application, is programmed for a digital computer. Computer solutions specify the wiring configuration for a core or net of cores yielding a device for performing combinational logic. Switching functions are realizable in essentially one clock time. The logical designer may synthesize a function directly from the truth table without proceeding in the customary manner of expressing the function in Boolean canonical form and then attempting to minimize with respect to hardware or other criteria by means of algebraic manipulation or a mapping or charting technique.

This paper deals with the problem of compound synthesis of threshold-logic network, or of realizing a general Boolean function with a number of threshold-logic elements. Some basic theorems concerning the expression of a general Boolean function as a combination of a number of threshold functions are presented. The general structure of a network of m threshold-logic elements is analyzed in light of the basic theorems and properties of threshold functions. The properties of isobaric threshold functions are discussed and are utilized for compound synthesis. Methods for decomposing a function into a sum or product of unate functions and into a sum or product of threshold functions are developed. A synthesis procedure conforming with the general structure of a network of threshold-logic elements is given. A simplified synthesis procedure, which needs less cut and trial than the original procedure and is, therefore, more practical, is also presented. Some special situations are discussed. Examples are worked out to show the decomposition of functions, and to illustrate the synthesis method.

This article is primarily concerned with means for finding economical tree circuit realizations?iterative applications of decompositions f(x n , x n-1 ,..., x 1 ) = F i (G i (x n , x n-1 ,..., x? i ,..., x 1 ), H i ,(x n , x n-1 ,..., x? i ,..., x 1 ), x i ) and their associated circuitry?for Boolean functions f(x n , x n-1 ,..., x 1 ). A uniform estimate or inequality shows that when synthesis is effected with two-input-per-gate circuitry, tree circuits are preferable to those which result from conventional sum of products techniques. The practical significance of the estimate is illustrated by its application to the tree circuit synthesis problem. The relationship of tree circuit theory to decomposition theory is established and the extension of the present theory to the corresponding multiple-output and incompletely-specified problems is indicated.

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.

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.