Recently, an algorithm has been developed for deriving optimal NAND array realizations of complete Boolean functions [1]. The algorithm has two defects. It often requires a cumbersomely large amount of computations and does not handle incomplete functions. The short-cut method presented here is free from those defects.

Presented in this correspondence is a tabular method for obtaining minimal sum-of-products representations of Boolean functions. The method uses a single table called the adjacency table. This table provides a record of the adjacency properties of the minterms of the given function. In particular, the table records 1) all adjacent pairs of minterms, 2) the variable absent from each product term subsumed by each pair of adjacent minterms, and 3) each minterm that is adjacent to no minterm. From this table, prime implicants of the function are readily determined by using a simple set operation-intersection-on the sets of absent variables.

The object of this paper is the presentation of a theory of decomposition of Boolean functions having the following properties: 1) ease of understanding and application without previous decomposition theory background; 2) flexibility of application to meet varying logic design criteria; 3) suitability of both numerical calculation and chart techniques; and 4) reduction in the number and complexity of calculations required to achieve decomposition.

Recently, Tan developed a heuristic state assignment algorithm for asynchronous sequential machines. In this paper a state assignment algorithm based on Tan's is developed for synchronous sequential machines. It shares with Tan's algorithm the advantages of simplicity of execution and economy of logic elements in the resulting realizations.

A new type of double-rank synchronous sequential machine is introduced in this paper. Its dissimilarities and similarities with the other types (Types 1 and 2) of double-rank sequential machines are discussed along with the relative merits of each type. Providing a striking example of the advantages of this new type (called Type 3) double-rank machine is a new kind of binary counter, which is highly reliable, fast, and efficient. Circuit realizations of Type 3 double-rank sequential machines can be derived by using a slight variation of a method presently used for Type 2 double-rank machines. This paper shows how the method can be markedly improved.

In this paper there are developed simple processes for deriving, for finite synchronous sequential machines, polylinear sequential circuit realizations using trigger, set–reset, or J–K flip-flops as the memory elements. It is shown that each such realization is directly obtainable from a graph analogous to the reverse state diagram of the given machine; the latter graph was shown in a former paper by this author to correspond to a polylinear sequential circuit realization using delays for memory. The processes consist of the straightforward steps in the construction of the reverse state diagram analogs. Almost polylinear sequential circuits are defined, and it is shown how certain proper subgraphs of the aforementioned graphs can be used to derive these circuits.

Paull and Unger [1] were the first to develop methods for solving the problem of minimizing the number of internal states of incompletely specified sequential machines. Grasselli and Luccio [2] improved upon these methods by introducing rules for reducing the size of the problem and by transforming the problem into a linear integer programming problem. House and Stevens [3] have provided a means of further reducing the size of the problem by developing an additional rule.

This paper is Part II of a two-part study of systematic procedures for realizing synchronous sequential machines using flip-flop memory. In this study the methods of Dolotta and McCluskey, and Weiner and Smith are generalized so that they can be used to obtain directly good realizations of machines using flip-flop memory. In Part I the generalizations were simple, straightforward, and required a minimal amount of changes to the basic methods. For machines using trigger flip-flop memory or a combination of trigger and set-reset, or trigger and J-K flip-flops, these generalizations usually yield significantly better realizations than those obtained from the use of the ungeneralized versions of these methods along with methods for transforming the resulting next-state functions into flip-flop input functions. Minimization of changes of these methods was achieved at the expense of imposing the restriction that the inputs to each of the set-reset and J-K flip-flop types be complementary. In the present paper further generalizations for obtaining even better realizations using trigger, set-reset, and J-K flip-flops are developed by dropping the aforementioned restriction.

This paper is Part I of a two-part study of systematic procedures for realizing synchronous sequential machines using flip-flop memory. In this study the methods of Dolotta and McCluskey, and Weiner and Smith are generalized so that they can be used to obtain directly good realization of machines using flip-flop memory. In Part I the generalizations are simple, straightforward, and require a minimal amount of changes to the basic methods. For machines using trigger flip-flop memory or a combination of trigger and set-reset, or trigger and J–K flip-flops, these generalizations usually yield significantly better realizations than those obtained from the use of the ungeneralized versions of these methods along with methods for transforming the resulting next-state functions into flip-flop input functions. Minimization of changes of these methods was achieved at the expense of imposing the restriction that the inputs to each of the set-reset and J–K flip-flop types be complementary. In Part II of this study1 further generalizations for obtaining even better realizations using trigger, set-reset, and J–K flip-flops are developed by dropping the aforementioned restriction.

Abstract—This paper considers the problem of obtaining realizations of synchronous finite automata from their regular expression specifications. A polylinear sequential circuit realization is defined, and it is proven that every synchronous finite automaton has such a realization. A method is developed for the derivation of a polylinear sequential circuit realization of any automaton specified by a regular expression. The method uses a derivative approach and is applied to the reverse of the given regular expression. As a by-product of developing the method, a connection between the state assigmnent problem and regular expressions is established. Another by-product is a simple method for obtaining polylinear sequential circuit realizations of automata specified by flow tables instead of regular expressions.

An important phase of the design of finite state sequential macilines is the assignmen~ of binary variables to represent their internal states.J. Hartmanis, in a number of papers [1-5], has solved the problem of making such assigmnents economically for seqaential machines which can be decomposed into two or nmre simpler sequential machines or which have reduced dependency relations among their internal state variables.The present, author [61 refined some of the methods and theories of Hartmanis in making assignments for sequential machines with multiply-reduced state variable dependency.In the present paper the methods and theories of the aforementioned papers are extended with the aid of the principles of decomposition theory as developed by Ashenhurst [71 and by this author in [8, 91.The extensions are applicable to sequential machines whose internat state vari~bles can be expressed as composite functions with certain decompositional structures; such maehines encompass those with reduced state variable dependency and hence those which are decomposable into a set of simpler sequential machines.How the results of this paper can be further generalized to provide economical solutions to the state assignment problem for all finite state sequential machines is discussed.

In [1] and [2] this author developed an algorithm for the synthesis of switching circuits in forms with tree-like ch:~raeteristies--generalized tree circuits.Switching functions corresponding to such tree circuits take the form f(xl, x:, ... , x,~) = F[(zt(xl, x: , ... , xj), 42(:cl , x~, ... , xj), ... , ~(x~ , x2 , ..-, xj), x~+~ , ... , z,],where the subfunctions 4,~, 1 -< i -< k, and all succeeding subfunctions assume similar forms.R. Karp [3] refined the algorithm by developing methods for choosing the "best" set of subfunctions ~ from a large possible set on the basis of their disjoint decomposition, symmetric, unate, and threshold strueturM properties.The primary objective of the present paper is to improve further the algorithm.Another objective, a by-product of the first, but possibly a more important one, is to extend the theory of functional decomposition.

An important step in the design of finite state sequential machines is the assignment of binary variables to represent their internal states.In [1] J. Hartmanis studied the problem of determining economical state assignments.In [2] he and R. E. Stearns generalized many of the results of [1].Assignments obtained by the methods of [1] and [2] reduce dependence among the state variables of any sequential machine in which reduction is possible.These methods, however, will not guarantee the production of assignments with a maximal reduction of state variable dependence.The present paper generalizes these methods to produce efficiently and systematically for machines of the aforementioned class assignments in which state variable is optimally reduced.

From the very founding of switching theory by Claude E. Shannon, the tree circuit has been a useful instrument in the design of logic networks. Besides being a valuable practical addition to the designer's “tool kit”, it has been a theoretical asset in the study of circuit complexity and the establishment of general bounds on the relative costs of switching networks. The object of this paper is to expand the practical and theoretical scope of the tree circuit. The expansion is effected by the formulation of a generalized tree circuit, which in actuality is a set of circuits having basic tree circuit characteristics.

article Free Access Share on A Functional Canonical Form Author: H. Allen Curtis Lewis Research Center, N.A S A., Cleveland, Ohio Lewis Research Center, N.A S A., Cleveland, OhioView Profile Authors Info & Claims Journal of the ACMVolume 6Issue 2April 1959 pp 245–258https://doi.org/10.1145/320964.320982Online:01 April 1959Publication History 13citation348DownloadsMetricsTotal Citations13Total Downloads348Last 12 Months16Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The primary objective of this paper is to extend the results of the earlier paper, “A Functional Canonical Form”, in this journal [4]. This extension includes the application of the fundamental functional canonical form to multiple output circuits and the formulation of cost bounds on these circuits. It also includes the use of a multifunctional canonical form in the design of single output circuits.