The determination of the number of distinct state assignments for a sequential machine has generally been made by the elimination of assignments that are the result of complementation or permutation of the state variables within a basic set of state assignments. For the D-type flip-flop, however, complementation may have an effect upon the cost of the control logic for a machine, leading, as some have interpreted it, to a new distinct state assignment. In this correspondence we reconsider the effect of complementation, showing that a new state assignment is produced only if the choice of Boolean form for the excitation expressions is restricted. This development unifies a previously unresolved question in determining the number of distinct state assignments for sequential machines that are implemented with D-type flip-flops.

The minimization of switching functions involving many variables is a difficult task. This paper presents a new minimization procedure that allows this process to be implemented with reduced computational effort. This procedure, designated as the directed-search algorithm, is applicable to both manual and computer-programmed minimization. The details of the algorithm are presented and illustrated by example. Comparative run-times between another minimization program and the directed-search algorithm, as implemented in Fortran, are also given.

This correspondence is a modification of the basic SHR-optimal1state assignment procedure for the D flip-flop. Under the minimum sum-of-products (MSOP) constraint, a sequential machine with n D flip-flops has 2ntimes as many distinct state assignments and twice as many distinct state assignment columns as the other flip-flop types. This correspondence shows that even though the D flip-flop machine has 2nN total distinct state assignments, the costs of these assignments can be uniquely determined by examination of only N of these assignments. Integration of this concept into the basic SHR-optimal algorithm produces a computational saving on the order of 2n-1times.

In a recently published article, Story et al. detailed an organized search process leading to the optimum state assignment for a synchronous sequential machine. Their procedure begins with the calculation of a set of lower bounds (minimum numbers) on the costs of the excitation logic required for each possible distinct partial state assignment.

By contradictory example, the method proposed by Bubenik for selecting "an irredundant set of prime implicants" is shown to lack generality.

The optimal state assignment procedure by Story, Harrison, and Reinhard [1] depends computationally on the number of distinct state assignment columsn Cdi, i = 1, 2, ..., C(R). C(R) can be computed exactly by see the [Eqa] in pdf file but a bound for C(R) is shown to be C(R) = 2R-1- 1 for R - 1 =2n. Furthermore, for this value of R a distinct state assignment set can be tabulated instead of generated; i.e., Cdi= Ci, i = 1, 2, ..., C(R).